Low-rank approximation

Keeping the part of a matrix that matters

The SVD writes a matrix as a sum of rank-one layers, $A=\sum_i\sigma_i\mathbf u_i\mathbf v_i^{T}$, ordered from the biggest layer to the smallest. Keeping only the first $k$ layers gives $A_k=U_k\Sigma_kV_k^{T}$, a matrix of rank $k$. The Eckart-Young theorem says this truncation is the best rank-$k$ approximation there is, whether error is measured by the Frobenius norm or by the spectral norm. No clever choice of $k$ directions can beat the top $k$ singular directions.

The error is exactly the discarded singular values, so the share of squared size you keep is $\sum_{i\le k}\sigma_i^2\big/\sum_i\sigma_i^2$, often called the explained variance when $A$ is centred data. A rank-$k$ approximation of an $m\times n$ matrix needs only $k(m+n+1)$ numbers instead of $mn$, which is why low rank is also compression. In finance, the layers with small $\sigma_i$ are mostly sampling noise, so truncating them is denoising, and the number to keep is usually chosen by a threshold on the kept share or by a gap in the singular values.

• Eckart-Young: truncating the SVD at $k$ terms is the best rank-$k$ approximation in both norms.
• Error: Frobenius $\sqrt{\sum_{i>k}\sigma_i^2}$, spectral $\sigma_{k+1}$.
• Storage: $k(m+n+1)$ numbers instead of $mn$.

Lab · what's graded

• The Frobenius error15 pts
• The share kept15 pts
• A rank-one approximation15 pts
• Storage of a low-rank matrix10 pts
• The Eckart-Young theorem15 pts
• Compressing a matrix15 pts
• Why truncation denoises15 pts