Specific Spectral Norm Inequality

Question

Let $\Sigma, V\in\mathbb{R}^{d\times d}$ be positive definite and $\beta, y\in\mathbb{R}^d$.
Claim: $$ (y-V\beta)^T\Sigma^{-1}(y-V\beta) \ge \left(\lVert \beta \rVert_2 / \lVert (V^T\Sigma^{-1}V)^{-1/2}\rVert_2 - \lVert \Sigma^{-1/2}y \rVert_2 \right)^2 $$ Own work:
I almost have it, so I feel like either I used a too weak bound at some point or the statement is just not true. Here's what I did: Expanding the left-hand side yields $$ (y-V\beta)^T\Sigma^{-1}(y-V\beta) = \lVert \Sigma^{-1/2}y\rVert_2^2 + \beta^TV^T\Sigma^{-1}V\beta - 2y^T\Sigma^{-1}V\beta. $$ Now from $\lVert u \rVert = \sup_{\lVert v \rVert=1}u^Tv$ for any $u,v\in\mathbb{R}^d$ we have $$y^T\Sigma^{-1}V\beta \le y^T\Sigma^{-1/2}\Sigma^{-1/2}V\beta/\lVert\Sigma^{-1/2}V\beta\rVert_2\lVert\Sigma^{-1/2}V\beta\rVert_2 \le \lVert \Sigma^{-1/2}y\rVert_2 \lVert\Sigma^{-1/2}V\rVert_2\lVert\beta\rVert_2. $$ Courant-Fischer's theorem tells us $\lambda_{\min}(A)v^Tv \le v^TAv$, where $\lambda_{\min}(A)$ denotes the smallest eigenvalue of $A\in\mathbb{R}^{d\times d}$, and since for symmetric $A$ we have $1/\lVert A^{-1} \rVert_2 = \lambda_{\min}(A)$, we get $$ \beta^TV^T\Sigma^{-1}V\beta\ge\lVert \beta \rVert_2^2/\lVert (V^T\Sigma^{-1}V)^{-1}\rVert_2, $$ so all together $$ (y-V\beta)^T\Sigma^{-1}(y-V\beta) \ge \lVert \Sigma^{-1/2}y\rVert_2^2 + \lVert \beta \rVert_2^2/\lVert (V^T\Sigma^{-1}V)^{-1}\rVert_2 -2\lVert \Sigma^{-1/2}y\rVert_2 \lVert\Sigma^{-1/2}V\rVert_2\lVert\beta\rVert_2 $$ I fail to put this in the claim's nice binomial form, since $$ 1/\lVert (V^T\Sigma^{-1}V)^{-1}\rVert_2 = \lambda_{\min}(V^T\Sigma^{-1}V) \le \lambda_{\max}(V^T\Sigma^{-1}V) = \lVert\Sigma^{-1/2}V\rVert_2^2. $$ Can someone help? Thanks a lot!

Answer 1

It depends on whether the term inside the pair of brackets on the RHS (without being squared) is nonnegative or not. Let $z=\Sigma^{-1/2}y,\,x=\Sigma^{-1/2}V\beta$ and $A=\Sigma^{-1/2}V$. Since $\|(V^T\Sigma^{-1}V)^{-1/2}\|_2=\|(A^TA)^{-1/2}\|_2=\|A^{-1}\|_2$, the inequality $$ (y-V\beta)^T\Sigma^{-1}(y-V\beta) \ge \left(\frac{\|\beta\|_2}{\|(V^T\Sigma^{-1}V)^{-1/2}\|_2} - \|\Sigma^{-1/2}y\|_2 \right)^2 $$ can be rewritten as $$ \|z-x\|_2^2 \ge \left(\frac{\|A^{-1}x\|_2}{\|A^{-1}\|_2} - \|z\|_2 \right)^2.\tag{1} $$ If the term inside the brackets on the RHS is nonnegative, the inequality becomes $$ \|x-z\|_2+\|z\|_2 \ge \frac{\|A^{-1}x\|_2}{\|A^{-1}\|_2}, $$ which is true because the LHS $\ge\|x\|_2\ge$ the RHS.

However, if the term inside the brackets on the RHS of $(1)$ is negative, then $(1)$ becomes $$ \frac{\|A^{-1}x\|_2}{\|A^{-1}\|_2} + \|z-x\|_2 \ge \|z\|_2,\tag{2} $$ which is false in general, as shown by the counterexample in the other answer. Conceptually, when $z=x$ is not a singular vector corresponding to the largest singular value of $A^{-1}$, the LHS of $(2)$ is strictly smaller than the RHS.

Answer 2

In fact, it is false. Take $d=2$, $\Sigma = I$, $\beta^T = [0\,\, 1]$, $y^T = [0\,\, 2]$ and $$ V = \begin{pmatrix} 1 &0\\0&2\end{pmatrix}. $$ Since $y=V\beta$, the left hand side of your inequality is zero, but the right hand side is $$ \left( 1 - 2 \right)^2 = 1 > 0. $$