# 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)$" ?

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 descending order), we have that there exists 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$$.

• @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). Apr 18, 2014 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$). Apr 25, 2014 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}$. Apr 3, 2015 at 18:26
• @AlgebraicPavel Then, I don't understand where $A$ is, as for what I have understood, $v_i^*x$ is just a way to write $x$. I tried to compute it explicitly, but I got quite a different result: $$\| A x \|_2 = (Ax)^*(Ax) = x^*V\Sigma^*U^*U\Sigma V^*x = (V^*x)^*\Sigma^2(V^*x) = \sum_{i=1}^{k+1}\sigma_i^2\mid v_i^* x\mid$$ where the term in the sum is not squared, which makes a great difference in the following passage of the proof. Apr 4, 2015 at 8:58
• @gosbi The problem of the last equality is that you forgot that square. Apr 4, 2015 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.

• Hi. Can you explain to me why $\left \| A - A_k \right \|_2 = \sigma_{k+1}$ ? I'll appreciate Nov 27, 2020 at 15:56

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$. Oct 18, 2016 at 5:43