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)$" ?
 A: 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$.
A: 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
\begin{equation}
\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
\end{equation}
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, 
\begin{equation}
\mathrm{null}(B) \cap \mathrm{span}\{ v_1,v_2,\cdots,v_{k+1} \} \neq \{0\}
\end{equation}
So, $\exists$ a non-zero vector lying in both spaces. This'll lead to a contradiction.
A: 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
\begin{equation}
  ||\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
\end{equation}
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.
