Definition
The singular value decomposition (SVD) writes any real matrix as : an orthonormal set of input directions , a list of non-negative stretch factors on the diagonal of , and an orthonormal set of output directions . Equivalently, is a sum of rank-1 layers sorted from most to least important — and cutting the sum after terms gives the best possible rank- approximation of .
At a glance
- Task
- Matrix factorization: dimensionality reduction, compression, denoising, latent factors, solving least squares
- Input → output
- a matrix → , , with (thin SVD)
- Learns
- row-space directions (e.g. "taste profiles" over movies), column-space directions (each user's coordinates), and their strengths
- Training cost
- exact: ; top- only (randomized / Lanczos): about
- Prediction cost
- projecting a new row : for ; reconstructing it: another
- Hyperparameters
- the rank kept; the solver (full LAPACK, randomized, ARPACK); whether to centre / scale columns first; the cutoff below which a is treated as 0
- Assumes
- nothing statistical — it is exact linear algebra. Using a truncated SVD as a model assumes the signal is low-rank and the noise is spread over all directions
The problem
Real data matrices are big and redundant. A users × movies ratings table, a documents × words count table, a grayscale image, a sensor array over time — each has thousands of columns, but the columns are strongly correlated: people who love Alien tend to love Star Wars. We want a factorization that (1) works for any rectangular matrix, (2) finds the few directions that carry most of the structure, (3) tells us exactly how much we lose by keeping only those, and (4) is numerically stable.
The eigendecomposition fails all four: it only exists for square matrices, may need complex numbers, its eigenvectors need not be orthogonal (so "keeping the top ones" has no clean error guarantee), and it can fail to exist at all (defective matrices). Gaussian elimination or QR tells you nothing about which directions matter. The SVD fixes all of this: it exists for every matrix, it is real, both bases are orthonormal, and its truncation is provably optimal.
The idea
Geometry. Any linear map, however messy its matrix looks, does only three things: it rotates the input (by ), stretches along the coordinate axes (by , possibly squashing some axes to zero), and rotates again into the output space (by ). Feed in the unit circle and you get an ellipse; the ellipse's semi-axes are and , and the input directions that land on them are and .
Layers. Read the same factorization as a sum: . Each term is a rank-1 matrix — a single pattern across the columns, multiplied by a single loading down the rows. For ratings, might be "overall movie popularity" and "romance minus sci-fi"; says how strongly each user expresses that pattern. The layers are sorted by , so the first few carry the bulk of the matrix and the tail is mostly noise.
Vocabulary
- Singular value σᵢ
- the -th stretch factor, , sorted descending. is the largest gain over unit vectors
- Right singular vector vᵢ
- a unit vector in the input space (a pattern over the columns); the are orthonormal and are the eigenvectors of
- Left singular vector uᵢ
- a unit vector in the output space (a loading over the rows); , the eigenvectors of
- Rank r
- the number of non-zero singular values — the true number of independent directions in
- Full / thin / truncated SVD
- full: is , is ; thin: only the columns that meet ; truncated: only the top (see Truncated SVD)
- Frobenius norm
- — total "energy" of the matrix
- Spectral norm
- — the most any unit vector can be stretched
- Energy kept
- — the fraction of that a rank- approximation retains
- Condition number
- — how much relative error in can be amplified when solving
- Pseudo-inverse A⁺
- , where inverts the non-zero — the least-squares, minimum-norm "inverse" of any matrix
The math
- the data matrix, rows (samples) × columns (features)
- , orthonormal columns: left singular vectors
- diagonal, entries
- , orthonormal columns: right singular vectors
- rank of (at most )
Where and come from. Suppose the factorization exists. Then . That is an eigendecomposition of the symmetric, positive-semidefinite matrix : its eigenvectors are the and its eigenvalues are . Run the argument backwards to construct the SVD: the spectral theorem gives orthonormal eigenvectors with eigenvalues (because ). Set .
- 1 if , else 0 — so the come out orthonormal automatically
- the defining pair of equations; also
Stacking for all gives , and multiplying by on the right gives . Every matrix therefore has an SVD. The singular values are unique; each pair is unique up to a joint sign flip (or rotation within a block if two tie).
- how long the unit vector becomes after applying
- the maximizer: the input direction stretches most
This variational view is what power iteration exploits: maximizing is a Rayleigh quotient, so repeatedly applying to a vector and normalizing converges to , at a rate set by .
A 2×2 by hand. gives , with eigenvalues and and eigenvectors , . So , , and . Checks: , and . This is the default matrix in the figure below.
Why truncation is optimal (Eckart–Young)
- the truncated SVD: keep the top layers
- the first columns of , and the top-left block of
- any matrix of rank at most — no other one does better
Why the error is the tail sum. Orthogonal matrices preserve the Frobenius norm, so . The optimality (no rank- beats it) follows from Weyl's inequality with : the residual must have singular values at least of . The same theorem holds in the spectral norm: .
The hyperparameter , mathematically. Raising by one adds one layer, lowers the squared error by exactly , and costs more stored numbers. Since the are sorted, the returns diminish monotonically — which is why you look for the point where the spectrum flattens into a noise floor.
Least squares and the pseudo-inverse
- the minimum-norm minimizer of
- the component of the target along output direction
- the gain applied to it — huge when σᵢ is tiny
This explains ill-conditioning: noise in along a direction with small gets divided by and blows up. Two cures fall straight out of the formula: truncate (drop terms with below a cutoff — "truncated SVD regression"), or damp them — ridge regression multiplies each term by the filter factor , which is about 1 for big and about 0 for small ones. Least-squares solvers such as NumPy's lstsq use exactly this SVD route.
Worked example: a tiny ratings matrix
Six users rate four movies from 1 to 5: two sci-fi films (Alien, Star Wars) and two romances (Notting Hill, Titanic). Users 1–3 prefer sci-fi, users 4–5 romance, user 6 rates everything 3. We factor the raw (uncentred) matrix, as a recommender would.
| User | Alien | Star Wars | Notting Hill | Titanic |
|---|---|---|---|---|
| u1 | 5 | 5 | 1 | 1 |
| u2 | 4 | 5 | 1 | 2 |
| u3 | 5 | 4 | 2 | 1 |
| u4 | 1 | 1 | 5 | 4 |
| u5 | 2 | 1 | 4 | 5 |
| u6 | 3 | 3 | 3 | 3 |
Factoring A by hand
- 1Gram matrix. holds the dot products between movie columns: . Its trace equals , the sum of all squared ratings.
- 2Eigenvalues of (the characteristic polynomial of a 4×4 is solved numerically): — they sum to 269. Square roots give the singular values .
- 3Right singular vectors (eigenvectors of ): — all positive, "how much you like movies at all". — negative on sci-fi, positive on romance: the genre axis.
- 4Left singular vectors . For : , divided by 14.615 gives . Likewise : sci-fi fans negative, romance fans positive, user 6 near 0.
- 5Rank-2 reconstruction of one entry. , against the true 5.
- 6Error by Eckart–Young. (RMS error per cell ). The two kept layers hold of the energy.
| k | σₖ | σₖ² | Energy kept | ‖A − Aₖ‖²_F | ‖A − Aₖ‖₂ | Numbers stored k(m+n+1) |
|---|---|---|---|---|---|---|
| 1 | 14.615 | 213.59 | 79.4% | 55.408 | 7.220 | 11 |
| 2 | 7.220 | 52.13 | 98.8% | 3.281 | 1.499 | 22 |
| 3 | 1.499 | 2.25 | 99.6% | 1.034 | 1.017 | 33 |
| 4 | 1.017 | 1.03 | 100% | 0 | 0 | 44 (vs 24 raw) |
Predicting for a new user. A newcomer rates only Alien = 5 and Notting Hill = 1. Find the coordinates in the rank-2 taste space that fit those two ratings: solve , giving . The full predicted row is : recommend Star Wars (5.06), skip Titanic (1.05). With only the same fit predicts — popularity alone cannot see the genre, which is exactly what layer 2 adds.
The algorithm, step by step
The textbook construction (eigen-decompose ) is how to understand the SVD, not how to compute it. Libraries use the Golub–Kahan–Reinsch family; for a few top components on big matrices they use iterative or randomized methods.
Exact SVD (LAPACK gesdd / gesvd)
- 1Bidiagonalize. Apply Householder reflections alternately from the left and right, , with upper-bidiagonal. Orthogonal transforms leave the singular values unchanged. Cost for .
- 2Diagonalize . Run implicit-shift QR sweeps (gesvd) or divide-and-conquer (gesdd, NumPy's default) on the bidiagonal matrix until off-diagonals vanish: .
- 3Assemble. , . Sort by and fix signs if you want a canonical form.
- 4Truncate to the top if you only need .
Top-k SVD by power iteration with deflation (what the from-scratch code does)
- 1Start with a random unit vector .
- 2Repeat , until it stops changing — never form explicitly.
- 3Set and .
- 4Deflate: removes this layer, so the next run converges to the next singular triple.
- 5Repeat times. Each run costs per iteration; convergence slows when is close to 1.
Randomized SVD (Halko–Martinsson–Tropp; used by scikit-learn)
- 1Draw a Gaussian test matrix of size , with a small oversampling (scikit-learn's default is 10).
- 2Sample the range: , using power iterations (re-orthonormalized each time) to sharpen a slowly decaying spectrum.
- 3Orthonormalize: , an basis that captures the top of 's range.
- 4Project to a small matrix , , and take its exact SVD .
- 5Lift back: ; keep the first columns. Cost about plus a few passes over .
Complexity
- Exact thin SVD
- time, memory — fine to about dense
- Top-k (Lanczos / ARPACK, randomized)
- about dense, or for a sparse matrix with nnz non-zeros
- Projecting a new row
- : (or for -coordinates)
- Storage of Aₖ
- numbers instead of
Variants and practical tuning
| Variant | Computes | Use when | Call |
|---|---|---|---|
| Full SVD | U (m×m), Σ, V (n×n) | you need null-space bases | np.linalg.svd(A) |
| Thin (economy) SVD | U (m×r), Σ, V (n×r) | the default for data | svd(A, full_matrices=False) |
| Truncated, iterative | top k only | big / sparse, k ≪ min(m,n) | scipy.sparse.linalg.svds |
| Randomized | top k, approximately | big dense matrices | sklearn randomized_svd |
| Centred SVD | SVD of centred A | variance directions (PCA) | sklearn PCA |
| Incremental / streaming | running top k | data larger than memory | sklearn IncrementalPCA |
Choosing k and preparing A
- Energy threshold
- smallest whose cumulative passes a target (90%, 95%…). For the ratings, already keeps 98.8%
- Spectrum gap / elbow
- plot on a log scale and cut where it drops into a flat noise floor (here 7.22 → 1.50)
- Optimal hard threshold
- for a matrix of signal plus i.i.d. noise, Gavish and Donoho derive a cutoff proportional to the median singular value — a principled default when no labels exist
- Downstream validation
- if the factors feed a model (recommender, classifier), choose by held-out error, not by energy
- Centring and scaling
- a column with large units dominates . Uncentred, often just captures the mean (here: "likes movies"); centre if you want contrasts, standardize if units differ
- Rank cutoff
- for pseudo-inverses treat as 0 (NumPy's pinv default is a few multiples of machine precision); raise it to regularize
In code
1import numpy as np23def svd_power(A, k, iters=500, seed=0):4 """Top-k SVD by power iteration on A^T A, with deflation."""5 A = A.astype(float).copy()6 rng = np.random.default_rng(seed)7 U, S, V = [], [], []8 for _ in range(k):9 v = rng.normal(size=A.shape[1])10 for _ in range(iters):11 v = A.T @ (A @ v) # one step of power iteration on A^T A12 v /= np.linalg.norm(v)13 Av = A @ v14 sigma = np.linalg.norm(Av) # sigma = ||A v||15 u = Av / sigma # u = A v / sigma16 if v[np.argmax(abs(v))] < 0: # fix the sign ambiguity17 u, v = -u, -v18 U.append(u); S.append(sigma); V.append(v)19 A -= sigma * np.outer(u, v) # deflate: remove this rank-1 layer20 return np.array(U).T, np.array(S), np.array(V)2122# users x movies: Alien, Star Wars, Notting Hill, Titanic23A = np.array([[5, 5, 1, 1],24 [4, 5, 1, 2],25 [5, 4, 2, 1],26 [1, 1, 5, 4],27 [2, 1, 4, 5],28 [3, 3, 3, 3]], float)2930U, S, Vt = svd_power(A, k=4)31print("singular values:", S.round(3))32print("v1:", Vt[0].round(3), " v2:", Vt[1].round(3))3334A2 = U[:, :2] * S[:2] @ Vt[:2] # best rank-2 approximation35print("rank-2 error ||A-A2||_F^2 =", round(((A - A2) ** 2).sum(), 3),36 " = s3^2 + s4^2 =", round((S[2:] ** 2).sum(), 3))37print("energy kept:", round((S[:2] ** 2).sum() / (S ** 2).sum(), 4))3839# new user: Alien = 5, Notting Hill = 1, the rest unknown40known, x = [0, 2], np.array([5.0, 1.0])41z = np.linalg.lstsq(Vt[:2, known].T, x, rcond=None)[0]42print("predicted ratings:", (z @ Vt[:2]).round(2))4344# singular values: [14.615 7.22 1.499 1.017]45# v1: [0.579 0.553 0.423 0.425] v2: [-0.386 -0.462 0.569 0.56 ]46# rank-2 error ||A-A2||_F^2 = 3.281 = s3^2 + s4^2 = 3.28147# energy kept: 0.987848# predicted ratings: [5. 5.06 1. 1.05]1import numpy as np2from sklearn.utils.extmath import randomized_svd34A = np.array([[5, 5, 1, 1], [4, 5, 1, 2], [5, 4, 2, 1],5 [1, 1, 5, 4], [2, 1, 4, 5], [3, 3, 3, 3]], float)67U, s, Vt = np.linalg.svd(A, full_matrices=False) # exact, LAPACK8print("sigma:", s.round(3))9print("energy:", (np.cumsum(s**2) / (s**2).sum()).round(4))1011k = 212A2 = U[:, :k] @ np.diag(s[:k]) @ Vt[:k]13print("Frobenius error:", round(np.linalg.norm(A - A2), 3),14 " spectral error:", round(np.linalg.norm(A - A2, 2), 3))1516# Randomized SVD: only the top k, cost O(m n k) -- what you use on big matrices17Ur, sr, Vtr = randomized_svd(A, n_components=k, random_state=0)18print("randomized sigma:", sr.round(3))1920# Pseudo-inverse from the SVD solves least squares21print("pinv(A) @ A ~ I:", np.allclose(np.linalg.pinv(A) @ A, np.eye(4)))22print("condition number:", round(s[0] / s[-1], 2))2324# sigma: [14.615 7.22 1.499 1.017]25# energy: [0.794 0.9878 0.9962 1. ]26# Frobenius error: 1.811 spectral error: 1.49927# randomized sigma: [14.615 7.22 ]28# pinv(A) @ A ~ I: True29# condition number: 14.37Note the two error norms: the Frobenius error is the root of the dropped energy, while the spectral error is exactly — Eckart–Young in both norms.
Use when
- +You need the best low-rank approximation of a matrix with a guaranteed, computable error.
- +You want latent factors of a matrix (users × items, documents × terms, time × sensors) or to compress / denoise it.
- +You are solving least squares that may be rank-deficient or ill-conditioned — the SVD shows and controls the small σ's.
- +You need numerically stable rank, null space, condition number or pseudo-inverse.
Avoid when
- −The structure is nonlinear (curved manifolds, clusters) — linear layers miss it; consider Kernel PCA, t-SNE or UMAP.
- −You need parts-based, non-negative factors that are easy to interpret — singular vectors mix signs; use NMF.
- −The matrix is huge and sparse — a dense exact SVD is infeasible; use a truncated / randomized solver (Truncated SVD).
- −Many entries are missing — a plain SVD needs a complete matrix; use matrix-completion methods.
- −Outliers are present — squared error lets a few large entries dominate σ₁ (robust PCA addresses this).
Where it's used
Recommender systems
Latent-factor models factor the users × items matrix; the Netflix Prize era popularized SVD-style factorizations fitted on observed ratings only.
Image and signal compression
An image stored as needs numbers; natural images have fast-decaying spectra, so modest looks close to the original.
Text: latent semantic analysis
The SVD of a documents × terms matrix groups co-occurring words into topics — the main use of Truncated SVD.
Numerical solvers and statistics
Least squares (lstsq), pseudo-inverses, rank and condition-number checks, PCA, canonical correlation and many regularized regression methods are computed through the SVD.
Check yourself
A matrix has singular values 10, 3 and 1. What is the Frobenius error of its best rank-1 approximation?
Check yourself
How are the singular values of A related to the eigenvalues of AᵀA?
Check yourself
For A = [3 0; 4 5] (σ₁ = 6.708, σ₂ = 2.236), what is the condition number, and what is |det A|?
Check yourself
A 1000×800 grayscale image is stored as its rank-50 truncated SVD. How many numbers are stored, as a share of the raw pixels?
Remember
- ✓Every matrix factors as : rotate (), stretch (), rotate () — or a sum of rank-1 layers sorted by importance.
- ✓ are eigenvectors of , its eigenvalues, and — but compute with a real SVD routine, never via .
- ✓Eckart–Young: keeping the top layers is the best rank- approximation; the squared Frobenius error is exactly and the spectral error is .
- ✓The pseudo-inverse solves least squares; small amplify noise, which truncation or ridge filter factors control.
- ✓PCA is the SVD of centred data; for big or sparse matrices compute only the top with randomized or Lanczos solvers.