Skip to content
Tutorials Center
My learning

Topics

Lesson 48 of 62 ยท Eigenvalues and Decompositions

Low-Rank Approximation and Image Compression

Use the truncated SVD to build the best rank-k approximation of a matrix, understand the Eckart-Young idea, and compress and denoise a generated image.

A matrix with a million entries often does not contain a million entries' worth of information. Neighbouring pixels in a photo look alike, ratings in a table follow a few tastes, and measurements share a handful of underlying causes. When that happens, a matrix is close to one of low rank, and you can store or process a much smaller version without losing much.

The SVD tells you exactly how to do it. Sort the singular values from large to small, keep the first k, and throw away the rest. This lesson explains why that is the best possible choice, shows how to measure the error and the savings, and then applies it to a generated image so you can see the effect. The same trick drives recommender systems, latent semantic analysis and noise removal.

Truncated SVD in three moves

Decompose A = U Sigma V^T.
Truncate Keep only the top k singular values.
Rebuild A_k = U_k Sigma_k V_k^T.

A_k has rank k and is the closest such matrix to A.

1 / 2

Truncating the SVD

Write the SVD as a sum of rank-one layers. If u_i is column i of U and v_i^T is row i of Vt, then

A = s1 u1 v1^T + s2 u2 v2^T + ... + sr ur vr^T

Each layer is an outer product, a rank-one matrix, scaled by its singular value. Because the singular values are sorted, the first layers are the most important. The rank-k approximation keeps just the first k layers:

A_k = s1 u1 v1^T + ... + sk uk vk^T

In NumPy, with the compact SVD, that is U[:, :k] @ np.diag(S[:k]) @ Vt[:k], or shorter (U[:, :k] * S[:k]) @ Vt[:k].

The Eckart-Young idea

How good is A_k? The Eckart-Young theorem says it is the best you can do: among all matrices of rank at most k, no matrix is closer to A than A_k, whether you measure the distance with the Frobenius norm (square root of the sum of squared entries) or with the 2-norm (largest stretch). The distances are also easy to read off the singular values:

  • Frobenius error: sqrt(s_{k+1}^2 + s_{k+2}^2 + ...), the root of the sum of the dropped squares.
  • 2-norm error: s_{k+1}, the first singular value you dropped.

So the singular values are not just ingredients; they are an error budget that you can read before you throw anything away.

Python Checking the error formulas

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both columns of numbers agree with the formulas, and none of the 500 competitors beats the truncated SVD. (Eckart-Young is a theorem, so this is an illustration rather than a proof.)

Compressing a generated image

A grayscale image is a matrix of brightness values, so low-rank approximation is a compression method. A rank-k version of an m x n image needs only the first k columns of U, the first k singular values and the first k rows of Vt, which is k * (m + n + 1) numbers instead of m * n. The saving is large when k is small compared with the image size.

The next example builds a 96 x 96 test picture with plain NumPy, so no file is needed: a smooth gradient, a bright disc and a few stripes. Smooth areas are exactly what low rank captures cheaply.

Python The same image at different ranks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The program prints the full rank of this picture: it is exactly 10, because the gradient, the disc and the stripes are each built from a few simple patterns. Rank 1 is a single outer product, so every row of that picture is a multiple of one pattern, yet it already captures the broad brightness. By rank 10 the rebuilt picture equals the original, while storing 1,930 numbers instead of 9,216. A real photo has no exact low rank and needs a larger k, but the principle is the same.

Error versus rank

How do you choose k? Plot or print the cumulative share of the "energy", the squared singular values. The fraction sum(S[:k]**2) / sum(S**2) is the proportion of the matrix's squared size that the first k layers capture. It is the same quantity as the explained variance in PCA. A common rule is to keep the smallest k that reaches 95 or 99 percent.

Python Choosing k from the singular values

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the shape of the curve. The singular values fall steeply (56, 8.6, 5.1, ...) and drop to rounding-error size after the tenth, because this picture has rank 10. That "elbow" is the signature of data with a few strong patterns, and it is what makes compression possible. A matrix of pure random noise would have a flat spectrum, and low-rank approximation would not help it at all.

Noise removal

The tail of small singular values is where unstructured noise lives, because noise has no preferred direction and spreads its energy evenly over all layers. Keeping the top k layers therefore smooths the noise away, while keeping the structure. This is called truncated SVD denoising.

Python Removing noise with a low-rank approximation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The relative error versus the clean image is smallest at rank 2, the true rank of the clean picture (about 0.07, against 0.29 for the noisy image itself), and it grows again as you keep more layers, because the extra layers add noise back in. Choosing k is a trade-off: too low blurs real detail, too high keeps noise.

The SVD of a large matrix can be expensive. For huge matrices you rarely need all singular values, so libraries offer partial or randomized SVDs (for example scipy.sparse.linalg.svds or scikit-learn's TruncatedSVD) that compute only the top k directly.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How do you form the best rank-k approximation of A from its SVD?

    A_k = U[:, :k] @ diag(S[:k]) @ Vt[:k]. By the Eckart-Young theorem nothing of rank k is closer to A.
  2. 2. A is 100 x 200 and you keep k = 10 singular values. How many numbers must you store?

    You store 10 columns of U (100 each), 10 singular values and 10 rows of Vt (200 each): k(m + n + 1).
  3. 3. The singular values of A are 9, 4, 2, 1. What is the Frobenius error of the best rank-2 approximation?

    The Frobenius error is the square root of the sum of the squares of the dropped singular values: sqrt(4 + 1).
  4. 4. Why does truncating the SVD often remove noise?

    Unstructured noise has no dominant direction, so its energy lies in the long tail of small singular values that truncation discards.

Summary

  • The SVD writes a matrix as a sum of rank-one layers s_i u_i v_i^T, sorted by importance.
  • Keeping the top k layers gives A_k, the closest rank-k matrix (Eckart-Young). Its Frobenius error is the root of the sum of the dropped s_i^2; its 2-norm error is s_{k+1}.
  • A rank-k approximation of an m x n matrix stores k(m + n + 1) numbers instead of m * n.
  • Choose k from the singular value curve or the cumulative energy cumsum(S**2) / sum(S**2).
  • Truncation also removes noise, because noise fills the many small singular values.

Next, see why computers sometimes get linear algebra wrong in Numerical Linear Algebra Pitfalls.