11 - Best Rank-𝑟 Approximation Theorem

Best Rank- $r$ Approximation Theorem

Let $r\le n$ be an integer

For any $Bin{\mathbb{C}}^{m\times n}$ with $\mathrm{rank}(B)\le r$ then

$$||A-A_r|{|}_2={\sigma }_{r+1}\le ||A-B|{|}_2$$

So truncated SVD $A_r$ is the best rank-$r$ approximant to $A$ in spectral norm

Proof

As

$$A=A_r=\sum _{i=r+1}^n{\sigma }_i{u}_i{v}_i^T$$

with singular values ${\sigma }_{r+1},\cdots ,{\sigma }_n$ along with $r$ $0$s then

$$||A-A_r|{|}_2={\sigma }_{r+1}$$

As $\mathrm{rank}(B)\le r$ then $B=B_1{B}_2^T$ where $B_1,B_2$ have $r$ columns
Hence exists orthonormal null space $W\in {\mathbb{C}}^{n\times (n-r)}$ such that $BW=0$

Then

$$||A-B|{|}_2\ge ||(A-B)W|{|}_2=||AW|{|}_2=||U\Sigma (V^{T}W)|{|}_2$$

As $W$ is $(n-r)$-dimensional and $[v_1,\cdots ,v_{r+1}]$ is the $(r+1)$-dimensional subspace then
Intersection of $W$ and $[v_1,\cdots ,v_{r+1}]$ has non-zero solution for

$$([W,v_1,\cdots ,v_{r+1}])\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=0$$

Let $W{x}_1$ be a solution

Let $x_1$ have unit norm so

$$||U\Sigma V^{T}W{x}_1|{|}_2=||\Sigma V^{T}W{x}_1|{|}_2=||{\Sigma }_{r+1}{y}_1|{|}_2$$

where $||y_1|{|}_2=1$

Then

$$||U{\Sigma }_{r+1}{y}_1||\ge {\sigma }_{r+1}$$