Low-rank approximation

How many simple pieces does a picture need? Watch a photo rebuilt from 1, 2, 4, 8, 16 and 32 of them.

A picture is a matrix

A greyscale picture is a table of brightness values, one per pixel, so it is a matrix. The picture at the top is $128\times128$: 16 384 numbers. By The singular value decomposition, it is a sum of rank-one pieces,

with the singular values in decreasing order. Each piece $\mathbf{u}\mathbf{v}^\top$ is a column times a row. Every row of it is a multiple of the same row $\mathbf{v}^\top$, and every column a multiple of the same column $\mathbf{u}$. As a picture, one piece is a plaid: horizontal bands times vertical bands. That is why the first frame of the clip looks like a plaid, not blurred in the usual way.

Keep the largest pieces

Keep only the first $k$ pieces:

Here the subscript counts the pieces kept: $\mathbf{A}_k$ is not the power $\mathbf{A}^k$, and not a column of $\mathbf{A}$. The matrix $\mathbf{A}_k$ has rank $k$. And no matrix of rank $k$ is closer to $\mathbf{A}$. This is the Eckart–Young theorem. The error is exactly what was dropped, measured two ways:

• the largest stretch of the error is the first singular value left out, $\lVert\mathbf{A}-\mathbf{A}_k\rVert_2=\sigma_{k+1}$;
• the sum of the squared entries of the error is the sum of the squares left out, $\lVert\mathbf{A}-\mathbf{A}_k\rVert_\mathrm{F}^2=\sigma_{k+1}^2+\sigma_{k+2}^2+\cdots$

The share of the total kept is $(\sigma_1^2+\dots+\sigma_k^2)/(\sigma_1^2+\sigma_2^2+\cdots)$. In the bar chart of the picture, a few tall bars carry most of it.

A small example

Here is a $3\times3$ matrix whose pieces have whole-number singular values:

with $\mathbf{u}_1=\tfrac13(1,2,2)$, $\mathbf{u}_2=\tfrac13(2,1,-2)$, $\mathbf{u}_3=\tfrac13(2,-2,1)$ and $\mathbf{v}_1=\tfrac13(2,2,1)$, $\mathbf{v}_2=\tfrac13(2,-1,-2)$, $\mathbf{v}_3=\tfrac13(1,-2,2)$. Both sets are orthonormal. Check one pair: $\mathbf{N}\mathbf{v}_1=\tfrac13(32-4-1,\;28+28-2,\;10+28+16)=(9,18,18)=27\,\mathbf{u}_1$.

One piece. $\mathbf{N}_1=\begin{bmatrix}6&6&3\\12&12&6\\12&12&6\end{bmatrix}$: every row is a multiple of $(2,2,1)$. The squared entries of $\mathbf{N}$ add up to $1134=27^2+18^2+9^2$, and $\mathbf{N}_1$ keeps $729/1134=64.3\,\%$ of that. Its error has largest stretch 18 and Frobenius size $\sqrt{18^2+9^2}=\sqrt{405}=20.12$.

Two pieces. $\mathbf{N}_2=\begin{bmatrix}14&2&-5\\16&10&2\\4&16&14\end{bmatrix}$ keeps $1053/1134=92.9\,\%$, and its error is the last piece alone:

with Frobenius size 9.

Counting the numbers

A piece $\sigma\,\mathbf{u}\mathbf{v}^\top$ of an $m\times n$ matrix needs $m+n+1$ numbers: the column, the row and the scale. So $\mathbf{A}_k$ needs $k(m+n+1)$, against $mn$ for the whole matrix.

• The $128\times128$ picture: $257k$ numbers against 16 384. It saves space only while $k<63.75$; at $k=64$ it stores 16 448, more than the picture.
• A $512\times512$ picture has 262 144 numbers. Rank 20 needs $20\times1025=20\,500$, which is 7.8 % of them.

So low rank pays when a few pieces carry most of the picture, as they do for smooth scenes, and not for pure noise.

Limits of low rank

Real image formats do not use the SVD. A JPEG file uses the cosine transform of The discrete cosine transform, a fixed basis that needs no pieces to be stored and costs far less to compute. Low rank is a model: it works when the data really are made of a few patterns, as a ratings table or a set of similar signals often are.

Worked example

1. The pieces of $\mathbf{N}$. Singular values 27, 18 and 9, with the vectors above.

2. Best rank one. $\mathbf{N}_1$ keeps 64.3 % of the squared size; its error is 18 in largest stretch and 20.12 in Frobenius size, which is 0.598 of the whole, $\sqrt{1134}$.

3. Best rank two. $\mathbf{N}_2$ keeps 92.9 %; its error is $9\,\mathbf{u}_3\mathbf{v}_3^\top$, 9 in both measures, 0.267 of the whole.

4. Storage. Rank 20 of a $512\times512$ picture stores 20 500 numbers, 7.8 %; break-even is near $k=256$.

Try these before you read the answers.

• What is the rank of a column times a row, $\mathbf{u}\mathbf{v}^\top$? 1.
• A picture whose rows are all equal: how many singular values are not zero? One.
• The largest-stretch error of the best rank-two approximation of $\mathbf{N}$? $\sigma_3=9$.

Where you’ll meet this

Denoising. Measurements of a few true patterns plus noise give a matrix with a few large singular values and many small ones. Keeping the large pieces and dropping the rest removes much of the noise.

Recommendations. A table of ratings, people by items, is close to low rank: tastes come in a few kinds. The best low-rank fit fills in the missing ratings.

Fast filters. A two-dimensional Gaussian blur kernel aligned with the image’s axes is a column times a row, so blurring costs two short passes, not one long one. A Gaussian stretched along a slant is not rank one.

Reference card