Is $\sigma_n \|x\|_2 \leq \|Ax\|_2 \leq \sigma_1 \|x\|_2$?

Question

It is known that if $A \in \mathbb{R}^{n \times n}$ has singular values $\sigma_1 \geq ... \geq \sigma_n$ then $\|Ax\|_2 \leq \|A\|_2\|x\|_2 = \sigma_1\|x\|$.

Is the "opposite" also true? I.e., is $\|Ax\|_2 \geq \sigma_n\|x\|_2$ ?

Answer 1

Yes.

Recall that by the singular value decomposition, $A = USV^T$, where $U$ and $V$ are unitary. Since unitary matrices like $U^T$ are rotations, and rotations preserve lengths, $|Ax| = |U^T Ax| = |SV^T x|$. Now since $x$ can be split into a linear combination of rows of $V$, $|SV^T x|$ is smallest when $x$ is a multiple of the row corresponding to $\sigma_n$, and largest when $x$ is the a multiple of the row corresponding to $\sigma_1$. So $\sigma_n |x| \le |Ax| \le \sigma_1 |x|$.

Answer 2

Let me explain more detail for @Timur's answer.

Consider SVD decomposition

$A = USV^T$ therefore $U^TA = SV^T$

we know that $U$ and $ V$ are unit orthogonal matrix,and orthogonal transformation did not change the euclidian distance.

that is

$||Ax|| = ||U^TAX|| = ||SV^Tx||$

our main concern become $||SV^Tx||$

notice V is n by n Full rank matrix

and $\boldsymbol{v_{r1}},\boldsymbol{v_{r2}},...,\boldsymbol{v_{rn}}$ are the row vector of V.

therefore:

$$ x = k_1\boldsymbol{v_{r1}} + ...+ k_n\boldsymbol{v_{rn}}$$ $$ V^Tx = k_1V^T\boldsymbol{v_{r1}} + ...+ k_nV^T\boldsymbol{v_{rn}}=(k_1,k_2,...k_n)^T$$

left multiply an $S$

$$ SV^Tx = S(k_1,k_2,...k_n)^T = (\sigma_1k_1, \sigma_2k_2, ...,\sigma_nk_n)^T$$

we know that $\sigma_1$ is the largest singular value of A

$$ ||SV^Tx|| = ||(\sigma_1k_1, \sigma_2k_2, ...,\sigma_nk_n)^T|| <= ||(\sigma_1k_1, \sigma_1k_2, ...,\sigma_1k_n)^T|| = \sigma_1 ||V^Tx||$$

Again, orthogonal transform action did not change the distance.

$$||V^Tx|| = ||x||$$

combine the last two formula

$$ ||Ax|| = ||SV^Tx|| <= \sigma_1||x|| $$

the $\sigma_n$ term can be proved similarly.

Answer 3

The singular values of $A$ are square roots of the eigenvalues of $A^TA$, which is positive semidefinite. That is, $\sigma_n = \sqrt{\lambda_n}$ where $\lambda_n$ is the smallest eigenvalue of $A^TA$. We have $$ \lambda_n = \min_{\|x\|=1}x^TA^TAx = \min_{\|x\|=1} \|Ax\|_2^2 $$ thus $$ \sigma_n = \min_{\|x\|=1}\|Ax\|_2 $$ The conclusion should be immediate then.