SVD & Low-Rank ApproximationOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

SVD & Low-Rank Approximation

Eigendecomposition was powerful but picky: it needs a square matrix, and the nicest guarantees only arrive when the matrix is symmetric. The singular value decomposition drops every restriction. Any matrix (rectangular, rank-deficient, ugly) factors as:

A=UΣV⊤A = U \Sigma V^\top
  • V⊤V^\top — an orthogonal rotation of the input space (columns of VV = right singular vectors)
  • Σ\Sigma — a diagonal stretch by the singular values σ1≥σ2≥⋯≥0\sigma_1 \ge \sigma_2 \ge \cdots \ge 0
  • UU — an orthogonal rotation of the output space (columns = left singular vectors)

Every linear map, no matter how messy, is just rotate → stretch along perpendicular axes → rotate. The singular values are the stretch factors, and they are always real and non-negative.

Where it comes from

The matrices A⊤AA^\top A and AA⊤A A^\top are always symmetric, so the spectral theorem — which guarantees symmetric matrices always have real eigenvalues and mutually orthogonal eigenvectors — applies to them even when it doesn't apply to AA:

  • VV = eigenvectors of A⊤AA^\top A
  • UU = eigenvectors of AA⊤A A^\top
  • σi=λi\sigma_i = \sqrt{\lambda_i}, the square roots of their (shared, non-negative) eigenvalues

This is also exactly the PCA connection: for centered data XX, the covariance is 1nX⊤X\frac{1}{n}X^\top X, so the principal components are the right singular vectors of XX, and explained variances are σi2/n\sigma_i^2 / n. Numerical libraries compute PCA via SVD rather than forming the covariance matrix — it's more stable.

The sum-of-layers view and best rank-kk approximation

Rewriting A=UΣV⊤A = U\Sigma V^\top one column at a time gives a sum of rank-1 layers: A=∑iσiuivi⊤A = \sum_i \sigma_i \mathbf{u}_i\mathbf{v}_i^\top. Truncating to the first kk layers gives AkA_k, and the Eckart–Young theorem proves this is the best rank-kk approximation in Frobenius norm, with error ∑i>kσi2\sqrt{\sum_{i>k}\sigma_i^2}.

Quick numeric example. Suppose AA has singular values [10,5,0.3][10, 5, 0.3]. The full Frobenius norm is 102+52+0.32=125.09≈11.18\sqrt{10^2+5^2+0.3^2} = \sqrt{125.09} \approx 11.18. Keeping only k=2k=2 gives error 0.32=0.3\sqrt{0.3^2} = 0.3 — we captured 99.9% of the "signal" in just two layers. Keeping only k=1k=1 gives error 52+0.32=25.09≈5.01\sqrt{5^2+0.3^2} = \sqrt{25.09} \approx 5.01 — still meaningful structure, but a lot is lost. The singular value spectrum tells you at a glance where to cut.

This fact powers image compression, recommender systems, LoRA fine-tuning, and noise filtering.

Deep dive
SVD and the Eckart-Young Theorem
Includes runnable notebook
Python
import numpy as np

rng = np.random.default_rng(0)
A = rng.normal(size=(60, 40)) @ rng.normal(size=(40, 40))

U, s, Vt = np.linalg.svd(A, full_matrices=False)

k = 10
A_k = U[:, :k] @ np.diag(s[:k]) @ Vt[:k, :]
err = np.linalg.norm(A - A_k, "fro")
tail = np.sqrt((s[k:] ** 2).sum())
print(f"rank-{k} error = {err:.4f}, tail = {tail:.4f}")  # identical

Sweep the truncation rank kk below and watch the rank-kk reconstruction sharpen as the discarded singular values (and the Frobenius error ∑i>kσi2\sqrt{\sum_{i>k}\sigma_i^2}) shrink. A few layers capture almost all the signal.

Low-rank approximation: keep the biggest layers, drop the rest

original A (rank 8)
rank-2 approximation
12345678σ
Frobenius error5.171
energy captured81.4%
numbers stored80 / 400

A is rebuilt from its rank-1 layers σᵢ uᵢ vᵢᵀ, biggest singular value first. Truncating to the top k layers gives the provably best rank-k approximation (Eckart–Young), with Frobenius error √(Σ_{i>k} σᵢ²) — the height of the bars you discarded. The spectrum's steep drop then flat tail means a handful of layers carry almost all the signal.

Reading the spectrum

Plot the singular values in decreasing order. A steep drop followed by a flat noise floor means the matrix is effectively low-rank — the elbow tells you the true number of underlying factors.

Exercise

A 1000×800 matrix has singular values [95, 80, 60, 0.4, 0.3, 0.2, ...all below 0.4]. What's the best way to describe it?

Need a hint?

Where does the spectrum drop off a cliff?

Key takeaways

  • SVD factors any matrix into rotation · stretch · rotation; singular values are the stretch factors, always real and ≥ 0
  • UU, VV are eigenvectors of AA⊤AA^\top and A⊤AA^\top A; σi=λi\sigma_i = \sqrt{\lambda_i}, and PCA is the SVD of centered data
  • A=∑iσiuivi⊤A = \sum_i \sigma_i \mathbf{u}_i \mathbf{v}_i^\top: a stack of rank-1 layers, sorted by importance
  • Truncating the stack gives the provably best rank-k approximation (Eckart–Young) — the engine behind compression, recommenders, denoising, and LoRA

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

RelatedGo deeper
SVD & Low-Rank ApproximationEigenvalues and Eigenvect…Principal Component Analy…PCA in PracticeJacobians & Vector Calcul…Matrix FactorizationSVD and the Eckart-Young …