Interactive demo · Probabilistic Machine Learning · Chapter 7

Truncated SVD: low-rank approximation of an image

A greyscale image is a \(200\times320\) matrix \(\mathbf A\) of pixel values. Its singular value decomposition \(\mathbf A=\sum_k\sigma_k\mathbf u_k\mathbf v_k^{\mathsf T}\) writes it as a sum of rank-one layers in order of importance; keeping the first \(K\) gives the best rank-\(K\) approximation \(\hat{\mathbf A}_K\) (the Eckart–Young theorem), stored with \(K(200+320+1)\) numbers instead of 64,000. Because the singular values of a natural image fall quickly, a small \(K\) already looks right. Shuffle the pixels and the structure disappears: the spectrum flattens and no small rank is good. The SVD is computed in your browser, from the eigenvectors of \(\mathbf A\mathbf A^{\mathsf T}\).

Image

Pixels

Rank K

Right-hand picture

Computing the SVD…

Try these

The residual picture shows \(\mathbf A-\hat{\mathbf A}_K\), mid-grey for zero. The bottom panel marks \(\sigma_{K+1}\), which is also the spectral-norm error \(\|\mathbf A-\hat{\mathbf A}_K\|_2\). Stand-in image: a photograph bundled with scikit-learn (the book uses a different one).

In the lecture notes