Singular Value Decomposition

Every matrix, however ugly, is a rotation then a stretch then another rotation. Step through the three and watch it happen.

Overview

What every matrix does

Take the unit circle and apply any 2×2 matrix. The result is always an ellipse. Not sometimes — always, for every matrix there is.

That is a strong claim, and the SVD is the reason it holds. Every matrix can be written as three operations in sequence:

A  =  U  Sigma  V'

Read right to left, which is the order they apply:

V' rotates. A rotation does nothing to a circle, which is why stage 2 in the visualisation looks identical to stage 1 — but watch the two spokes, which do move. It is choosing which directions are about to be stretched.

Sigma stretches along the axes, by the singular values. This is where the circle becomes an ellipse.

U rotates the ellipse into its final orientation.

Step through the four stages above and the claim stops being abstract. Whatever you set the four matrix entries to, the shape at stage 3 is an axis-aligned ellipse, every time.

Singular Value Decomposition

This module needs JavaScript: the numbers are computed in the page rather than recorded.

Worth knowing

Any matrix factors as A = U Σ V': rotate, stretch along the axes, rotate again.
The singular values in Σ are the stretch factors, always non-negative and always in descending order.
Unlike eigenvectors, an SVD exists for every matrix — non-square ones included.
The condition number is the largest singular value divided by the smallest. Large means the matrix is near-singular.

Singular Value Decomposition

The factorisation that works on every matrix, and the one worth knowing if you only learn one.

The singular values

They are the lengths of the ellipse's semi-axes, always non-negative, and conventionally listed largest first.

The largest is how much the matrix can stretch any vector — its gain in the worst case.

The smallest is how much it can squash one.

Their ratio is the condition number, and it is the single most useful number in the readout. A condition number near 1 means the matrix treats all directions roughly alike. A large one means it nearly flattens some direction, and solving anything involving that matrix will amplify error along it. Drag the entries until the two singular values are far apart and watch the ellipse become a sliver.

A zero singular value means the matrix genuinely flattens a direction: the ellipse degenerates to a line segment, the matrix is singular, and it has no inverse.

Why not eigenvectors

The [eigendecomposition](eigenvalues_and_eigenvectors.html) is the more famous factorisation, and the SVD is the more useful one, for three reasons.

It always exists. Eigendecomposition requires a square matrix, and even then not every square matrix has one. The SVD exists for every matrix of every shape, including a 1000×3.

Its bases are orthonormal. Eigenvectors need not be perpendicular, and when they are nearly parallel the decomposition is numerically fragile. U and V are [orthonormal](basis_span_and_orthogonality.html) by construction.

Its values are real and non-negative. Eigenvalues of a real matrix can be complex. Singular values never are.

For a symmetric positive-definite matrix the two coincide, which is why they are so often confused.

Low-rank approximation

The property that makes the SVD indispensable: keep only the largest *k* singular values, set the rest to zero, and multiply back. The result is provably the best rank-*k* approximation of the original matrix, in the least-squares sense. Not a good one — the best.

That single fact underwrites a surprising amount:

PCA is the SVD of the mean-centred data matrix. The principal components are the right singular vectors and the explained variances are the squared singular values, which is why any PCA implementation you look inside is calling an SVD.

Image compression keeps the top singular values of the pixel matrix.

Latent semantic analysis factors a term-document matrix and reads the retained dimensions as topics.

Recommender systems factor a sparse user-item matrix into a low-rank product.

Noise reduction works on the assumption that signal concentrates in the large singular values and noise spreads through the small ones.

Where it goes wrong

Forgetting to centre before PCA. Without subtracting the mean, the first component points at the mean rather than at the direction of greatest variance.

Reading a condition number as an error. It is a sensitivity: it says how much input error can be amplified, not how much has been.

Assuming singular values are eigenvalues. They are the eigenvalues of A'A, square-rooted. Not the same object, and not equal except in special cases.

Computing the full SVD when you want the top few. For a large sparse matrix a truncated solver is orders of magnitude cheaper.

Check yourself

0 of 3

Answer without scrolling back up.

  1. What shape does the unit circle become under any 2x2 matrix?

  2. What does a large condition number tell you?

  3. Why is the SVD preferred over an eigendecomposition?

Cheat sheet

Singular Value Decomposition

V' rotates. A rotation does nothing to a circle, which is why stage 2 in the visualisation looks identical to stage 1 — but watch the two spokes, which do move. It is choosing which directions are about to be stretched.

MATHS · vizlearn.in/maths/singular_value_decomposition.html

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.