relation of singular values of A and A+E with spectral norm of E

Question

let $A$ an $n\times m$ matrix and $p = \min(m, n)$. if $\{\sigma_1 ,\sigma_2,...,\sigma_p\}$ and $\{\alpha_1,\alpha_2,...,\alpha_p\}$ be the all singular values of $A$ and $A+E$ respectively,

the question is to prove that for each $k = 1,2,...,p$ we have:

$|\sigma_k - \alpha_k| \le \|E\|_2$.

Also there is a theorem called Eckhart-Young that I think is related to this question but I can't figure out how to use it. you can see it in following link: Eckart–Young–Mirsky theorem (for spectral norm)

Answer 1

We can prove this using the min-max principle for singular values, as stated here. The principle states that for a given matrix $M$, if $\sigma_k(M)$ denotes the k-th singular value of $M$ (in increasing order) then:

$\sigma _{k}(M)=\min _{S:\dim(S)=k}\max _{x\in S,\|x\|=1}\|Mx\|$

By using this principle, we will show that for any matrices $M, N$, we have $\sigma_k(M+N) \leq \sigma_k(M) + \|N\|_2$.

Note that for any $x$ such that $\|x\|_2 = 1$, we have: $\|(M+N)x\| = \|Mx + Nx\| \leq \|Mx\| + |Nx\| \leq \|Mx\| + \|N\|_2 \|x\|= \|Mx\|+ \|N\|_2$

It follows that:

$\begin{align*} \sigma _{k}(M+N)&=\min _{S:\dim(S)=k}\max _{x\in S,\|x\|=1}\|(M+N)x\|\\ &\leq \min _{S:\dim(S)=k}\max _{x\in S,\|x\|=1}\|Mx\|+ \|N\|_2 \\ & = \left(\min _{S:\dim(S)=k}\max _{x\in S,\|x\|=1}\|Mx\|\right)+ \|N\|_2 \\ &= \sigma_k(M) + \|N\|_2 \end{align*}$

Letting $M = A, N = E$ in the statement gives:

$\sigma_k(A+E) \leq \sigma_k(A) + \|E\|_2$.

Letting $M = A + E, Y=-E$ in the statement gives:

$\sigma_k(A) \leq \sigma_k(A+E) + \|-E\|_2 = \sigma_k(A+E) + \|E\|_2$.

Combining these two inequalities, we have $|\sigma_k(A+E) - \sigma_k(A)| \leq \|E\|_2$ as desired.

Answer 2

A direct proof, using the SVD-version of the Courant-Fischer theorem: we have $$ \sigma_k = \min\left\{ \max_{x \in U, \|x\| = 1} \|Ax\|:U \subset \Bbb C^n \text{ is a subspace},\ \dim(U) = n-k+1\right\}. $$ On the other hand, for any $\|x\| = 1$, we have $$ \|(A + E)x\| \leq \|Ax\| + \|Ex\| \leq \|Ax\| + \|E\|_2. $$ Similarly, $\|(A + E)x\| \geq \|Ax\| - \|E\|_2$. It follows that $$ \alpha_k = \min_{\dim(U) = n-k+1} \left(\max_{x \in U, \|x\| = 1} \|(A + E)x\|\right) \\ \leq \min_{\dim(U) = n-k+1} \left(\max_{x \in U, \|x\| = 1} \|E\|_2 + \|A x\|\right) \\ = \|E\|_2 + \min_{\dim(U) = n-k+1} \left(\max_{x \in U, \|x\| = 1} \|A x\|\right) = \sigma_k + \|E\|_2. $$ Similarly, $\alpha_k \geq \sigma_k - \|E\|_2$. So indeed, $|\alpha_k - \sigma_k| \leq \|E\|_2$, as desired.