# Inequality on norm in terms of eigenvalue

I came across this inequality but not sure if it's true:

$$|\lambda_{\text{min}}|^2\|\hat{\beta}-\beta\|^2_2\leq (\hat{\beta}-\beta)'\hat{\Sigma}(\hat{\beta}-\beta)$$ where $$\lambda_{\text{min}}$$ is the min eigenvalue of $$\hat{\Sigma}\equiv X'X/n$$ for some $$n\times k$$ matrix $$X$$, and $$\hat{\beta},\beta$$ are $$k\times 1$$.

I take this inequality is equivalent to $$|\lambda_{\text{min}}|\|\hat{\beta}-\beta\|_2\leq \|X(\hat{\beta}-\beta)\|_2/n$$, but not sure where to go from here.

How can the result be shown (if it is indeed true)? Or is something similar true?

Hard to give more context here---I came across it when studying class notes of compatibility constraint in LASSO; but hopefully it doesn't need the context to address.

• If $\hat{\Sigma}$ has full rank and has orthogonal eigenvectors, then the inequality follows. Is this applicable to your context? I can provide a full answer if that is the case. Dec 1, 2021 at 10:33
• Yes, it would be great if you could provide a more detailed explanation. The context is a bit involved, so a context-free explanation should suffice. Dec 1, 2021 at 12:27
• The inequality, as first written, is incorrect: it must not square $|\lambda_{\text{min}}|.$ As a counterexample, consider $X=\pmatrix{2&0\\0&2}$ and let $\hat\beta-\beta$ be any nonzero vector. The whole idea is that the quadratic form on the right hand side is diagonalizable: that is, it's a weighted sum of squares with the eigenvalues (necessarily nonnegative) as weights. Thus, the corrected inequality merely says that when you replace all the weights by the smallest weight, you cannot increase the value. Pretty obvious, right? ;-)
– whuber
Dec 1, 2021 at 16:07
• @whuber, do we need the absolute value, i.e., do we not know that $\lambda_{\text{min}}\geq0$ for the matrix $\hat\Sigma$ (clearly, if so, it would not "hurt")? Dec 1, 2021 at 16:13
• @Christoph that's correct--no absolute value is needed, since $\hat\Sigma$ is manifestly positive semi-definite.
– whuber
Dec 1, 2021 at 16:18

I arrive at a slightly different result and am curious about your thoughts (no square of the minimal eigenvalue). Some experimentation suggests that the inequality (if correct) would be stronger, as the minimal eigenvalue of $$X'X/n$$ generally is less than one.

First, since the quadratic form is a scalar, it equals its trace, $$(\hat{\beta}-\beta)'\hat{\Sigma}(\hat{\beta}-\beta)=tr((\hat{\beta}-\beta)'\hat{\Sigma}(\hat{\beta}-\beta))=tr(\hat{\Sigma}(\hat{\beta}-\beta)(\hat{\beta}-\beta)')$$ Note that $$\hat\Sigma$$ and $$(\hat{\beta}-\beta)(\hat{\beta}-\beta)'$$ are symmetric and psd. Lemma 1 from this link then says that that $$\sum_{i=1}^k \sigma_i b_{k-i+1} \leq tr(\hat{\Sigma}(\hat{\beta}-\beta)(\hat{\beta}-\beta)')$$ for $$\sigma_i$$ and $$b_i$$ the eigenvalues of $$\hat\Sigma$$ and $$(\hat{\beta}-\beta)(\hat{\beta}-\beta)'$$. Now, \begin{align*} \sum_{i=1}^k \sigma_i b_{k-i+1}&\geq\min_i\sigma_i\sum_{i=1}^k b_{k-i+1}\\ &=\min_i\sigma_itr((\hat{\beta}-\beta)(\hat{\beta}-\beta)')\\ &=\min_i\sigma_itr((\hat{\beta}-\beta)'(\hat{\beta}-\beta))\\ &=\min_i\sigma_i(\hat{\beta}-\beta)'(\hat{\beta}-\beta)\\ &=\min_i\sigma_i||\hat\beta-\beta||_2^2, \end{align*} where the first equality uses that the trace equals the sum of the eigenvalues.

Alternatively, write the eigendecomposition of the real symmetric matrix $$\hat\Sigma=Q\Lambda Q'$$ into a matrix $$Q$$ containing the eigenvectors $$q_i$$ and a diagonal matrix $$\Lambda$$ containing the eigenvalues. We may write $$Q\Lambda Q'=\sum_{i=1}^k\sigma_iq_iq_i'\geq\min_i\sigma_i\sum_{i=1}^kq_iq_i'=\min_i\sigma_iQ Q'=\min_i\sigma_iI,$$ since $$Q$$ is orthonormal.

Hence, \begin{align*} (\hat{\beta}-\beta)'\hat{\Sigma}(\hat{\beta}-\beta)&\geq\min_i\sigma_i(\hat{\beta}-\beta)'(\hat{\beta}-\beta)\\ &=\min_i\sigma_i||\hat\beta-\beta||_2^2 \end{align*}

• The answer I provided earlier had a minor mistake, but by correcting I think it arrives at the same inequality here. No square term on the eigenvalue. Dec 1, 2021 at 14:46
• That makes sense, thanks! Yes, so I think the square eigenvalue is then a typo in the notes. Dec 2, 2021 at 3:05

I just want to add that there is also a connection to the Rayleigh quotient, which for the real symmetric $$k \times k$$ Matrix $$\hat{\Sigma}$$ is defined as $$\frac{x^\prime \hat{\Sigma} x }{x^\prime x}, \,x \in \mathbb{R}^{k},\, x \neq 0$$ .

By the Courant–Fischer Theorem, we obtain $$\lambda_{min} = \min_{x \neq 0} \frac{x^\prime \hat{\Sigma} x }{x^\prime x}, \,x \in \mathbb{R}^{k},\, x \neq 0.$$

Let $$\delta:= \hat{\beta}-\beta \in \mathbb{R}^{k}$$ and $$\delta\neq 0$$. Then, $$$$\lambda_{min} = \min_{x \neq 0} \frac{x^\prime \hat{\Sigma} x }{x^\prime x} \leq \frac{\delta^\prime \hat{\Sigma} \delta }{ \delta^\prime \delta} = \frac{(\hat{\beta}-\beta )^\prime \hat{\Sigma} (\hat{\beta}-\beta ) }{ (\hat{\beta}-\beta )^\prime (\hat{\beta}-\beta )},$$$$ where the inequality holds since $$\delta \in \mathbb{R}^{k}, \, \delta \neq 0,$$ and we are minimizing over $$x \in \mathbb{R}^{k}, \, x \neq 0.$$

Rearranging the inequality, we get $$\lambda_{min} \, \Vert\hat{\beta}-\beta \Vert_2^2 \leq (\hat{\beta}-\beta )^\prime \hat{\Sigma} (\hat{\beta}-\beta ) .$$

(For $$\delta=0$$, the last inequality obviously also holds.)

The square in your inequality may be related to singular values? Let $$\sigma_{min}$$ denote the minimal singular value value of $$X/\sqrt{n}$$, then $$\lambda_{min} = \sigma_{min}^2$$ and therefore, $$\sigma_{min}^2 \, \Vert\hat{\beta}-\beta \Vert_2^2 \leq (\hat{\beta}-\beta )^\prime \hat{\Sigma} (\hat{\beta}-\beta ).$$