SVD and the Eckart-Young TheoremOpen in Colab

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 m×nm \times n real matrix AA of rank rr:

A=UΣV⊤A = U \Sigma V^\top
  • U∈Rm×rU \in \mathbb{R}^{m \times r} — left singular vectors; orthonormal columns; eigenvectors of AA⊤AA^\top
  • Σ=diag(σ1,…,σr)\Sigma = \text{diag}(\sigma_1, \ldots, \sigma_r) — singular values, σ1≥σ2≥⋯≥σr>0\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_r > 0
  • V∈Rn×rV \in \mathbb{R}^{n \times r} — right singular vectors; orthonormal columns; eigenvectors of A⊤AA^\top A

Each σi=λi(A⊤A)\sigma_i = \sqrt{\lambda_i(A^\top A)}, because A⊤A=(UΣV⊤)⊤(UΣV⊤)=VΣ2V⊤A^\top A = (U\Sigma V^\top)^\top(U\Sigma V^\top) = V\Sigma^2 V^\top, which is exactly the eigendecomposition of A⊤AA^\top A with eigenvalues σi2\sigma_i^2. UU and VV are orthogonal, so U⊤U=IU^\top U = I and V⊤V=IV^\top V = I.

SVD as a sum of rank-1 layers

Expanding UΣV⊤U\Sigma V^\top column by column gives a sum of rank-1 outer products:

A=∑i=1rσi uivi⊤A = \sum_{i=1}^{r} \sigma_i \, \mathbf{u}_i \mathbf{v}_i^\top

Each term uivi⊤\mathbf{u}_i \mathbf{v}_i^\top is a rank-1 matrix — the simplest possible structure (mm numbers times nn numbers). The singular value σi\sigma_i says how much of AA lives in that layer. Because the σi\sigma_i are sorted, the first few layers carry most of the information.

Rank-kk truncation and its savings

Drop all but the first kk layers:

Ak=∑i=1kσi uivi⊤=UkΣkVk⊤A_k = \sum_{i=1}^{k} \sigma_i \, \mathbf{u}_i \mathbf{v}_i^\top = U_k \Sigma_k V_k^\top

where UkU_k, VkV_k keep only the first kk columns and Σk=diag(σ1,…,σk)\Sigma_k = \text{diag}(\sigma_1, \ldots, \sigma_k).

Storage trade-off. A rank-kk approximation of an m×nm \times n matrix stores k(m+n+1)k(m + n + 1) numbers instead of mnmn. For a 512×512 image with k=50k = 50: 50×1025=51 25050 \times 1025 = 51\,250 vs 5122=262 144512^2 = 262\,144 — about 5×5\times compression.

The Eckart–Young guarantee

Theorem. Among all rank-kk matrices BB, the truncated SVD AkA_k minimizes the Frobenius norm of the approximation error:

Ak=arg⁡min⁡rank⁡(B)≤k ∥A−B∥FA_k = \underset{\operatorname{rank}(B) \le k}{\arg\min}\, \lVert A - B \rVert_F

and the minimum error is exactly the discarded tail:

∥A−Ak∥F=∑i=k+1rσi2\lVert A - A_k \rVert_F = \sqrt{\sum_{i=k+1}^{r} \sigma_i^2}

Why. The Frobenius norm satisfies ∥A∥F2=∑iσi2\lVert A \rVert_F^2 = \sum_i \sigma_i^2 (sum of squared singular values). Among all rank-kk matrices, the one closest to AA in Frobenius norm must retain the kk largest singular values unchanged and zero out the rest. Any other rank-kk matrix would keep some smaller σi\sigma_i while discarding a larger one, increasing the sum of dropped terms. AkA_k keeps exactly the top-kk. It is the unique minimizer.

Verifying the error formula numerically

Python
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

ApplicationHow AkA_k is used
Image compressionKeep top kk singular values; store Uk,Σk,Vk⊤U_k, \Sigma_k, V_k^\top instead of the full pixel matrix
Recommender systemsApproximate a sparse user×item ratings matrix; the layers become latent "taste dimensions"
LoRA fine-tuningRepresent each weight update as ΔW=BA\Delta W = B A with low-rank B,AB, A; reduces parameters from mnmn to k(m+n)k(m+n)
Noise filteringSmall σi≈\sigma_i \approx noise; truncating denoises: same logic as dropping low-variance PCA components

Reading the singular-value spectrum

The scree plot

Plot the singular values σ1,σ2,…\sigma_1, \sigma_2, \ldots 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.

Python
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

Concept neighbourhood

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

RelatedReferenced by
SVD and the Eckart-Young TheoremComputing Eigenvalues & E…SVD & Low-Rank Approximat…PCA in Practice