Proof of Eckart-Young-Mirsky theorem

Could someone please explain why in this Wiki page one says "we know that $\exists(k+1)$ dimension space $(v_1,v_2, \dots, v_n)$" ?

I've found that proof unreadable (missing symbols, text makes no sense occasionally, etc.). One needs to show that if $\mathrm{rank}(B)=k$, then $\|A-B\|_2\geq\|A-A_k\|_2$. This can be done as follows.

Since $\mathrm{rank}(B)=k$, $\dim\mathcal{N}(B)=n-k$ and from $$\dim\mathcal{N}(B)+\dim\mathcal{R}(V_{k+1})=n-k+k+1=n+1$$ (where $V_{k+1}=[v_1,\ldots,v_{k+1}]$ is the matrix of right singular vectors associated with the first $k+1$ singular values in the ascending order), we have that there is an $$x\in\mathcal{N}(B)\cap\mathcal{R}(V_{k+1}), \quad \|x\|_2=1.$$ Hence $$\|A-B\|_2^2\geq\|(A-B)x\|_2^2=\|Ax\|_2^2=\sum_{i=1}^{k+1}\sigma_i^2|v_i^*x|^2\geq\sigma_{k+1}^2\sum_{i=1}^{k+1}|v_i^*x|^2=\sigma_{k+1}^2.$$ From $\|A-A_k\|_2=\sigma_{k+1}$, one gets hence $\|A-B\|_2\geq\|A-A_k\|_2$. No contradiction required, Quite Easily Done.

EDIT An alternative proof, which works for both the spectral and Frobenius norms, is based on the Weyl's theorem for eigenvalues (or more precisely, its alternative for singular values): if $X$ and $Y$ are $m\times n$ ($m\geq n$) and (as above) the singular values are ordered in the descreasing order, we have $$\tag{1} \sigma_{i+j-1}(X+Y)\leq\sigma_i(X)+\sigma_j(Y) \quad\text{for 1\leq i,j\leq n, \; i+j-1\leq n}$$ (this follows from the variational characterization of eigen/singular values; see, e.g., Theorem 3.3.16 here). If $B$ has rank $k$, $\sigma_{k+1}(B)=0$. Setting $j=k+1$, $Y:=B$, and $X:=A-B$, in (1) gives $$\sigma_{i+k}(A)\leq\sigma_i(A-B) \quad \text{for 1\leq i\leq n-k}.$$ For the spectral norm, it is sufficient to take $i=1$. For the Frobenius norm, this gives $$\|A-B\|_F^2\geq\sum_{i=1}^{n-k}\sigma_i^2(A-B)\geq\sum_{i=k+1}^n\sigma_i^2(A)$$ with the equality attained, again, by $B=A_k$.

• Thank you. Maybe i'm missing something, but what i don't understand is this: what has $V_{k+1}$ to do with everything else and how it is connected to rank(B). – Alex Gaspare Apr 18 '14 at 13:41
• @AlexGaspare I'm not sure I've understood the question. $V_{k+1}$ is formed from the first $k+1$ right (not left, sorry) singular vectors of $A$, that is, first $k+1$ columns of $V$ from the SVD $A=U\Sigma V^*$; truncating this SVD determines the optimal approximation $A_k$. It does not have much to do with the rank of $B$, except that it has a non-trivial intersection with the nullspace of $B$ by the dimensional argument (if the sum of the dimensions of two subspaces of an $n$-dimensional subspace is larger than $n$, they have non-trivial intersection). – Algebraic Pavel Apr 18 '14 at 13:46
• @AlexGaspare Squaring norms is not needed, it's there just to avoid typesetting square roots. The numbers are all non-negative so it does not matter. If $C$ is a matrix and $\|x\|_2=1$, then $\|Cx\|_2\leq\|C\|_2$ simply because $\|C\|_2=\max_{\|x\|_2=1}\|Cx\|_2$ (so taking a particular $x$ in $\max$ is a lower bound for the $\max$). – Algebraic Pavel Apr 25 '14 at 13:04
• @gosbi It's because $x\in\mathcal{R}(V_{k+1})$, so it can be written as a linear combination of $v_1,\ldots,v_{k+1}$. – Algebraic Pavel Apr 3 '15 at 18:26
• @gosbi The problem of the last equality is that you forgot that square. – Algebraic Pavel Apr 4 '15 at 13:59

Here's a slightly simplified version of the proof on wiki.

As shown there, $\left \| A - A_k \right \|_2 = \sigma_{k+1}$. Now, suppose $\exists \ B$ such that $\mathrm{rank}(B) \leq k$ and $\left \| A - B \right \|_2 < \left \| A - A_k \right \|_2$. Then, $\text{dim} (\mathrm{null}(B)) \geq n-k$. Let $w \in \mathrm{null}(B)$, then $$\left \| A w \right \|_2 = \left \| (A - B)w \right \|_2 \leq \left \| A - B \right \|_2 \left \| w \right \|_2 < \sigma_{k+1} \left \| w \right \|_2$$ Also, for any $v \in \mathrm{span}\{ v_1,v_2,\cdots,v_{k+1} \}$, $\left \| A v \right \|_2 \geq \sigma_{k+1} \left \| v \right \|_2$. But, $$\mathrm{null}(B) \cap \mathrm{span}\{ v_1,v_2,\cdots,v_{k+1} \} \neq \{0\}$$ So, $\exists$ a non-zero vector lying in both spaces. This'll lead to a contradiction.

The original statement of Eckart-Young-Mirsky theorem on wiki is based on Frobenius norm, but the proof is based on 2-norm. Though Eckart-Young-Mirsky theorem holds for all norms invariant to orthogonal transforms, I think it is necessary to add a proof purely based on Frobenius norm since it is even easier to prove than that based on 2-norm.

The following proof is replicated from these notes.

Since $||M-X_k||_F = ||U\Sigma V^\intercal - X_k||_F = ||\Sigma - U^\intercal X_k V ||_F$, denoting $N = U^\intercal X_k V$, an $m \times n$ matrix of rank $k$, a direct calculation gives $$||\Sigma-N||_F^2 = \sum_{i,j} |\Sigma_{i,j} - N_{i,j}|^2 = \sum_{i=1}^r |\sigma_i-N_{ii}|^2+\sum_{i>r}|N_{ii}|^2+\sum_{i\neq j} |N_{i,j}|^2$$ which is minimal when all the non diagonal terms of $N$ equal to zero, and so are all diagonal terms with $i > r$. Obviously, the minimum of the terms left is attained when $N_{ii} = \sigma_i$ for $i = 1,2,\cdots,k$ and all other $N_{ii}$ are zero.

• I think this proof is incorrect. Since $\mathrm{rank}(N) \le k$, all the $N_{ij}$ are coupled with one another. So it does not follow that the minimum should be attained when $N_{ij}=0$ for $i\ne j$. – Laurent Lessard Oct 18 '16 at 5:43