Eckart-Young-Mirsky theorem

定理：

(The Eckhart-Young Theorem) If $k<r=rank(A)$ and
$$A_k=\sum _{i=1}^k{\sigma }_i{\mu }_i{\nu }_i^{\top }$$
then
$$\underset{rank(B)=k}{\min }||A-B|{|}_2=||A-A_k|{|}_2={\sigma }_{k+1}$$

证明：
Since $U^{\top }{A}_{k}V=diag({\sigma }_1,\cdots ,{\sigma }_k,0,\cdots ,0)$ it follows that $A_k$ is rank k. Moreover, $U^{\top }(A-A_k)V=diag(0,\cdots ,0,{\sigma }_{k+1},\cdots ,{\sigma }_p)$ and so $||A-A_k|{|}_2={\sigma }_{k+1}$.
Now suppose $rank(B)=k$ for some $B\in {\mathbb{R}}^{m\times n}$. It follows that we can find orthonormal vectors $x_1,...,x_{n-k}$ so n u l l ( B ) = s p a n { x 1 , . . . , x n − k } null (B) = span\{x_1 , ... , x_{n-k}\} null(B)=span{x1​,...,xn−k​}· A dimension argument shows that
span { x 1 , ⋯   , x n − k } ∩ span { v 1 , ⋯   , v k + 1 } ≠ { 0 } . \text{span}\{x_1,\cdots,x_{n-k}\}\cap\text{span}\{v_1,\cdots,v_{k+1}\}\neq\{0\}. span{x1​,⋯,xn−k​}∩span{v1​,⋯,vk+1​}​={0}.
Let z be a unit 2-norm vector in this intersection. Since $Bz=0$ and
$$Az=\sum _{i=1}^{k+1}{\sigma }_i(v_i^{\top }z)u_i,$$
we have
$$||A-B|{|}_2^2\ge ||(A-B)z|{|}_2^2=||Az|{|}_2^2=\sum _{i=1}^{k+1}{\sigma }_i^2(v_i^{\top }z{)}^2\ge {\sigma }_{k+1}^2$$
completing the proof of the theorem.