Proof of Eckart-Young-Mirsky theorem

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$.

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.