Singular Value Decomposition

Why we need something beyond eigenvalues

Eigenvalues and eigenvectors answer: “Are there directions v that A maps onto themselves up to scaling?”

• •For a square matrix A ∈ ℝ^{n×n}, we look for v ≠ 0 such that Av = λv.
• •This is powerful, but it has limitations:
• •Many matrices are not diagonalizable over ℝ.
• •Many problems involve rectangular matrices (m×n), where eigenvalues are not even defined in the usual sense.
• •Even when eigenvectors exist, they may not be orthogonal, which makes geometric and numerical reasoning harder.

SVD fixes these issues by giving an orthonormal coordinate system in the input and output spaces.

Definition

For any real matrix A ∈ ℝ^{m×n}, the Singular Value Decomposition is

A = UΣVᵀ

where:

• •U ∈ ℝ^{m×m} is orthonormal (UᵀU = Iₘ)
• •V ∈ ℝ^{n×n} is orthonormal (VᵀV = Iₙ)
• •Σ ∈ ℝ^{m×n} is diagonal (rectangular):
• •Σ_{ii} = σᵢ ≥ 0 (singular values)
• •all off-diagonal entries are 0
• •typically ordered σ₁ ≥ σ₂ ≥ … ≥ σ_r > 0, where r = rank(A)

Concretely, Σ looks like

Σ = [ diag(σ₁,…,σ_r) 0 ]

[ 0 0 ]

with the diagonal sitting in the top-left.

The “three-step” story

SVD says A can be viewed as three simple transformations composed:

1) Vᵀ: rotate/reflect input space (ℝⁿ) into a special orthonormal basis (the right singular vectors)

2) Σ: scale along coordinate axes by nonnegative factors σᵢ

3) U: rotate/reflect output space (ℝᵐ) into the standard basis

Because U and V are orthonormal, they preserve lengths and angles:

‖Vᵀx‖ = ‖x‖, ‖Uy‖ = ‖y‖.

So all stretching/squashing is completely captured by Σ.

Geometric intuition: sphere → ellipsoid

Consider the unit sphere in ℝⁿ:

S = { x ∈ ℝⁿ : ‖x‖ = 1 }.

Under A, the set A(S) is generally an ellipsoid (possibly flattened into lower dimensions). SVD explains why:

• •Vᵀ rotates the sphere (still a sphere)
• •Σ scales orthogonal axes by σᵢ (sphere becomes axis-aligned ellipsoid)
• •U rotates the ellipsoid in ℝᵐ

The singular values σᵢ are the lengths of the ellipsoid’s semi-axes.

The cast of characters

Let V = [v₁ … vₙ] and U = [u₁ … uₘ]. Then:

• •Right singular vectors: columns vᵢ of V
• •Left singular vectors: columns uᵢ of U
• •Singular values: σᵢ (diagonal entries of Σ)

And the defining relationships are:

Avᵢ = σᵢ uᵢ

Aᵀuᵢ = σᵢ vᵢ

These say: A maps orthonormal directions vᵢ to orthonormal directions uᵢ, scaled by σᵢ.

Existence (why you can trust it)

A key promise of SVD: every real matrix has an SVD.

This is not just a convenience—it is the reason SVD becomes a universal tool in numerical linear algebra, data analysis, and machine learning.

A common route to existence uses the fact that AᵀA is symmetric positive semidefinite, hence has an orthonormal eigenbasis. From that eigenbasis we build V and Σ, then define U accordingly. We’ll do this carefully in the next section.

Why start with AᵀA?

We want orthonormal directions in the input space that A treats “nicely.” AᵀA is the right object because:

• •AᵀA is always n×n (square), even if A is rectangular.
• •AᵀA is symmetric: (AᵀA)ᵀ = AᵀA.
• •AᵀA is positive semidefinite:

xᵀ(AᵀA)x = (Ax)ᵀ(Ax) = ‖Ax‖² ≥ 0.

So AᵀA has real eigenvalues and orthonormal eigenvectors.

Step 1: Eigen-decompose AᵀA

Because AᵀA is symmetric, there exists an orthonormal matrix V and diagonal Λ such that:

AᵀA = VΛVᵀ

where Λ = diag(λ₁,…,λₙ) with λᵢ ≥ 0.

Let the eigenpairs be:

(AᵀA)vᵢ = λᵢ vᵢ

with ‖vᵢ‖ = 1 and vᵢ ⟂ vⱼ for i ≠ j.

Step 2: Define singular values

Singular values are defined as

σᵢ = √λᵢ (nonnegative)

and arranged in decreasing order σ₁ ≥ σ₂ ≥ … ≥ 0.

So singular values are literally the square-roots of eigenvalues of AᵀA.

Step 3: Define left singular vectors

For any λᵢ > 0 (equivalently σᵢ > 0), define

uᵢ = (1/σᵢ) Avᵢ.

Then uᵢ is a unit vector, and distinct uᵢ are orthogonal. Let’s show the unit-length claim carefully.

Compute ‖uᵢ‖²:

‖uᵢ‖² = uᵢᵀuᵢ

= ((1/σᵢ)Avᵢ)ᵀ ((1/σᵢ)Avᵢ)

= (1/σᵢ²) vᵢᵀ AᵀA vᵢ

= (1/σᵢ²) vᵢᵀ (λᵢ vᵢ)

= (1/σᵢ²) λᵢ (vᵢᵀvᵢ)

= (1/σᵢ²) λᵢ

= (1/(√λᵢ)²) λᵢ

= 1.

So ‖uᵢ‖ = 1.

Now check orthogonality for i ≠ j (assuming σᵢ,σⱼ > 0):

uᵢᵀuⱼ

= ((1/σᵢ)Avᵢ)ᵀ ((1/σⱼ)Avⱼ)

= (1/(σᵢσⱼ)) vᵢᵀ AᵀA vⱼ

= (1/(σᵢσⱼ)) vᵢᵀ (λⱼ vⱼ)

= (λⱼ/(σᵢσⱼ)) vᵢᵀvⱼ

= 0.

Thus {uᵢ} are orthonormal over the nonzero singular values.

For the remaining columns of U (if m > r), we choose any orthonormal vectors that complete a basis of ℝᵐ. This completion is not unique.

Step 4: Assemble Σ, U, V

Let r = rank(A) = number of positive singular values.

• •Put σ₁,…,σ_r on the diagonal of Σ.
• •Let V contain the eigenvectors vᵢ of AᵀA.
• •Let U contain uᵢ = Avᵢ/σᵢ for i ≤ r, plus any orthonormal completion.

Then we can show A = UΣVᵀ.

One clean way is to check what A does to each vᵢ:

Avᵢ = σᵢ uᵢ.

Now consider the matrix UΣVᵀ applied to vᵢ:

(UΣVᵀ)vᵢ

= UΣ (Vᵀvᵢ)

= UΣ eᵢ

= U (σᵢ eᵢ)

= σᵢ uᵢ.

So A and UΣVᵀ agree on the basis vectors vᵢ, hence they are the same linear map.

What singular values mean: operator norm and energy

The largest singular value σ₁ tells you the maximum stretching factor of A:

σ₁ = max_{‖x‖=1} ‖Ax‖.

You can see this from

‖Ax‖² = xᵀAᵀAx.

For symmetric matrices, the maximum of xᵀMx over ‖x‖=1 is the largest eigenvalue. Here M = AᵀA, so the maximum is λ₁, and thus max ‖Ax‖ = √λ₁ = σ₁.

More generally, the sum of squared singular values equals the squared Frobenius norm:

‖A‖_F² = ∑_{i=1}^{r} σᵢ².

This becomes useful for measuring how much “energy” is captured by keeping only the top k singular values.

Relationship to eigenvalues (what carries over, what doesn’t)

If A is symmetric positive semidefinite, then its eigen-decomposition A = QΛQᵀ looks SVD-like.

In that case:

• •U = V = Q
• •Σ = Λ (with nonnegative eigenvalues)

But in general:

• •Eigenvalues of A can be negative or complex.
• •Singular values of A are always real and nonnegative.
• •SVD always exists over ℝ.

This is why SVD is the robust “geometric backbone” behind many algorithms.

Why a rank-1 sum matters

Matrices can be complicated globally, but rank-1 matrices are simple:

• •A rank-1 matrix has the form abᵀ.
• •It maps any x to a(bᵀx):
• •first take a dot product with b (a scalar)
• •then scale a by that scalar

So if we can write A as a sum of rank-1 pieces, we get an interpretable and computable structure.

SVD gives exactly that.

The outer-product expansion of SVD

Write the (thin) SVD using r = rank(A):

A = U_r Σ_r V_rᵀ

where:

• •U_r ∈ ℝ^{m×r} has columns u₁,…,u_r
• •V_r ∈ ℝ^{n×r} has columns v₁,…,v_r
• •Σ_r = diag(σ₁,…,σ_r)

Then:

A = ∑_{i=1}^{r} σᵢ uᵢ vᵢᵀ.

This is worth pausing on:

• •Each term σᵢ uᵢ vᵢᵀ is rank 1.
• •The singular values act like weights.
• •The left/right singular vectors give orthonormal directions on output/input sides.

Derivation (showing the work)

Start from thin SVD:

A = U_r Σ_r V_rᵀ.

Let Σ_r have diagonal entries σᵢ. We can write Σ_r as a sum of diagonal basis matrices:

Σ_r = ∑_{i=1}^{r} σᵢ (eᵢ eᵢᵀ).

Then

A = U_r (∑_{i=1}^{r} σᵢ eᵢ eᵢᵀ) V_rᵀ

= ∑_{i=1}^{r} σᵢ (U_r eᵢ) (V_r eᵢ)ᵀ

= ∑_{i=1}^{r} σᵢ uᵢ vᵢᵀ.

That’s the outer-product form.

Geometry: orthogonal directions map to orthogonal directions

The defining relation Avᵢ = σᵢ uᵢ means:

• •The input direction vᵢ (unit length) maps to the output direction uᵢ (unit length)
• •The length is scaled by σᵢ

If you take an arbitrary input vector x and express it in the V-basis:

x = ∑_{i=1}^{n} αᵢ vᵢ

where αᵢ = vᵢᵀx.

Then

Ax

= A(∑_{i} αᵢ vᵢ)

= ∑_{i} αᵢ Avᵢ

= ∑_{i} αᵢ σᵢ uᵢ.

So the components along vᵢ get scaled by σᵢ and re-expressed along uᵢ.

This is the ellipsoid story in coordinates.

Rank and null spaces through Σ

Because Σ has σ₁,…,σ_r > 0 and the rest 0:

• •rank(A) = r
• •dim(null(A)) = n − r
• •dim(null(Aᵀ)) = m − r

The right singular vectors associated with σᵢ = 0 span null(A):

If σᵢ = 0, then Avᵢ = 0.

Similarly, left singular vectors with σᵢ = 0 span null(Aᵀ).

This makes SVD a “coordinate system” where the fundamental subspaces (row space, column space, null space) become clean blocks.

Full SVD vs thin SVD (practical distinction)

You will see two common SVD shapes:

The thin SVD discards the “zero singular value” directions and keeps only what A actually uses.

Best rank-k approximation (why SVD dominates compression)

A remarkable theorem (Eckart–Young–Mirsky) says:

If you want a rank-k matrix B that best approximates A, then truncating the SVD is optimal.

Define

A_k = ∑_{i=1}^{k} σᵢ uᵢ vᵢᵀ.

Then A_k solves:

min_{rank(B)=k} ‖A − B‖_F

and also

min_{rank(B)=k} ‖A − B‖₂.

Intuition:

• •The first singular directions capture the largest stretches (largest “energy”).
• •Any rank-k matrix can only capture k independent input-output directions.
• •SVD orders directions from most to least influential.

Quantitatively, the truncation error is clean:

‖A − A_k‖_F² = ∑_{i=k+1}^{r} σᵢ²

‖A − A_k‖₂ = σ_{k+1}.

These formulas are incredibly useful in practice: they tell you exactly what you lose by compressing.

PCA connection (what SVD unlocks)

Principal Component Analysis (PCA) finds directions of maximal variance in data.

Suppose you have a centered data matrix X ∈ ℝ^{N×d}:

• •rows are data points
• •columns are features
• •“centered” means each feature has mean 0

The sample covariance is

C = (1/(N−1)) XᵀX.

PCA traditionally says: compute eigenvectors of C.

Now notice:

• •XᵀX is exactly the AᵀA object from SVD.
• •If X = UΣVᵀ, then

XᵀX = VΣᵀUᵀUΣVᵀ = V(ΣᵀΣ)Vᵀ.

Since UᵀU = I, we get an eigen-decomposition:

C = (1/(N−1)) V(ΣᵀΣ)Vᵀ.

So:

• •PCA directions (principal axes) are the right singular vectors vᵢ of X
• •PCA variances are (σᵢ²/(N−1))

This is why numerical PCA is often implemented via SVD of X directly.

Least squares and the pseudoinverse

Given an overdetermined system Ax ≈ b (m > n), the least squares solution minimizes

min_{x} ‖Ax − b‖².

SVD provides a stable way to solve it using the Moore–Penrose pseudoinverse A⁺.

If A = UΣVᵀ, then

A⁺ = V Σ⁺ Uᵀ

where Σ⁺ is formed by inverting nonzero singular values:

Σ⁺_{ii} = 1/σᵢ for i ≤ r, and 0 otherwise.

Then one least-squares solution is

x̂ = A⁺ b.

Why this is good:

• •Small singular values correspond to directions where A barely changes the output.
• •Inverting tiny σᵢ can amplify noise (ill-conditioning).
• •SVD exposes this explicitly, enabling regularization (e.g., truncated SVD or ridge regression).

Conditioning and numerical stability

The condition number (in 2-norm) of a full-rank matrix is

κ₂(A) = σ₁ / σ_n

(or σ₁/σ_r if rank-deficient).

Interpretation:

• •If κ₂(A) is large, A squashes some directions much more than others.
• •Solving Ax = b becomes sensitive to noise.

SVD makes this sensitivity visible and measurable.

A practical mental model

When you see A = UΣVᵀ, think:

• •V gives “input axes that matter”
• •Σ tells you “how much each axis matters”
• •U tells you “where those axes land in output space”

And when you truncate at k:

A ≈ A_k = U_k Σ_k V_kᵀ

you are choosing to keep only the k most influential input-output modes.

Where SVD appears (a few common places)

• •PCA / dimensionality reduction: compress features while preserving variance
• •Recommender systems: matrix factorization (low-rank structure)
• •Compression: images, embeddings, model weights
• •Signal processing: denoising via truncation
• •Machine learning: analyzing linear layers, conditioning, and rank

SVD is not just a theorem—it is a lens for understanding what a matrix does, and a toolkit for acting on that understanding.