SVD and the Eckart–Young Theorem
The singular value decomposition (SVD) factors any matrix into a rotation, a stretch, and another rotation. But its real power is the Eckart–Young theorem: discarding the smallest stretches gives the provably best compressed approximation of the original matrix.
The SVD and its pieces
For any real matrix of rank :
- — left singular vectors; orthonormal columns; eigenvectors of
- — singular values,
- — right singular vectors; orthonormal columns; eigenvectors of
Each , because , which is exactly the eigendecomposition of with eigenvalues . and are orthogonal, so and .
SVD as a sum of rank-1 layers
Expanding column by column gives a sum of rank-1 outer products:
Each term is a rank-1 matrix — the simplest possible structure ( numbers times numbers). The singular value says how much of lives in that layer. Because the are sorted, the first few layers carry most of the information.
Rank- truncation and its savings
Drop all but the first layers:
where , keep only the first columns and .
Storage trade-off. A rank- approximation of an matrix stores numbers instead of . For a 512×512 image with : vs — about compression.
The Eckart–Young guarantee
Theorem. Among all rank- matrices , the truncated SVD minimizes the Frobenius norm of the approximation error:
and the minimum error is exactly the discarded tail:
Why. The Frobenius norm satisfies (sum of squared singular values). Among all rank- matrices, the one closest to in Frobenius norm must retain the largest singular values unchanged and zero out the rest. Any other rank- matrix would keep some smaller while discarding a larger one, increasing the sum of dropped terms. keeps exactly the top-. It is the unique minimizer.
Verifying the error formula numerically
import numpy as np
rng = np.random.default_rng(0)
A = rng.normal(size=(60, 40)) @ rng.normal(size=(40, 40)) # full-rank 60x40 matrix
U, s, Vt = np.linalg.svd(A, full_matrices=False)
print(f"{'k':>4} {'actual error':>14} {'theory (tail)':>14} {'match':>6}")
for k in [1, 5, 10, 20, 30]:
A_k = U[:, :k] @ np.diag(s[:k]) @ Vt[:k, :]
actual = np.linalg.norm(A - A_k, "fro")
theory = np.sqrt((s[k:] ** 2).sum())
print(f"{k:>4} {actual:>14.6f} {theory:>14.6f} {np.isclose(actual, theory)!s:>6}")
All rows print True — the error formula is exact.
Low-rank approximation in practice
| Application | How is used |
|---|---|
| Image compression | Keep top singular values; store instead of the full pixel matrix |
| Recommender systems | Approximate a sparse user×item ratings matrix; the layers become latent "taste dimensions" |
| LoRA fine-tuning | Represent each weight update as with low-rank ; reduces parameters from to |
| Noise filtering | Small noise; truncating denoises: same logic as dropping low-variance PCA components |
Reading the singular-value spectrum
The scree plot
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 is the true number of underlying factors. A completely flat spectrum means no compression is lossless: the matrix genuinely uses all its dimensions.
import matplotlib.pyplot as plt
fig, axes = plt.subplots(1, 2, figsize=(10, 4))
# Low-rank + noise: elbow is visible
rng2 = np.random.default_rng(1)
A_lr = rng2.normal(size=(50, 5)) @ rng2.normal(size=(5, 50)) # true rank 5
A_lr += 0.5 * rng2.normal(size=(50, 50)) # noise
s_lr = np.linalg.svd(A_lr, compute_uv=False)
axes[0].plot(s_lr, marker='o', ms=4)
axes[0].set_title("Effectively low-rank: elbow at k=5")
axes[0].set_xlabel("Index i")
axes[0].set_ylabel("σᵢ")
# Full-rank: no clear elbow
s_full = np.linalg.svd(A, compute_uv=False)
axes[1].plot(s_full, marker='o', ms=4)
axes[1].set_title("Full-rank: no clear elbow")
axes[1].set_xlabel("Index i")
plt.tight_layout()
plt.show()
Related concepts
- SVD & Low-Rank Approximation: the full lesson with the rotate→stretch→rotate geometric view and PCA connection
- Computing Eigenvalues & Eigenvectors: the eigenvector problem that generates and
- PCA in Practice: choosing rank from the scree plot, reconstruction error