13.3 Low-Rank Approximation

Eckart-Young-Minsky Theorem

A general matrix $A\in {\mathbb{R}}^{m\times n}$ with rank $r\le \min \{m,n\}$ can be approximated by a lower-rank matrix $A_k$ with rank $1\le k\le r$, such that $A_k$ is the best rank-$k$ approximation to $A$,
$A_k=\arg \underset{A_k\in {\mathbb{R}}^{m\times n}}{\min }\Vert A-A_k{\Vert }_F^2.$
We may then approximate our matrix $A$ using singular value decomposition as
$A_k={\sum }_{i=1}^k{\sigma }_i{\vec{u}}_i{\vec{v}}_i^T=U_k{\Sigma }_k{V}_k^T.$

Intuition

Essentially, the above definition states that $A_l$ is found inside the set of matrices $B$ that minimize the square of the Frobenius norm of $A-B$ (in other words $A\approx B$). This holds mostly if the data is real, and therefore has some linear, low-rank structure with some singular values being large, and some very small. Then, we can equivalently say that the first $l$ ordered singular values are large, and the remaining $r-l$ are small:
${\sum }_{i=1}^r{\sigma }_i{\vec{u}}_i{\vec{v}}_i^T={\sum }_{i=1}^l{\sigma }_i{\vec{u}}_i{\vec{v}}_i^T+{\sum }_{i=l+1}^r\underset{\approx 0}{\underbrace{{\sigma }_i}}{\vec{u}}_i{\vec{v}}_i^T={\sum }_{i=1}^l{\sigma }_i{\vec{u}}_i{\vec{v}}_i^T.$