Eckart-Young Theorem

A singular Value Decomposition is defined as a factorisation of a given matrix $D\in\mathbb{R}^{n\times d}$ into three matrices:

$D=L\Delta R^T$

One can discard the singular vectors that correspond to zero singular values, to obtain the reduced SVD:
$D=L_r\Delta_r R_r^T=\sum^r_{i=1}\delta_i\pmb{l}_i\pmb{r}_i^T$

Eckart-Young Theorem:

If $D_r$ is the matrix defined as $\sum^r_{i=1}\delta_i\pmb{l}_i\pmb{r}_i^T$ , then $D_r$ is the rank-r matrix that minimises the objective $\Vert D-D_r\Vert_F$ .

The Frobenius Norm of a matrix A, $\Vert A\Vert_F$ , is defined as

$\Vert A\Vert_F=\sqrt{\sum^n_{i=1}\sum^n_{j=1}A_{i,j}^2}$

Proof:

Assume D is of rank k(k>r).

Since $\Vert D-D_r\Vert_F=\Vert L\Delta R^T-D_r\Vert_F=\Vert\Delta-L^TD_rR\Vert_F$ .

Denoting $N=L^TD_rR$ , we can compute the Frobenius norm as

$\Vert\Delta-N\Vert^2_F=\sum_{i,j}\vert \Delta_{i,j}-N_{i,j}\vert^2=\sum^k_{i=1}\vert\delta_i-N_{i,i}\vert^2+\sum_{I>k}\vert N_{i,i}\vert^2+\sum_{I\neq j}\vert N_{i,j}\vert^2$

This is minimised if all off-diagonal terms of N and all $N_{i,i}$ for I>k are zero. The minimum of $\sum\vert\delta_i-N_{i,i}\vert^2 is obtained for$ latex N_{i,i} =\delta_i $ for i=1,…,r and all other $N_{i,i}$ are zero.