lower bound on norm of matrix vector product

Question

I'm wondering if the following inequality holds

$ \sigma_{min}\|v\|_2 \leq \|Av\|_2$

, where $ \sigma_{min}$ is the smallest singular value of A. Furthermore, assuming that A is positive definite and $v \in \mathbb{R^n}$.

Thank you :)

Answer 1

As Brian noted above we have from a SVD that: $Av=UΣV^Tv$, with $U$ and $V$ orthogonal and for orthogonal matrices holds $\|Av\|=\|v\|$.

Thus: $$\|Av\|_2=\|UΣV^Tv\|_2=\|U(ΣV^T)v\|_2=\|V^T(Σv)\|_2=\|Σv\|_2=\sqrt{\sigma_1^2v_1^2+...+\sigma_n^2v_n^2}\\ \geq \sqrt{\sigma^2_{\min}(v_1^2+...+v_n^2)}=\sigma_{\min}\|v\|_2$$

Answer 2

This is equivalent to showing that $$||Av||\geq\sigma_{min}$$ for every vector $v$ with $||v||=1$. Let $(e_1,...,e_n)$ be an orthonormal basis in which $A$ is diagonal, $\lambda_1=\sigma_{min},...,\lambda_n$ the associated eigenvalues in increasing order, and write $v=\sum_{i=1}^nv_ie_i$. Then $$Av=\sum_{i=1}^n\lambda_iv_ie_i$$ so that (by orthonormality of the basis): $$||Av||^2=\sum_{i=1}^n\lambda_i^2||v_i||^2$$ Since $\lambda_1\leq...\leq\lambda_n$ and $\sum_{i=1}^n||v_i||^2=1$, the minimum of this function is assumed if $v_1=1$ and $v_2=...=v_n=0$ so that $$||Av||^2\geq\lambda_1^2=\sigma_{min}^2$$

Answer 3

Be careful: the current accepted best answer posted by Jonasson might be confusing if $A$ is not a square matrix. Even though the author mentioned $A$ was positive definite (hence necessarily square), using the singular value decomposition in its general form may suggest $A$ is rectangular. I personally think it would have been sufficient and clearer to use the eigenvalue decomposition of $A$ in this specific case.

In particular, there is a dimension mismatch in $V^\top\Sigma v$ if $A$ is not a square matrix. However, the result is still valid when $A$ has a general rectangular form; following what Thoth wrote in a more concise way:

$\| Av \|_2^2 = \| U\Sigma V^\top v \|_2^2 = \| \Sigma V^\top v\|_2^2$ since $U$ is orthogonal. In addition, noting $\sigma_i$ the $i^{\text{th}}$ singular value of $A$ and using the fact that $\sigma_i \geq \sigma_{\text{min}} \geq 0$ for all $i$, one has

$$\| \Sigma V^\top v\|_2^2 = \| \Sigma (V^\top v)\|_2^2 = \sum_{i}\sigma_i^2 |(V^\top v)_i|^2 \geq \sigma_{\min}^2 \sum_{i} |(V^\top v)_i|^2 = \sigma_{\min}^2 \|V^\top v\|^2 = \sigma_{\min}^2 \|v\|^2 \ ,$$ where the last equality follows from the fact that $V$ is orthogonal.