0
$\begingroup$

What are some lower bounds (if they exist) on $w^t A w$ in terms of $||w||_2^2$ for $A$ an matrix with all positive values? The lower bound can depend on $A$ and $\|w\|_2^2$. $w$ is $k \times 1$. Note when $A = I$ then we exactly get the squared norm of $w$.

If there are no such values, what in the case that $A$ is positive semi-definite? (I.e., $A$ has a $B$ such that $A = BB^T$ and then we are talking $w^tA w = \|Bw\|^2_2$ and we want it to be larger than something that depends on $\|w\|^2_2$).

Thanks.

  • 0
    now that I think of it, for the second case, upper bounds are good as well. Because if, for example, $||Cw||_2^2 < ||C||*||w||_2^2$, then we have $||w||^2_2 = ||B^{-1}Bw|| <= ||B^{-1}||*||Bw||$ and therefore $||Bw|| >= 1/||B^{-1}||*||w||^2_2$.2010-10-14
  • 1
    You need the spectral norm http://mathworld.wolfram.com/SpectralNorm.html If your matrix has some additional structure then you might find the Perron-Frobenius theorem useful http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem2010-10-14
  • 0
    @Jyotirmoy: The spectral norm gives an upper bound on $\|Aw\|$, which is not necessarily equivalent to the upper bound on $w^TAw$ unless $A$ is symmetric. Come to think of it, there's no point computing $w^TAw$ on a non-symmetric $A$, but still, it wasn't specified in the question...2010-10-14

1 Answers 1

3

The bounds on $w^TAw$ are $$\lambda_{\min} \|w\|_2^2 \le w^TAw \le \lambda_{\max}\|w\|_2^2,$$ where $\lambda_{\min}$ and $\lambda_{\max}$ are the smallest and largest eigenvalues, respectively, of $\frac{1}{2}\left(A + A^T\right)$. Each bound is attained when $w$ is parallel to the corresponding eigenvector.