Topic 8 of 8

Singular value decomposition

Step 19 · Linear algebra topics

Write any matrix as a turn, a stretch and another turn, find its singular values, and use the largest ones to approximate the matrix with far less data.

Singular values

Every matrix A sends the unit circle (or sphere) to an ellipse. The lengths of the ellipse's semi-axes are the singular values σ₁ ≥ σ₂ ≥ … ≥ 0. They are the square roots of the eigenvalues of AᵀA.

Example: A diagonal matrix

Find the singular values of $\begin{pmatrix} 3 & 0 \\ 0 & -2 \end{pmatrix}$ .

AᵀA has diagonal entries 9 and 4.
Take square roots.

Answer3 and 2: the signs do not matter

Example: A squashing matrix

Find the singular values of $\begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix}$ .

AᵀA = $\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$ , with eigenvalues 2 and 0.
Take square roots.

Answer√2 and 0

The matrix with rows (2, 1) and (1, 2) turns the unit circle into an ellipse with semi-axes 3 and 1: its singular values.

The decomposition

A = U\Sigma V^{T}

Every matrix can be written as A = UΣVᵀ. Vᵀ turns the input (a rotation, perhaps with a reflection), Σ stretches along the axes by the singular values, and U turns the result. The columns of U and V are orthonormal.

Example: Reading the pieces

A = UΣVᵀ, and Σ has diagonal 5 and 2. What does A do to v₁, the first column of V?

Vᵀ sends v₁ to ⟨1, 0⟩.
Σ stretches that to ⟨5, 0⟩, and U turns it into 5u₁.

AnswerAv₁ = 5u₁

Example: Rank

A 4 × 3 matrix has singular values 6, 2 and 0. What is its rank?

The rank is the number of singular values that are not 0.

Answer2

Low-rank approximation

A matrix is a sum of rank-one pieces, σ₁u₁v₁ᵀ + σ₂u₂v₂ᵀ + … Keeping only the k largest pieces gives the best approximation of rank k, and its error is set by the first singular value left out.

Example: Compressing an image

A 1000 × 1000 grayscale image is a matrix. Keeping 50 singular values, how many numbers are stored?

Each piece needs a u (1000 numbers), a v (1000 numbers) and a σ.
50 × 2001 = 100,050.

AnswerAbout 100,000: a tenth of the original million

Example: How good is it?

A matrix has singular values 10, 4, 0.1 and 0.05. How good is a rank-2 approximation?

The largest singular value left out is 0.1, tiny next to 10 and 4.
So the rank-2 version is almost exactly A.

AnswerVery good: its error is at most about 0.1 in size

Try it yourself

Work each one on paper first, then open the answer to check.

Find the singular values of $\begin{pmatrix} 4 & 0 \\ 0 & 1 \end{pmatrix}$ .
Show answer
4 and 1
Find the singular values of $\begin{pmatrix} 0 & 2 \\ -3 & 0 \end{pmatrix}$ .
Show answer
3 and 2
A matrix has singular values 7, 3, 0 and 0. What is its rank?
Show answer
2
In A = UΣVᵀ, which factor stretches?
Show answer
Σ
What is the best rank-1 approximation of A, in terms of its SVD?
Show answer
σ₁u₁v₁ᵀ
AᵀA has eigenvalues 16 and 9. What are the singular values of A?
Show answer
4 and 3