Truncated singular values give the best Frobenius rank-k approximation

By [F1], write $A={\sum }_{j=1}^r{\sigma }_j{u}_j{v}_j^T$ for its $r$ positive singular values, and set $A_k={\sum }_{j=1}^{\min (k,r)}{\sigma }_j{u}_j{v}_j^T$. Its image lies in the span of at most $k$ left singular vectors, so its rank is at most $k$. The residual is the sum of the positive singular terms with index greater than $k$; padding the singular-value list by zeros, [F2]–[F3] give $\mathrm{\parallel }A-A_k{\mathrm{\parallel }}_F^2={\sum }_{j>k}{\sigma }_j^2$.

Let $P$ be the orthogonal projection onto the row space of $B$, which exists by [F4]. Its rank is at most $k$, every row of $B$ lies in $\mathrm{ran}P$, and hence $B=BP$. Rowwise, $A-B=A(I-P)+(AP-B)$, where the first summand has each row in $\mathrm{ran}(I-P)$ and the second has each row in $\mathrm{ran}P$. These subspaces are orthogonal, so summing the rowwise Pythagorean identities gives $\mathrm{\parallel }A-B{\mathrm{\parallel }}_F^2\ge \mathrm{\parallel }A(I-P){\mathrm{\parallel }}_F^2=\mathrm{\parallel }A{\mathrm{\parallel }}_F^2-\mathrm{\parallel }AP{\mathrm{\parallel }}_F^2$.

Let $v_1,\dots ,v_r$ be the right singular vectors for the positive singular values, and complete them to an orthonormal basis $v_1,\dots ,v_n$ of ${\mathbb{R}}^n$ using vectors in $\ker A$; set ${\sigma }_j=0$ for $j>r$. The SVD gives $AP={\sum }_{j=1}^r{\sigma }_j{u}_j(P{v}_j{)}^T$, so orthonormality of $u_1,\dots ,u_r$ and [F2] give $\mathrm{\parallel }AP{\mathrm{\parallel }}_F^2={\sum }_{j=1}^n{\sigma }_j^2{b}_j$, where $b_j=\mathrm{\parallel }P{v}_j{\mathrm{\parallel }}_2^2\in [0,1]$. If $w_1,\dots ,w_s$ is an orthonormal basis of $\mathrm{ran}P$, then Parseval in the basis $v_1,\dots ,v_n$ gives ${\sum }_j{b}_j={\sum }_{\mathrm{\ell }=1}^s{\sum }_j\mathrm{\mid }⟨v_j,w_{\mathrm{\ell }}⟩{\mathrm{\mid }}^2=s=\mathrm{rank}P\le k$. For $k=0$, every $b_j=0$. For $k\ge 1$, put ${\lambda }_j={\sigma }_j^2$ and use ${\lambda }_j\ge {\lambda }_k$ for $j\le k$ and ${\lambda }_j\le {\lambda }_k$ for $j>k$ to obtain ${\sum }_{j=1}^k{\lambda }_j-{\sum }_{j=1}^n{\lambda }_j{b}_j={\sum }_{j=1}^k{\lambda }_j(1-b_j)-{\sum }_{j=k+1}^n{\lambda }_j{b}_j\ge {\lambda }_k(k-{\sum }_{j=1}^n{b}_j)\ge 0.$ Thus $\mathrm{\parallel }AP{\mathrm{\parallel }}_F^2\le {\sum }_{j\le k}{\sigma }_j^2$ in either case.

Substitute the bound from step 1.3 into step 1.2 and use $\mathrm{\parallel }A{\mathrm{\parallel }}_F^2={\sum }_j{\sigma }_j^2$ from [F3]. This gives $\mathrm{\parallel }A-B{\mathrm{\parallel }}_F^2\ge {\sum }_{j>k}{\sigma }_j^2=\mathrm{\parallel }A-A_k{\mathrm{\parallel }}_F^2$, proving the claim.