SVD

Factor the data matrix as UΣVᵀ; keeping the top k singular vectors gives the best rank-k approximation of the data.

17 min read1618 wordscore14 viewsupdated 2026-10-07

Definition

The singular value decomposition (SVD) writes any real m×nm\times n matrix as A=UΣV⊤A=U\Sigma V^\top: an orthonormal set of input directions VV, a list of non-negative stretch factors σ1≥σ2≥⋯≥0\sigma_1\ge\sigma_2\ge\dots\ge 0 on the diagonal of Σ\Sigma, and an orthonormal set of output directions UU. Equivalently, AA is a sum of rank-1 layers σiuivi⊤\sigma_i u_i v_i^\top sorted from most to least important — and cutting the sum after kk terms gives the best possible rank-kk approximation of AA.

At a glance

Task
Matrix factorization: dimensionality reduction, compression, denoising, latent factors, solving least squares
Input → output
a matrix A∈Rm×nA\in\mathbb{R}^{m\times n} → U∈Rm×rU\in\mathbb{R}^{m\times r}, σ1..σr\sigma_1..\sigma_r, V∈Rn×rV\in\mathbb{R}^{n\times r} with r=min⁡(m,n)r=\min(m,n) (thin SVD)
Learns
row-space directions viv_i (e.g. "taste profiles" over movies), column-space directions uiu_i (each user's coordinates), and their strengths σi\sigma_i
Training cost
exact: O(mnmin⁡(m,n))O(mn\min(m,n)); top-kk only (randomized / Lanczos): about O(mnk)O(mnk)
Prediction cost
projecting a new row xx: O(nk)O(nk) for z=Vk⊤xz=V_k^\top x; reconstructing it: another O(nk)O(nk)
Hyperparameters
the rank kk kept; the solver (full LAPACK, randomized, ARPACK); whether to centre / scale columns first; the cutoff below which a σi\sigma_i 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 A=QΛQ−1A=Q\Lambda Q^{-1} 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 V⊤V^\top), stretches along the coordinate axes (by Σ\Sigma, possibly squashing some axes to zero), and rotates again into the output space (by UU). Feed in the unit circle and you get an ellipse; the ellipse's semi-axes are σ1u1\sigma_1u_1 and σ2u2\sigma_2u_2, and the input directions that land on them are v1v_1 and v2v_2.

Layers. Read the same factorization as a sum: A=σ1u1v1⊤+σ2u2v2⊤+…A=\sigma_1u_1v_1^\top+\sigma_2u_2v_2^\top+\dots. Each term is a rank-1 matrix — a single pattern viv_i across the columns, multiplied by a single loading uiu_i down the rows. For ratings, v1v_1 might be "overall movie popularity" and v2v_2 "romance minus sci-fi"; uiu_i says how strongly each user expresses that pattern. The layers are sorted by σi\sigma_i, so the first few carry the bulk of the matrix and the tail is mostly noise.

Vocabulary

Singular value σᵢ
the ii-th stretch factor, σi≥0\sigma_i\ge 0, sorted descending. σ1\sigma_1 is the largest gain ∥Av∥\|Av\| over unit vectors vv
Right singular vector vᵢ
a unit vector in the input space Rn\mathbb{R}^n (a pattern over the columns); the viv_i are orthonormal and are the eigenvectors of A⊤AA^\top A
Left singular vector uᵢ
a unit vector in the output space Rm\mathbb{R}^m (a loading over the rows); ui=Avi/σiu_i=Av_i/\sigma_i, the eigenvectors of AA⊤AA^\top
Rank r
the number of non-zero singular values — the true number of independent directions in AA
Full / thin / truncated SVD
full: UU is m×mm\times m, VV is n×nn\times n; thin: only the min⁡(m,n)\min(m,n) columns that meet Σ\Sigma; truncated: only the top kk (see Truncated SVD)
Frobenius norm
∥A∥F=∑ijaij2=∑iσi2\|A\|_F=\sqrt{\sum_{ij}a_{ij}^2}=\sqrt{\sum_i\sigma_i^2} — total "energy" of the matrix
Spectral norm
∥A∥2=σ1\|A\|_2=\sigma_1 — the most any unit vector can be stretched
Energy kept
∑i≤kσi2 /∑iσi2\sum_{i\le k}\sigma_i^2\,/\sum_i\sigma_i^2 — the fraction of ∥A∥F2\|A\|_F^2 that a rank-kk approximation retains
Condition number
κ=σ1/σr\kappa=\sigma_1/\sigma_r — how much relative error in bb can be amplified when solving Ax=bAx=b
Pseudo-inverse A⁺
VΣ+U⊤V\Sigma^+U^\top, where Σ+\Sigma^+ inverts the non-zero σi\sigma_i — the least-squares, minimum-norm "inverse" of any matrix

The math

A=UΣV⊤=∑i=1rσi uivi⊤,U⊤U=I,  V⊤V=IA=U\Sigma V^\top=\sum_{i=1}^{r}\sigma_i\,u_i v_i^\top,\qquad U^\top U=I,\; V^\top V=I
AA
the data matrix, mm rows (samples) × nn columns (features)
U=[u1…ur]U=[u_1\dots u_r]
m×rm\times r, orthonormal columns: left singular vectors
Σ\Sigma
r×rr\times r diagonal, entries σ1≥⋯≥σr>0\sigma_1\ge\dots\ge\sigma_r>0
V=[v1…vr]V=[v_1\dots v_r]
n×rn\times r, orthonormal columns: right singular vectors
rr
rank of AA (at most min⁡(m,n)\min(m,n))

Where VV and Σ\Sigma come from. Suppose the factorization exists. Then A⊤A=VΣU⊤UΣV⊤=VΣ2V⊤A^\top A=V\Sigma U^\top U\Sigma V^\top=V\Sigma^2V^\top. That is an eigendecomposition of the symmetric, positive-semidefinite matrix A⊤AA^\top A: its eigenvectors are the viv_i and its eigenvalues are σi2\sigma_i^2. Run the argument backwards to construct the SVD: the spectral theorem gives A⊤AA^\top A orthonormal eigenvectors viv_i with eigenvalues λi≥0\lambda_i\ge 0 (because v⊤A⊤Av=∥Av∥2≥0v^\top A^\top Av=\|Av\|^2\ge0). Set σi=λi\sigma_i=\sqrt{\lambda_i}.

ui=Aviσi⇒ui⊤uj=vi⊤A⊤A vjσiσj=σj2 vi⊤vjσiσj=δiju_i=\frac{Av_i}{\sigma_i}\quad\Rightarrow\quad u_i^\top u_j=\frac{v_i^\top A^\top A\,v_j}{\sigma_i\sigma_j}=\frac{\sigma_j^2\,v_i^\top v_j}{\sigma_i\sigma_j}=\delta_{ij}
δij\delta_{ij}
1 if i=ji=j, else 0 — so the uiu_i come out orthonormal automatically
Avi=σiuiAv_i=\sigma_iu_i
the defining pair of equations; also A⊤ui=σiviA^\top u_i=\sigma_iv_i

Stacking Avi=σiuiAv_i=\sigma_iu_i for all ii gives AV=UΣAV=U\Sigma, and multiplying by V⊤V^\top on the right gives A=UΣV⊤A=U\Sigma V^\top. Every matrix therefore has an SVD. The singular values are unique; each pair (ui,vi)(u_i,v_i) is unique up to a joint sign flip (or rotation within a block if two σ\sigma tie).

σ1=max⁡∥v∥=1∥Av∥,σk=max⁡∥v∥=1,  v⊥v1..vk−1∥Av∥\sigma_1=\max_{\|v\|=1}\|Av\|,\qquad \sigma_k=\max_{\|v\|=1,\;v\perp v_1..v_{k-1}}\|Av\|
∥Av∥\|Av\|
how long the unit vector vv becomes after applying AA
v1v_1
the maximizer: the input direction AA stretches most

This variational view is what power iteration exploits: maximizing ∥Av∥2=v⊤A⊤Av\|Av\|^2=v^\top A^\top Av is a Rayleigh quotient, so repeatedly applying A⊤AA^\top A to a vector and normalizing converges to v1v_1, at a rate set by (σ2/σ1)2(\sigma_2/\sigma_1)^2.

A 2×2 by hand. A=[3045]A=\begin{bmatrix}3&0\\4&5\end{bmatrix} gives A⊤A=[25202025]A^\top A=\begin{bmatrix}25&20\\20&25\end{bmatrix}, with eigenvalues 4545 and 55 and eigenvectors v1=(1,1)/2v_1=(1,1)/\sqrt2, v2=(−1,1)/2v_2=(-1,1)/\sqrt2. So σ1=45=6.708\sigma_1=\sqrt{45}=6.708, σ2=5=2.236\sigma_2=\sqrt5=2.236, u1=Av1/σ1=(1,3)/10=(0.316,0.949)u_1=Av_1/\sigma_1=(1,3)/\sqrt{10}=(0.316,0.949) and u2=Av2/σ2=(−3,1)/10u_2=Av_2/\sigma_2=(-3,1)/\sqrt{10}. Checks: σ1σ2=15=∣det⁡A∣\sigma_1\sigma_2=15=|\det A|, and κ=σ1/σ2=3\kappa=\sigma_1/\sigma_2=3. This is the default matrix in the figure below.

Why truncation is optimal (Eckart–Young)

Ak=∑i=1kσiuivi⊤=UkΣkVk⊤,min⁡rank⁡B≤k∥A−B∥F2=∥A−Ak∥F2=∑i>kσi2A_k=\sum_{i=1}^{k}\sigma_iu_iv_i^\top=U_k\Sigma_kV_k^\top,\qquad \min_{\operatorname{rank}B\le k}\|A-B\|_F^2=\|A-A_k\|_F^2=\sum_{i>k}\sigma_i^2
AkA_k
the truncated SVD: keep the top kk layers
Uk,Σk,VkU_k,\Sigma_k,V_k
the first kk columns of UU, VV and the top-left k×kk\times k block of Σ\Sigma
BB
any matrix of rank at most kk — no other one does better

Why the error is the tail sum. Orthogonal matrices preserve the Frobenius norm, so ∥A−Ak∥F=∥U⊤(A−Ak)V∥F=∥diag⁡(0,..,0,σk+1,..,σr)∥F\|A-A_k\|_F=\|U^\top(A-A_k)V\|_F=\|\operatorname{diag}(0,..,0,\sigma_{k+1},..,\sigma_r)\|_F. The optimality (no rank-kk BB beats it) follows from Weyl's inequality σi+k(A)≤σi(A−B)+σk+1(B)\sigma_{i+k}(A)\le\sigma_i(A-B)+\sigma_{k+1}(B) with σk+1(B)=0\sigma_{k+1}(B)=0: the residual A−BA-B must have singular values at least σk+1,σk+2,…\sigma_{k+1},\sigma_{k+2},\dots of AA. The same theorem holds in the spectral norm: min⁡rank⁡B≤k∥A−B∥2=σk+1\min_{\operatorname{rank}B\le k}\|A-B\|_2=\sigma_{k+1}.

The hyperparameter kk, mathematically. Raising kk by one adds one layer, lowers the squared error by exactly σk+12\sigma_{k+1}^2, and costs m+n+1m+n+1 more stored numbers. Since the σi\sigma_i 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

x⋆=A+b=VΣ+U⊤b=∑i=1rui⊤bσi vix^\star=A^+b=V\Sigma^+U^\top b=\sum_{i=1}^{r}\frac{u_i^\top b}{\sigma_i}\,v_i
x⋆x^\star
the minimum-norm minimizer of ∥Ax−b∥2\|Ax-b\|^2
ui⊤bu_i^\top b
the component of the target along output direction uiu_i
1/σi1/\sigma_i
the gain applied to it — huge when σᵢ is tiny

This explains ill-conditioning: noise in bb along a direction with small σi\sigma_i gets divided by σi\sigma_i and blows up. Two cures fall straight out of the formula: truncate (drop terms with σi\sigma_i below a cutoff — "truncated SVD regression"), or damp them — ridge regression multiplies each term by the filter factor σi2/(σi2+λ)\sigma_i^2/(\sigma_i^2+\lambda), which is about 1 for big σi\sigma_i 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.

UserAlienStar WarsNotting HillTitanic
u15511
u24512
u35421
u41154
u52145
u63333
The 6×4 ratings matrix A. Highlighted: user 6, who has no preference between genres.

Factoring A by hand

  1. 1Gram matrix. A⊤AA^\top A holds the dot products between movie columns: [80774141777736374136565441375456]\begin{bmatrix}80&77&41&41\\77&77&36&37\\41&36&56&54\\41&37&54&56\end{bmatrix}. Its trace 80+77+56+56=26980+77+56+56=269 equals ∥A∥F2\|A\|_F^2, the sum of all squared ratings.
  2. 2Eigenvalues of A⊤AA^\top A (the characteristic polynomial of a 4×4 is solved numerically): 213.59,  52.13,  2.25,  1.03213.59,\;52.13,\;2.25,\;1.03 — they sum to 269. Square roots give the singular values σ=(14.615,  7.220,  1.499,  1.017)\sigma=(14.615,\;7.220,\;1.499,\;1.017).
  3. 3Right singular vectors (eigenvectors of A⊤AA^\top A): v1=(0.579,0.553,0.423,0.425)v_1=(0.579,0.553,0.423,0.425) — all positive, "how much you like movies at all". v2=(−0.386,−0.462,0.569,0.560)v_2=(-0.386,-0.462,0.569,0.560) — negative on sci-fi, positive on romance: the genre axis.
  4. 4Left singular vectors ui=Avi/σiu_i=Av_i/\sigma_i. For i=1i=1: Av1=(6.506,6.352,6.376,4.945,5.527,5.938)Av_1=(6.506,6.352,6.376,4.945,5.527,5.938), divided by 14.615 gives u1=(0.445,0.435,0.436,0.338,0.378,0.406)u_1=(0.445,0.435,0.436,0.338,0.378,0.406). Likewise u2=(−0.431,−0.300,−0.288,0.587,0.532,0.117)u_2=(-0.431,-0.300,-0.288,0.587,0.532,0.117): sci-fi fans negative, romance fans positive, user 6 near 0.
  5. 5Rank-2 reconstruction of one entry. a^11=σ1u11v11+σ2u12v12=14.615(0.445)(0.579)+7.220(−0.431)(−0.386)=3.766+1.201=4.967\hat a_{11}=\sigma_1u_{11}v_{11}+\sigma_2u_{12}v_{12}=14.615(0.445)(0.579)+7.220(-0.431)(-0.386)=3.766+1.201=4.967, against the true 5.
  6. 6Error by Eckart–Young. ∥A−A2∥F2=σ32+σ42=2.247+1.034=3.281\|A-A_2\|_F^2=\sigma_3^2+\sigma_4^2=2.247+1.034=3.281 (RMS error per cell 3.281/24=0.37\sqrt{3.281/24}=0.37). The two kept layers hold (213.59+52.13)/269=98.8%(213.59+52.13)/269=98.8\% of the energy.
kσₖσₖ²Energy kept‖A − Aₖ‖²_F‖A − Aₖ‖₂Numbers stored k(m+n+1)
114.615213.5979.4%55.4087.22011
27.22052.1398.8%3.2811.49922
31.4992.2599.6%1.0341.01733
41.0171.03100%0044 (vs 24 raw)
Every rank k for the ratings matrix. The error column is exactly the sum of the dropped σᵢ²; the spectral error is the first dropped σ.

Predicting for a new user. A newcomer rates only Alien = 5 and Notting Hill = 1. Find the coordinates zz in the rank-2 taste space that fit those two ratings: solve [0.579−0.3860.4230.569]z=[51]\begin{bmatrix}0.579&-0.386\\0.423&0.569\end{bmatrix}z=\begin{bmatrix}5\\1\end{bmatrix}, giving z=(6.561,−3.113)z=(6.561,-3.113). The full predicted row is z⊤V2⊤=(5.00,  5.06,  1.00,  1.05)z^\top V_2^\top=(5.00,\;\mathbf{5.06},\;1.00,\;\mathbf{1.05}): recommend Star Wars (5.06), skip Titanic (1.05). With only k=1k=1 the same fit predicts (3.74,3.57,2.73,2.75)(3.74,3.57,2.73,2.75) — popularity alone cannot see the genre, which is exactly what layer 2 adds.

▸ SVD explorer
σ₁u₁σ₂u₂Ae₁Ae₂A = UΣVᵀ — stages:0. x1. Vᵀx2. ΣVᵀx3. UΣVᵀx = AxA = [3 0; 4 5]σ₁ = 6.708σ₂ = 2.236v₁ = (0.707, 0.707)u₁ = (0.316, 0.949)|det A| = σ₁σ₂ = 15.00cond = σ₁/σ₂ = 3.00U is a rotationdrag the □ handles (thecolumns of A) to change A
U rotates (or reflects) the axes onto u₁ and u₂
fig.Two tabs. Rotate · stretch · rotate: A = [3 0; 4 5] maps the unit circle to an ellipse; press play to watch Vᵀ turn v₁ = (0.707, 0.707) onto the x-axis, Σ stretch by σ₁ = 6.708 and σ₂ = 2.236, then U turn the axes onto u₁ = (0.316, 0.949). Drag the □ handles (the columns of A) to change the matrix; the coloured dots show where individual inputs travel. Best rank-k: the ratings matrix from the table, its rank-k reconstruction and the residual; at k = 2 the kept layers hold 98.8% of the energy and ‖A − A₂‖²_F = 3.281 = σ₃² + σ₄².

The algorithm, step by step

The textbook construction (eigen-decompose A⊤AA^\top A) 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)

  1. 1Bidiagonalize. Apply Householder reflections alternately from the left and right, A=QL B QR⊤A=Q_L\,B\,Q_R^\top, with BB upper-bidiagonal. Orthogonal transforms leave the singular values unchanged. Cost O(mn2)O(mn^2) for m≥nm\ge n.
  2. 2Diagonalize BB. Run implicit-shift QR sweeps (gesvd) or divide-and-conquer (gesdd, NumPy's default) on the bidiagonal matrix until off-diagonals vanish: B=WΣZ⊤B=W\Sigma Z^\top.
  3. 3Assemble. U=QLWU=Q_LW, V=QRZV=Q_RZ. Sort by σ\sigma and fix signs if you want a canonical form.
  4. 4Truncate to the top kk if you only need AkA_k.

Top-k SVD by power iteration with deflation (what the from-scratch code does)

  1. 1Start with a random unit vector v∈Rnv\in\mathbb{R}^n.
  2. 2Repeat v←A⊤(Av)v\leftarrow A^\top(Av), v←v/∥v∥v\leftarrow v/\|v\| until it stops changing — never form A⊤AA^\top A explicitly.
  3. 3Set σ=∥Av∥\sigma=\|Av\| and u=Av/σu=Av/\sigma.
  4. 4Deflate: A←A−σuv⊤A\leftarrow A-\sigma uv^\top removes this layer, so the next run converges to the next singular triple.
  5. 5Repeat kk times. Each run costs O(mn)O(mn) per iteration; convergence slows when σi+1/σi\sigma_{i+1}/\sigma_i is close to 1.

Randomized SVD (Halko–Martinsson–Tropp; used by scikit-learn)

  1. 1Draw a Gaussian test matrix Ω\Omega of size n×(k+p)n\times(k+p), with a small oversampling pp (scikit-learn's default is 10).
  2. 2Sample the range: Y=(AA⊤)qAΩY=(AA^\top)^qA\Omega, using qq power iterations (re-orthonormalized each time) to sharpen a slowly decaying spectrum.
  3. 3Orthonormalize: Q=qr⁡(Y)Q=\operatorname{qr}(Y), an m×(k+p)m\times(k+p) basis that captures the top of AA's range.
  4. 4Project to a small matrix B=Q⊤AB=Q^\top A, (k+p)×n(k+p)\times n, and take its exact SVD B=U~ΣV⊤B=\tilde U\Sigma V^\top.
  5. 5Lift back: U=QU~U=Q\tilde U; keep the first kk columns. Cost about O(mnk)O(mnk) plus a few passes over AA.

Complexity

Exact thin SVD
O(mnmin⁡(m,n))O(mn\min(m,n)) time, O(mn)O(mn) memory — fine to about 104×10410^4\times10^4 dense
Top-k (Lanczos / ARPACK, randomized)
about O(mnk)O(mnk) dense, or O(nnz⋅k)O(\text{nnz}\cdot k) for a sparse matrix with nnz non-zeros
Projecting a new row
O(nk)O(nk): z=Vk⊤xz=V_k^\top x (or Σk−1Vk⊤x\Sigma_k^{-1}V_k^\top x for uu-coordinates)
Storage of Aₖ
k(m+n+1)k(m+n+1) numbers instead of mnmn

Variants and practical tuning

VariantComputesUse whenCall
Full SVDU (m×m), Σ, V (n×n)you need null-space basesnp.linalg.svd(A)
Thin (economy) SVDU (m×r), Σ, V (n×r)the default for datasvd(A, full_matrices=False)
Truncated, iterativetop k onlybig / sparse, k ≪ min(m,n)scipy.sparse.linalg.svds
Randomizedtop k, approximatelybig dense matricessklearn randomized_svd
Centred SVDSVD of centred Avariance directions (PCA)sklearn PCA
Incremental / streamingrunning top kdata larger than memorysklearn IncrementalPCA
Which SVD to call. The decomposition is the same; what differs is how much of it you compute and on what matrix. Truncated and iterative solvers are covered in depth in Truncated SVD.

Choosing k and preparing A

Energy threshold
smallest kk whose cumulative ∑i≤kσi2/∑σi2\sum_{i\le k}\sigma_i^2/\sum\sigma_i^2 passes a target (90%, 95%…). For the ratings, k=2k=2 already keeps 98.8%
Spectrum gap / elbow
plot σi\sigma_i 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 kk by held-out error, not by energy
Centring and scaling
a column with large units dominates σ1\sigma_1. Uncentred, v1v_1 often just captures the mean (here: "likes movies"); centre if you want contrasts, standardize if units differ
Rank cutoff
for pseudo-inverses treat σi<rcond⋅σ1\sigma_i<\text{rcond}\cdot\sigma_1 as 0 (NumPy's pinv default is a few multiples of machine precision); raise it to regularize

In code

python
1import numpy as np
2
3def 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 A
12 v /= np.linalg.norm(v)
13 Av = A @ v
14 sigma = np.linalg.norm(Av) # sigma = ||A v||
15 u = Av / sigma # u = A v / sigma
16 if v[np.argmax(abs(v))] < 0: # fix the sign ambiguity
17 u, v = -u, -v
18 U.append(u); S.append(sigma); V.append(v)
19 A -= sigma * np.outer(u, v) # deflate: remove this rank-1 layer
20 return np.array(U).T, np.array(S), np.array(V)
21
22# users x movies: Alien, Star Wars, Notting Hill, Titanic
23A = 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)
29
30U, S, Vt = svd_power(A, k=4)
31print("singular values:", S.round(3))
32print("v1:", Vt[0].round(3), " v2:", Vt[1].round(3))
33
34A2 = U[:, :2] * S[:2] @ Vt[:2] # best rank-2 approximation
35print("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))
38
39# new user: Alien = 5, Notting Hill = 1, the rest unknown
40known, 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))
43
44# 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.281
47# energy kept: 0.9878
48# predicted ratings: [5. 5.06 1. 1.05]
From scratch with NumPy: power iteration + deflation, applied to the worked example.
python
1import numpy as np
2from sklearn.utils.extmath import randomized_svd
3
4A = 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)
6
7U, s, Vt = np.linalg.svd(A, full_matrices=False) # exact, LAPACK
8print("sigma:", s.round(3))
9print("energy:", (np.cumsum(s**2) / (s**2).sum()).round(4))
10
11k = 2
12A2 = 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))
15
16# Randomized SVD: only the top k, cost O(m n k) -- what you use on big matrices
17Ur, sr, Vtr = randomized_svd(A, n_components=k, random_state=0)
18print("randomized sigma:", sr.round(3))
19
20# Pseudo-inverse from the SVD solves least squares
21print("pinv(A) @ A ~ I:", np.allclose(np.linalg.pinv(A) @ A, np.eye(4)))
22print("condition number:", round(s[0] / s[-1], 2))
23
24# 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.499
27# randomized sigma: [14.615 7.22 ]
28# pinv(A) @ A ~ I: True
29# condition number: 14.37
Library version: exact LAPACK SVD, randomized top-k SVD from scikit-learn, and the pseudo-inverse.

Note the two error norms: the Frobenius error 1.811=3.2811.811=\sqrt{3.281} is the root of the dropped energy, while the spectral error 1.4991.499 is exactly σ3\sigma_3 — 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 m×nm\times n image stored as AkA_k needs k(m+n+1)k(m+n+1) numbers; natural images have fast-decaying spectra, so modest kk 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 A=UΣV⊤A=U\Sigma V^\top: rotate (V⊤V^\top), stretch (σi≥0\sigma_i\ge0), rotate (UU) — or a sum of rank-1 layers σiuivi⊤\sigma_iu_iv_i^\top sorted by importance.
  • ✓viv_i are eigenvectors of A⊤AA^\top A, σi2\sigma_i^2 its eigenvalues, and ui=Avi/σiu_i=Av_i/\sigma_i — but compute with a real SVD routine, never via A⊤AA^\top A.
  • ✓Eckart–Young: keeping the top kk layers is the best rank-kk approximation; the squared Frobenius error is exactly ∑i>kσi2\sum_{i>k}\sigma_i^2 and the spectral error is σk+1\sigma_{k+1}.
  • ✓The pseudo-inverse VΣ+U⊤V\Sigma^+U^\top solves least squares; small σi\sigma_i amplify noise, which truncation or ridge filter factors σi2/(σi2+λ)\sigma_i^2/(\sigma_i^2+\lambda) control.
  • ✓PCA is the SVD of centred data; for big or sparse matrices compute only the top kk with randomized or Lanczos solvers.
← back to ML Algorithms roadmap