3.4 The singular value decomposition and PCA

Every matrix, of any shape, is a rotation, then a stretch along the axes, then another rotation. The stretch factors (singular values) measure how much each direction matters, which gives the best low-rank approximation of a matrix and the principal components of a data set.

The spectral theorem (3.1) is wonderful but only covers symmetric matrices. Most matrices in practice are not symmetric, and many are not even square: a data table with 10,000 rows and 50 columns, an image of 1080 by 1920 pixels, a neural-network layer mapping 768 numbers to 3072. The singular value decomposition says every one of them, without exception, is a rotation followed by a stretch along perpendicular axes followed by another rotation. The stretch factors tell you which directions matter, and throwing away the small ones is the best possible compression.

Before you start

Chapters 3.1 (spectral theorem), 3.2 (positive semidefinite) and 3.3 (orthogonal matrices).

Quick checkFor any matrix

A

, what kind of matrix is

A^{\mathsf T}A

Quick checkAn orthogonal matrix

Q

does what to the length of a vector?

The picture

Press Next three times. Move 1 ( $V^{\mathsf T}$ ) turns the circle so that two special perpendicular directions $v_1, v_2$ line up with the axes; a circle stays a circle. Move 2 ( $\Sigma$ ) stretches along the axes by $\sigma_1$ and $\sigma_2$ , making an ellipse. Move 3 ( $U$ ) turns the ellipse into its final position. The result is exactly what $A$ does to the circle. Try “Rank one”: $\sigma_2 = 0$ and the ellipse collapses to a segment.

Where this came from· Discovered twice, computed a century later

Eugenio Beltrami (1873) and Camille Jordan (1874) independently found the decomposition while studying bilinear forms, which are the expressions $x^{\mathsf T}Ay$ with two different vectors. Erhard Schmidt proved the matching approximation result for integral operators in 1907. Carl Eckart and Gale Young proved it for matrices in 1936, in the journal Psychometrika, where such approximations were wanted for test-score data. Principal component analysis has a separate history: Karl Pearson (1901) fitted lines and planes to data, and Harold Hotelling (1933) named it. A practical way to compute the SVD came only in the 1960s, from Gene Golub and William Kahan. Their idea of reducing the matrix to a simpler bidiagonal form first is still the first stage of the routines behind NumPy’s svd.

Definitions and the theorem

Definition B

Singular value

The singular values of a real $m \times n$ matrix $A$ are $\sigma_i = \sqrt{\lambda_i}$ , where $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n \ge 0$ are the eigenvalues of the symmetric positive semidefinite matrix $A^{\mathsf T}A$ . (Positive semidefinite was shown in 3.2: $x^{\mathsf T}A^{\mathsf T}Ax = \lVert Ax \rVert^2 \ge 0$ , so no $\lambda_i$ is negative and the square roots exist. If $m < n$ then $\operatorname{rank} A \le m$ , so at most $m$ of the $\sigma_i$ are non-zero.)

In one lineThe singular values of A are the square roots of the eigenvalues of AᵀA, listed from largest to smallest: the stretch factors of A.

Why it existsThey measure how much A stretches each of a set of perpendicular directions, which is what 'the size of A in each direction' should mean.

Definition B

Singular value decomposition

A singular value decomposition of $A$ is a factorisation $A = U\Sigma V^{\mathsf T}$ where $U$ is an $m \times m$ orthogonal matrix, $V$ is an $n \times n$ orthogonal matrix, and $\Sigma$ is $m \times n$ with the singular values $\sigma_1 \ge \sigma_2 \ge \dots \ge 0$ on its diagonal and zeros elsewhere. The columns $v_i$ of $V$ are the right singular vectors and the columns $u_i$ of $U$ the left singular vectors, with

Av_i = \sigma_i u_i.

In one lineA = UΣVᵀ with U (m×m) and V (n×n) orthogonal and Σ (m×n) diagonal with σ₁ ≥ σ₂ ≥ … ≥ 0.

Why it existsIt describes any matrix as rotate, stretch along axes, rotate, and exposes its rank, its four subspaces and its best approximations.

Theorem B Strang 7.2; Trefethen–Bau Thm 4.1

Every matrix has an SVD

Every real $m \times n$ matrix $A$ has a singular value decomposition.

In one lineEvery real m×n matrix has a singular value decomposition A = UΣVᵀ.

Why it is trueDiagonalize the symmetric AᵀA to get V; then the vectors Avᵢ are automatically perpendicular, and dividing by their lengths gives U.

Why· The picture behind the proof

Look for perpendicular inputs whose outputs are also perpendicular. Those inputs are the eigenvectors of $A^{\mathsf T}A$ : their images under $A$ come out perpendicular “for free”, because $(Av_i)\cdot(Av_j) = v_i \cdot (A^{\mathsf T}Av_j)$ , and $A^{\mathsf T}A$ only rescales $v_j$ . The lengths of the images are the singular values, and the image directions are the $u_i$ .

ProofStrang 7.2

The idea: Apply the spectral theorem to AᵀA: orthonormal eigenvectors v_i, eigenvalues λ_i = σ_i² ≥ 0. For σ_i > 0 set u_i = Av_i/σ_i; these are orthonormal. Extend to an orthonormal basis of ℝ^m. Then AV = UΣ.

Let

v_1, \dots, v_n

be orthonormal eigenvectors of

A^{\mathsf T}A

with eigenvalues

\lambda_1 \ge \dots \ge \lambda_n \ge 0

. Set

\sigma_i = \sqrt{\lambda_i}

A^{\mathsf T}A

is symmetric, so the spectral theorem (3.1) gives an orthonormal eigenbasis; its eigenvalues are

\ge 0

because it is positive semidefinite (3.2).

(Av_i)\cdot(Av_j) = v_i \cdot (A^{\mathsf T}Av_j) = \lambda_j\, v_i \cdot v_j

, which is

\sigma_j^2

i = j

and 0 otherwise.

Move

A

across the dot product with the transpose, then use the eigenvector equation and orthonormality.

Let

r

be the number of

\sigma_i > 0

. For

i \le r

set

u_i = \frac{Av_i}{\sigma_i}

. By the previous line these are orthonormal.

So the images are perpendicular, and

\lVert Av_i \rVert = \sigma_i

Extend

u_1, \dots, u_r

to an orthonormal basis

u_1, \dots, u_m

\mathbb R^m

Any orthonormal set in

\mathbb R^m

extends to an orthonormal basis (extend to a basis, 2.2, then Gram–Schmidt, 2.9).

Av_i = \sigma_i u_i

for every

i \le r

and

Av_i = O

for

i > r

, which in matrix form is

AV = U\Sigma

For

i \le r

Av_i = \sigma_i u_i

by definition. For

i > r

\lVert Av_i \rVert = \sigma_i = 0

, so

Av_i = O

. (If

m < n

, there is no

u_i

for

i > m

, but then

\sigma_i = 0

and the column of

\Sigma

is zero anyway.)

A = U\Sigma V^{\mathsf T}

\blacksquare

V

is orthogonal, so

V^{-1} = V^{\mathsf T}

Worked example

Compute an SVD of

A = \begin{bmatrix}3&0\\4&5\end{bmatrix}

Solution. The method is: form $A^{\mathsf T}A$ , diagonalize it, then get each $u_i$ by applying $A$ . The step-through below shows each stage.

Answer. $A = U\Sigma V^{\mathsf T}$ with $\sigma_1 = 3\sqrt5$ , $\sigma_2 = \sqrt5$ , $U = \frac1{\sqrt{10}}\begin{bmatrix}1&-3\\3&1\end{bmatrix}$ and $V^{\mathsf T} = \frac1{\sqrt2}\begin{bmatrix}1&1\\-1&1\end{bmatrix}$ .

Your answerFor

A = \begin{bmatrix}3&0\\4&5\end{bmatrix}

, what is

\sigma_2

squared? (It is an eigenvalue of

A^{\mathsf T}A = \begin{bmatrix}25&20\\20&25\end{bmatrix}

Worked example

Find the singular values and the rank of

\begin{bmatrix}1&2\\2&4\end{bmatrix}

, and of the symmetric matrix

\begin{bmatrix}2&0\\0&-3\end{bmatrix}

Solution.

First matrix: form $A^{\mathsf T}A$ . $A^{\mathsf T}A = \begin{bmatrix}1+4 & 2+8\\ 2+8 & 4+16\end{bmatrix} = \begin{bmatrix}5&10\\10&20\end{bmatrix}$ . Entry $(i,j)$ is column $i$ dotted with column $j$ .
Its eigenvalues. Trace $25$ , determinant $100 - 100 = 0$ , so $\lambda = 25, 0$ . For a $2 \times 2$ matrix the eigenvalues have sum equal to the trace and product equal to the determinant.
Singular values and rank. $\sigma = 5, 0$ , so the rank is 1. Rank is the number of non-zero singular values. The second column is twice the first, so rank 1 agrees.
Second matrix. $A^{\mathsf T}A = \operatorname{diag}(4, 9)$ , so the singular values are $3$ and $2$ (largest first). Singular values are square roots, never negative. The eigenvalues of $A$ are $2$ and $-3$ , so $|\lambda_i|$ is what we see here.
Where did the minus sign go? The right singular vector for $\sigma_1 = 3$ is $v_1 = e_2$ , and for $\sigma_2 = 2$ it is $v_2 = e_1$ . Then $u_1 = Av_1/3 = (0, -3)/3 = (0, -1)$ and $u_2 = Av_2/2 = (1, 0)$ . Apply $A$ and divide by the singular value, as in the proof. The minus sign lands in $u_1$ .
Check the product. $U = \begin{bmatrix}0&1\\-1&0\end{bmatrix}$ , $\Sigma = \operatorname{diag}(3, 2)$ , $V^{\mathsf T} = \begin{bmatrix}0&1\\1&0\end{bmatrix}$ give $U\Sigma V^{\mathsf T} = \begin{bmatrix}0&2\\-3&0\end{bmatrix}\begin{bmatrix}0&1\\1&0\end{bmatrix} = \begin{bmatrix}2&0\\0&-3\end{bmatrix}$ . Multiplying back is the check that the factorization is right.

Answer. First matrix: $\sigma = 5, 0$ , rank 1. Second matrix: $\sigma = 3, 2$ . For a symmetric matrix, $\sigma_i = |\lambda_i|$ , and the signs of negative eigenvalues move into $U$ .

Your answerThe singular values of

\begin{bmatrix}2&0\\0&-3\end{bmatrix}

: what is

\sigma_1

, the largest?

Quick checkHow is rank read off the SVD?

Worked example

Prove: the largest stretch of

A

, namely

\max_{\lVert x \rVert = 1}\lVert Ax \rVert

, equals

\sigma_1

. Test it on

\begin{bmatrix}3&0\\4&5\end{bmatrix}

Solution.

Square the length. $\lVert Ax \rVert^2 = (Ax)^{\mathsf T}(Ax) = x^{\mathsf T}(A^{\mathsf T}A)x$ . This turns the question into a quadratic form of the symmetric matrix $A^{\mathsf T}A$ (3.2).
Use the eigenbasis. Write $x = \sum c_iv_i$ with $\sum c_i^2 = 1$ . Then $x^{\mathsf T}A^{\mathsf T}Ax = \sum \lambda_ic_i^2$ . The $v_i$ are orthonormal eigenvectors of $A^{\mathsf T}A$ , so the cross terms vanish (3.1).
Bound it. $\sum\lambda_ic_i^2 \le \lambda_1\sum c_i^2 = \lambda_1$ , with equality at $x = v_1$ . $\lambda_1$ is the largest eigenvalue.
Take square roots. $\max\lVert Ax \rVert = \sqrt{\lambda_1} = \sigma_1$ . Square root is increasing.
Test. For $A = \begin{bmatrix}3&0\\4&5\end{bmatrix}$ , $x = v_1 = \frac1{\sqrt2}(1, 1)$ gives $Ax = \frac1{\sqrt2}(3, 9)$ of length $\sqrt{45} = 3\sqrt5 \approx 6.71$ . The longest output from a unit input.

Answer. $\max_{\lVert x \rVert = 1}\lVert Ax \rVert = \sigma_1$ , attained at $v_1$ . $\blacksquare$ This number is called the operator norm of $A$ (3.5).

Worked example

Prove: for a square matrix

A

|\det A| = \sigma_1\sigma_2\cdots\sigma_n

. Test on

\begin{bmatrix}3&0\\4&5\end{bmatrix}

Solution.

Take determinants of the SVD. $\det A = \det U\cdot\det\Sigma\cdot\det V^{\mathsf T}$ . Product rule for determinants (2.7).
Evaluate each factor. $\det U = \pm1$ and $\det V^{\mathsf T} = \pm1$ , and $\det\Sigma = \sigma_1\cdots\sigma_n$ since $\Sigma$ is diagonal. Orthogonal matrices have determinant $\pm1$ (3.3), and a diagonal determinant is the product of the diagonal.
Absolute value. $|\det A| = \sigma_1\cdots\sigma_n$ . The signs disappear, and the $\sigma_i$ are non-negative.
Test. $\det\begin{bmatrix}3&0\\4&5\end{bmatrix} = 15$ and $\sigma_1\sigma_2 = 3\sqrt5\cdot\sqrt5 = 15$ . Matches the step-through above.

Answer. $|\det A| = \prod\sigma_i$ . $\blacksquare$ Rotations keep area, so all the area change comes from the stretches.

Quick checkWhy is a singular value of a matrix never negative, even when

A

has a negative eigenvalue?

The SVD as a sum: low-rank approximation

Multiplying out $U\Sigma V^{\mathsf T}$ column by row gives

A = \sigma_1 u_1 v_1^{\mathsf T} + \sigma_2 u_2 v_2^{\mathsf T} + \dots + \sigma_r u_r v_r^{\mathsf T}.

Each $u_i v_i^{\mathsf T}$ is a rank-1 matrix (every row a multiple of $v_i^{\mathsf T}$ ). The SVD writes $A$ as a sum of rank-1 pieces, in decreasing order of importance $\sigma_i$ .

Definition B

Low-rank approximation

For $k < r$ , the rank- $k$ truncation of $A$ is $A_k = \sum_{i=1}^k \sigma_i u_i v_i^{\mathsf T}$ .

In one lineKeep the first k terms of the SVD sum: A_k = σ₁u₁v₁ᵀ + … + σ_k u_k v_kᵀ, a rank-k matrix close to A.

Why it existsIt compresses A to k(m + n + 1) numbers while keeping as much of A as any rank-k matrix can.

Theorem B Eckart and Young 1936; Trefethen–Bau Thm 5.8

Eckart–Young theorem

For every matrix $B$ of rank at most $k$ , $\lVert A - B \rVert \ge \sigma_{k+1} = \lVert A - A_k \rVert$ , where $\lVert M \rVert = \max_{\lVert x \rVert = 1}\lVert Mx \rVert$ is the largest stretch of $M$ (the operator norm, 3.5). In the Frobenius norm (square root of the sum of squared entries) the same $A_k$ is best, with error $\sqrt{\sigma_{k+1}^2 + \dots + \sigma_r^2}$ . (We prove the operator-norm version below. The Frobenius version has a longer proof, in Trefethen–Bau.)

In one lineThe truncated SVD A_k is the best rank-k approximation of A; its error is the first discarded singular value σ_{k+1} (in the operator norm).

Why it is trueAny rank-k matrix kills some direction in the span of v₁, …, v_{k+1}, and A stretches every vector of that span by at least σ_{k+1}.

ProofTrefethen–Bau 5.8

The idea: (Operator norm.) B has rank ≤ k, so its null space has dimension ≥ n − k and must meet the (k + 1)-dimensional span of v₁, …, v_{k+1}. Pick a unit vector w there: Bw = O, and ‖Aw‖ ≥ σ_{k+1}.

\dim N(B) \ge n - k

Rank–nullity (2.3).

N(B)

and

W = \operatorname{span}(v_1, \dots, v_{k+1})

have dimensions adding to at least

n + 1

, so there is a unit vector

w \in N(B) \cap W

Two subspaces of

\mathbb R^n

with dimensions adding to more than

n

share a non-zero vector (the

\dim(U + W)

formula, 2.2).

\lVert Aw \rVert^2 = \sum_{i \le k+1} c_i^2\sigma_i^2 \ge \sigma_{k+1}^2

Write

w = \sum_{i \le k+1} c_i v_i

with

\sum c_i^2 = 1

; then

Aw = \sum c_i\sigma_i u_i

and the

u_i

are orthonormal.

\lVert A - B \rVert \ge \lVert (A - B)w \rVert = \lVert Aw \rVert \ge \sigma_{k+1}

Bw = O

, so

(A - B)w = Aw

And

\lVert A - A_k \rVert = \sigma_{k+1}

, so

A_k

achieves the bound.

\blacksquare

A - A_k = \sum_{i > k}\sigma_i u_i v_i^{\mathsf T}

is itself an SVD with largest singular value

\sigma_{k+1}

, and the largest stretch of a matrix is its largest singular value (the worked example above).

Proof workshopRebuild the Eckart–Young argument (operator norm)

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

Worked example Strang 7.2 style

Find the SVD of the wide matrix

A = \begin{bmatrix}3&2&2\\2&3&-2\end{bmatrix}

using

AA^{\mathsf T}

, then give its best rank-1 approximation and the error.

Solution.

Choose the small product. $A$ is $2 \times 3$ , so $AA^{\mathsf T}$ is $2 \times 2$ while $A^{\mathsf T}A$ is $3 \times 3$ . We work with $AA^{\mathsf T} = \begin{bmatrix}17&8\\8&17\end{bmatrix}$ . Its non-zero eigenvalues are the same $\sigma_i^2$ as those of $A^{\mathsf T}A$ : if $A^{\mathsf T}Av = \lambda v$ with $\lambda \ne 0$ , then $Av \ne O$ and $AA^{\mathsf T}(Av) = A(A^{\mathsf T}Av) = \lambda(Av)$ . And it is smaller.
Eigenvalues. $17 \pm 8 = 25, 9$ , so $\sigma_1 = 5$ , $\sigma_2 = 3$ . Same pattern $a \pm b$ as before.
Left singular vectors. Eigenvectors of $AA^{\mathsf T}$ : $u_1 = \frac1{\sqrt2}(1, 1)$ for 25 and $u_2 = \frac1{\sqrt2}(1, -1)$ for 9. The $u_i$ are the orthonormal eigenvectors of $AA^{\mathsf T}$ .
Right singular vectors. $v_i = A^{\mathsf T}u_i/\sigma_i$ : $v_1 = \frac1{\sqrt2}(1, 1, 0)$ and $v_2 = \frac1{3\sqrt2}(1, -1, 4)$ . From $Av_i = \sigma_iu_i$ we get $A^{\mathsf T}u_i = \sigma_iv_i$ . Check: $\lVert(1, -1, 4)\rVert = \sqrt{18} = 3\sqrt2$ , so $v_2$ is a unit vector.
Best rank-1 approximation. $A_1 = \sigma_1u_1v_1^{\mathsf T} = 5\cdot\frac1{\sqrt2}\frac1{\sqrt2}\begin{bmatrix}1\\1\end{bmatrix}\begin{bmatrix}1&1&0\end{bmatrix} = \frac52\begin{bmatrix}1&1&0\\1&1&0\end{bmatrix}$ . Keep the term with the largest singular value.
Error. $\lVert A - A_1 \rVert = \sigma_2 = 3$ in the operator norm. Eckart–Young: the error is the first discarded singular value. Check: $A - A_1 = \begin{bmatrix}0.5&-0.5&2\\-0.5&0.5&-2\end{bmatrix}$ equals $\sigma_2u_2v_2^{\mathsf T}$ .

Answer. $\sigma = 5, 3$ . $A_1 = \frac52\begin{bmatrix}1&1&0\\1&1&0\end{bmatrix}$ , with error $3$ . There is no third $u$ , because a $2 \times 3$ matrix has at most 2 non-zero singular values. The third right singular vector $v_3 = \frac13(2, -2, -1)$ spans the null space of $A$ .

Your answerFor

A = \begin{bmatrix}3&2&2\\2&3&-2\end{bmatrix}

, the best rank-1 approximation has operator-norm error equal to

\sigma_2

. What is it?

Worked example

Compress a 1000 by 1000 greyscale image to rank 50. How much storage is saved, and what decides the quality?

Solution.

Count the full image. $1000 \times 1000 = 10^6$ numbers. One brightness value per pixel.
Count the rank-50 version. Each term $\sigma_i u_i v_i^{\mathsf T}$ needs $u_i$ (1000 numbers), $v_i$ (1000) and $\sigma_i$ (1): 2001 numbers. For 50 terms: $100{,}050$ . Store the factors, not the product.
Ratio. $100{,}050 / 10^6 \approx 10\%$ of the storage. About a tenfold saving.
Quality. By Eckart–Young no rank-50 image is closer, and the error is governed by $\sigma_{51}, \sigma_{52}, \dots$ . Many photos have quickly decaying singular values (smooth regions are nearly low rank), so rank 50 can look close to the original, though fine texture is lost first. The theorem gives the best possible; the data decides how good “best” is.

Answer. About 10% of the numbers, with the smallest possible error for that budget. (JPEG uses a fixed cosine basis instead, 2.2, because it is cheaper to compute; the SVD adapts its basis to each image.)

Python labTruncate the SVD of a small synthetic image

import numpy as np

x = np.linspace(0, 1, 40)
rng = np.random.default_rng(0)
# a smooth 40 by 40 "image": two rank-1 patterns plus a little noise
img = 5 * np.outer(np.sin(np.pi * x), np.cos(3 * x)) + 3 * np.outer(x, x**2)
img = img + 0.05 * rng.standard_normal((40, 40))

U, s, Vt = np.linalg.svd(img)
print("first singular values:", np.round(s[:5], 3))
for k in (1, 2, 3, 5):
    Ak = (U[:, :k] * s[:k]) @ Vt[:k]
    err = np.linalg.norm(img - Ak, 2)
    print(f"k={k}: error = {err:.4f}   next sigma = {s[k]:.4f}   numbers stored = {k*(40+40+1)} of 1600")

Try this. Run it and compare each error with the 'next sigma' printed beside it: they match, as Eckart–Young says. The picture is built from two rank-1 patterns plus noise, so the error collapses at $k = 2$ and then barely moves. Change the noise level 0.05 to 0.5 and watch the singular values from the third onward grow: that tail is the noise, and truncation throws it away.

Your answerHow many numbers store a rank-

k

approximation of an

m \times n

matrix? Give the answer for

m = 768

n = 768

k = 8

(a LoRA-style update).

Principal component analysis

Definition B

Principal component analysis

Let $X$ be an $N \times d$ data matrix (one row per sample, one column per feature) with each column’s mean subtracted (centered). The principal components are the right singular vectors $v_1, v_2, \dots$ of $X$ . The variance of the data along $v_i$ is $\frac{\sigma_i^2}{N - 1}$ , and $v_1$ is the direction of greatest variance.

In one lineCenter the data, take the SVD of the data matrix; the right singular vectors are the directions of greatest variance, in decreasing order.

Why it existsIt finds the few directions that carry most of the variation in high-dimensional data, so the data can be seen, compressed or denoised.

Why· Why the singular vectors are the directions of greatest variance

The variance of the data along a unit vector $w$ is $\frac{1}{N - 1}\sum_j (x_j \cdot w)^2 = \frac{1}{N - 1}\lVert Xw \rVert^2 = \frac{1}{N - 1}w^{\mathsf T}(X^{\mathsf T}X)w$ . That is a quadratic form in $w$ with the symmetric matrix $X^{\mathsf T}X$ (the covariance matrix up to the factor $\frac1{N-1}$ ). By the Rayleigh-quotient problem of 3.1, its maximum over unit $w$ is the largest eigenvalue of $X^{\mathsf T}X$ , which is $\sigma_1^2$ , at $w = v_1$ . The next direction, perpendicular to $v_1$ , is $v_2$ , and so on.

Worked example

Find the first principal component of the four points

(2, 1), (-2, -1), (1, 2), (-1, -2)

Solution.

Center. The mean is $(0, 0)$ already. PCA measures spread around the mean, so the mean must be subtracted first.
Form $X^{\mathsf T}X$ . $X^{\mathsf T}X = \begin{bmatrix}4+4+1+1 & 2+2+2+2\\ 8 & 1+1+4+4\end{bmatrix} = \begin{bmatrix}10&8\\8&10\end{bmatrix}$ . Entry $(i, j)$ is the sum over points of (coordinate $i$ ) times (coordinate $j$ ).
Eigenvectors. Eigenvalues $18$ and $2$ , with eigenvectors $(1, 1)$ and $(1, -1)$ . Same pattern as 3.1’s $\begin{bmatrix}2&1\\1&2\end{bmatrix}$ .
Read off. $v_1 = \frac1{\sqrt2}(1, 1)$ carries variance $\frac{18}{3} = 6$ ; $v_2$ carries $\frac23$ . Variance along $v_i$ is $\sigma_i^2/(N - 1)$ with $N = 4$ .

Answer. The points spread mostly along the diagonal $y = x$ : 90% of the total variance ( $\frac{18}{18 + 2}$ ) lies along $v_1$ . Projecting onto $v_1$ alone keeps 90% of the information in one number per point.

Your answerIn the four-point example the eigenvalues of

X^{\mathsf T}X

are 18 and 2. What fraction of the total variance lies along the first principal component? Give a decimal.

Quick checkThe shear

\begin{bmatrix}1&1\\0&1\end{bmatrix}

has eigenvalues

1, 1

. What are its singular values?

Quick checkWhy must you center the data before PCA?

Proof workshopGive the reason for each line: why the images Avᵢ are perpendicular

Each line of the proof is shown in order. Choose the reason that justifies it, then press Check.

$(Av_i)\cdot(Av_j) = v_i \cdot (A^{\mathsf T}Av_j)$
$= v_i \cdot (\lambda_j v_j)$
$= \lambda_j\,(v_i \cdot v_j)$
$= 0$ when $i \ne j$

Where it is used

Used inside maths· Inside maths: the four subspaces, the pseudoinverse, conditioning

The SVD hands you orthonormal bases of all four fundamental subspaces (2.6): $u_1..u_r$ for the column space, $v_{r+1}..v_n$ for the null space, and so on. It gives the least squares solution even when columns are dependent (the pseudoinverse $A^+ = V\Sigma^+U^{\mathsf T}$ ). And $\sigma_1/\sigma_r$ is the condition number of 3.5, which says how badly a system amplifies errors.

Used in the real world· Data and AI: recommendations, genes, and language models

In the Netflix Prize (2006 to 2009), the leading teams modelled the huge users-by-films ratings matrix as approximately low rank, a few “taste” directions explaining most ratings, and fitted SVD-like factorisations. In population genetics, the first two principal components of genetic data from Europeans reproduce a recognisable map of Europe (Novembre and colleagues, Nature, 2008). In language models, the LoRA paper (Hu and colleagues, 2021) hypothesised that the change in a weight matrix during fine-tuning has low rank, so it trains two thin factors $B$ and $A$ with $\Delta W = BA$ instead of the full matrix, and found that small ranks perform competitively.

Traps

Watch out· Singular values are not eigenvalues

For non-symmetric $A$ , the singular values are the square roots of the eigenvalues of $A^{\mathsf T}A$ , not the eigenvalues of $A$ . The shear $\begin{bmatrix}1&1\\0&1\end{bmatrix}$ has eigenvalues $1, 1$ but singular values about $1.618$ and $0.618$ .

Watch out· Computing the SVD by forming AᵀA is fine by hand, risky in floating point

Forming $A^{\mathsf T}A$ squares the condition number (3.5), so small singular values get lost to rounding. Library routines (Golub–Kahan) work on $A$ directly. Use np.linalg.svd(A), never np.linalg.eig(A.T @ A), for real data.

Problems

check

Find the singular values of $\begin{bmatrix}1&1\\0&0\end{bmatrix}$ and its rank.

Solution

$A^{\mathsf T}A = \begin{bmatrix}1&1\\1&1\end{bmatrix}$ with eigenvalues $2, 0$ , so $\sigma = \sqrt2, 0$ . Rank 1.

check

For a symmetric positive definite matrix, how are its SVD and its spectral decomposition related?

Solution

They coincide: $A = Q\Lambda Q^{\mathsf T}$ is already an SVD with $U = V = Q$ and $\Sigma = \Lambda$ (all $\lambda_i > 0$ ). For symmetric matrices with negative eigenvalues, $\sigma_i = |\lambda_i|$ and the signs move into $U$ .

useStrang 7.2 style

Compute an SVD of $\begin{bmatrix}1&1\\0&0\end{bmatrix}$ .

Solution

$v_1 = \frac1{\sqrt2}(1, 1)$ , $v_2 = \frac1{\sqrt2}(1, -1)$ ; $\sigma_1 = \sqrt2$ , $\sigma_2 = 0$ . $u_1 = Av_1/\sigma_1 = (1, 0)$ ; extend with $u_2 = (0, 1)$ . $A = \begin{bmatrix}1&0\\0&1\end{bmatrix}\begin{bmatrix}\sqrt2&0\\0&0\end{bmatrix}\frac1{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix}$ .

use

Give the best rank-1 approximation of the $\begin{bmatrix}3&0\\4&5\end{bmatrix}$ from the step-through, and its error in the operator norm.

Solution

$A_1 = \sigma_1 u_1 v_1^{\mathsf T} = 3\sqrt5 \cdot \frac1{\sqrt{10}}(1, 3)^{\mathsf T}\frac1{\sqrt2}(1, 1) = \frac{3}{2}\begin{bmatrix}1&1\\3&3\end{bmatrix}$ . Error $\sigma_2 = \sqrt5 \approx 2.24$ .

prove

Prove that $\sigma_1 = \max_{\lVert x \rVert = 1}\lVert Ax \rVert$ .

Solution

$\lVert Ax \rVert^2 = x^{\mathsf T}A^{\mathsf T}Ax$ , a quadratic form whose maximum over unit $x$ is the largest eigenvalue of $A^{\mathsf T}A$ , which is $\sigma_1^2$ (the Rayleigh problem of 3.1). Take square roots.

prove

Prove that $|\det A| = \sigma_1\sigma_2\cdots\sigma_n$ for a square $A$ .

Solution

$\det A = \det U \det\Sigma \det V^{\mathsf T} = (\pm1)\,\sigma_1\cdots\sigma_n\,(\pm1)$ , since orthogonal matrices have determinant $\pm1$ (3.3). Taking absolute values gives the claim. Geometrically: rotations keep area, so all the area change comes from the stretches.

stretch

Show that the eigenvalues of $AA^{\mathsf T}$ (an $m \times m$ matrix) are the same non-zero numbers $\sigma_i^2$ , with eigenvectors $u_i$ . Why might you compute the SVD of a wide data matrix this way?

Solution

$AA^{\mathsf T}u_i = AA^{\mathsf T}\frac{Av_i}{\sigma_i} = \frac{A(A^{\mathsf T}Av_i)}{\sigma_i} = \frac{A\sigma_i^2 v_i}{\sigma_i} = \sigma_i^2 u_i$ . For a matrix with few rows and many columns (say 100 by 1,000,000), $AA^{\mathsf T}$ is $100 \times 100$ while $A^{\mathsf T}A$ is enormous, so work with the small one and recover $v_i = A^{\mathsf T}u_i/\sigma_i$ .

Summary

SVD: every matrix is $A = U\Sigma V^{\mathsf T}$ : rotate, stretch along axes by $\sigma_1 \ge \sigma_2 \ge \dots \ge 0$ , rotate.
Build it from the spectral theorem on $A^{\mathsf T}A$ : $v_i$ its eigenvectors, $\sigma_i = \sqrt{\lambda_i}$ , $u_i = Av_i/\sigma_i$ .
Rank = number of non-zero singular values; $\sigma_1$ = the largest stretch.
$A = \sum \sigma_i u_i v_i^{\mathsf T}$ ; keeping $k$ terms gives the best rank- $k$ approximation, with error $\sigma_{k+1}$ (Eckart–Young).
PCA: center the data; the right singular vectors are the directions of greatest variance, with variance $\sigma_i^2/(N-1)$ .
Applications: compression, recommendations, genetics, low-rank fine-tuning of AI models.

Watch and read

The same ideas explained by someone else. Use these when an explanation here does not land.

3.4 The singular value decomposition and PCA

The picture

Definitions and the theorem

Singular value

Singular value decomposition

Every matrix has an SVD

The SVD as a sum: low-rank approximation

Low-rank approximation

Eckart–Young theorem

Principal component analysis

Principal component analysis

Where it is used

Traps

Problems

Summary

Watch and read

Where this sits

Comes from

Leads to

Same idea elsewhere