Low-Rank Approximation and Applications

The SVD sorts a matrix into pieces by importance. Keeping the important pieces and dropping the rest is the idea behind image compression, noise removal, recommendation systems and principal component analysis.

Multiplying out $U\Sigma V^{T}$ column by column gives the outer-product form $$A = \sigma_1\mathbf{u}_1\mathbf{v}_1^{T} + \sigma_2\mathbf{u}_2\mathbf{v}_2^{T} + \cdots + \sigma_r\mathbf{u}_r\mathbf{v}_r^{T},$$ a sum of rank-1 matrices, largest first. The rank-$k$ approximation $A_k$ keeps the first $k$ terms.

Key idea

Eckart–Young. $A_k$ is the closest matrix of rank $k$ to $A$. The error is $\lVert A - A_k\rVert = \sigma_{k+1}$ (largest stretch) and $\lVert A - A_k\rVert_F$ $= \sqrt{\sigma_{k+1}^{2} + \cdots + \sigma_r^{2}}$ (square root of the sum of squared entries).

Why it works

Why is dropping the small terms the right move? The Frobenius norm satisfies $\lVert A\rVert_F^{2} = \sigma_1^{2} + \cdots + \sigma_r^{2}$, because orthogonal matrices do not change it and $\Sigma$ holds the rest. So each term carries "energy" $\sigma_i^{2}$, and the leftover $A - A_k$ is itself an SVD with the dropped singular values. Proving that no other rank-$k$ matrix does better takes more work, but the energy count shows why the largest terms matter most.

A 40 × 40 picture is a matrix. Its rank-$k$ approximation keeps the $k$ largest terms $\sigma_i\mathbf{u}_i\mathbf{v}_i^{T}$. The bars show the singular values; green ones are kept.

Worked example: Storage for an image

A grayscale photo is a $400 \times 600$ matrix. How many numbers does its rank-20 approximation need, compared with the full image?

Each term needs $\sigma_i$ (1 number), $\mathbf{u}_i$ (400 numbers) and $\mathbf{v}_i$ (600 numbers): $1001$ numbers.
Twenty terms: $20 \times 1001 = 20{,}020$ numbers.
The full image has $400 \times 600 = 240{,}000$, so the approximation uses about $8.3\%$ of the storage.

Answer: $20{,}020$ numbers

Worked example: A rank-1 approximation

$A = U\Sigma V^{T}$ with $\mathbf{u}_1 = \left(\frac{3}{5}, \frac{4}{5}\right)$, $\mathbf{v}_1 = \left(\frac{4}{5}, \frac{3}{5}\right)$, $\sigma_1 = 10$ and $\sigma_2 = 1$. Find $A_1$ and its error.

$\mathbf{u}_1\mathbf{v}_1^{T}$ $= \begin{bmatrix} \frac{3}{5} \\ \frac{4}{5} \end{bmatrix}\begin{bmatrix} \frac{4}{5} & \frac{3}{5} \end{bmatrix}$ $= \begin{bmatrix} \frac{12}{25} & \frac{9}{25} \\ \frac{16}{25} & \frac{12}{25} \end{bmatrix}$.
$A_1$ $= 10\,\mathbf{u}_1\mathbf{v}_1^{T}$ $= \begin{bmatrix} \frac{24}{5} & \frac{18}{5} \\ \frac{32}{5} & \frac{24}{5} \end{bmatrix}$.
Error: $\lVert A - A_1\rVert = \sigma_2 = 1$, small compared with $\sigma_1 = 10$.

Answer: $A_1 = \begin{bmatrix} \frac{24}{5} & \frac{18}{5} \\ \frac{32}{5} & \frac{24}{5} \end{bmatrix}$, error $1$

Worked example: How much is kept?

A matrix has singular values $8, 4, 2, 1$. What fraction of $\lVert A\rVert_F^{2}$ does $A_2$ keep?

Total: $64 + 16 + 4 + 1 = 85$. Kept: $64 + 16 = 80$.
Fraction: $\frac{80}{85} = \frac{16}{17} \approx 94\%$, using half the terms.

Answer: $\frac{16}{17}$

Principal component analysis: center a data matrix (rows = people, columns = measurements). Its right singular vectors are the directions of greatest spread, and $\sigma_i^{2}$ measures the spread along each.
Noise reduction: noise spreads over many small singular values; truncating removes much of it.
Least squares: the pseudoinverse $A^{+} = V\Sigma^{+}U^{T}$ gives the least-squares solution of smallest length, even when the columns are dependent.

Common mistake

Expecting the error to be the sum of the dropped singular values. In the operator norm it is the first dropped value, $\sigma_{k+1}$; in the Frobenius norm it is the square root of the sum of their squares.

Low-Rank Approximation and Applications

Practice

Builds on

Leads to

Sources and further reading