Singular Value Decomposition and Low-Rank Structure

A face photograph is a grid of pixels, and a grid of pixels is a matrix. In 1987 L. Sirovich and M. Kirby asked how few ordered patterns could stand in for one. They assembled a file of 115 face photographs, each divided into 128 × 128 picture elements. Their introduction states the answer rather than promising it: “we show, through actual construction, that roughly 40 numbers giving the admixture of eigenpictures characterize a face to within 3% error”. That is the low-rank claim in its concrete form. A matrix of pixels, approximated by a short sum of rank-one patterns. The error stated as a number rather than as a hope.

For any real m×n matrix A, the singular value decomposition writes A = UΣVᵀ. The columns of V are orthogonal input directions, Σ contains nonnegative gains, and U gives the corresponding output directions. This three-part view separates orientation from strength. A matrix rotates or reflects into a principal coordinate system, scales each direction, then maps into the output space. Unlike eigendecomposition, the SVD applies to rectangular matrices. It does not require a complete eigenbasis.

A truncated SVD expresses a matrix as a sum of rank-one outer products ordered by singular value. Latent semantic indexing is that construction shipped as a product. Seven inventors at Bell Communications Research filed it in September 1988 and were granted US Patent 4,839,853 in June 1989. The patent puts the method in a single sentence: “A reduced SVD is employed to approximate the original matrix in terms of a much smaller number of orthogonal dimensions.” The matrix is terms against documents. The rank-one components are latent topics. And, unusually for a patent, the specification commits to a number for k.

The rank of A equals the number of nonzero singular values. In noisy data, exact zeros are rare, so practitioners also inspect effective rank or the decay pattern. A steep spectrum suggests that a few directions carry most of the matrix’s energy. A flat spectrum indicates that aggressive compression will discard substantial structure. The best rank-k approximation under common matrix norms is obtained by keeping the k largest singular values and corresponding vectors. This is the Eckart–Young result.

The name on the theorem is narrower than the theorem, and later than it too. Carl Eckart and Gale Young published their version in Psychometrika in 1936. Erhard Schmidt had proved it twenty-nine years earlier, in 1907, in a paper on linear and nonlinear integral equations. G. W. Stewart's history of the SVD makes the correction: “Eckart and Young [12, 1936], [13, 1939] extended it to rectangular matrices and rediscovered Schmidt's approximation theorem, which is often (and incorrectly) called the Eckart–Young theorem.” Leonid Mirsky then proved the general case in 1960. His version holds in every unitarily invariant norm. The Frobenius norm is one instance.

What a steep spectrum is worth in production can be read off a single system. LoRA, published in June 2021, freezes a pre-trained model’s weights and trains injected rank-decomposition matrices instead. The bet is that the update a fine-tune needs is low-rank even when the weight matrix is not. The abstract prices the bet: “Compared to GPT-3 175B fine-tuned with Adam, LoRA can reduce the number of trainable parameters by 10,000 times and the GPU memory requirement by 3 times.” The method matched or beat full fine-tuning on RoBERTa, DeBERTa, GPT-2 and GPT-3, and added no inference latency. Ten thousand times fewer trainable parameters is what an assumption about rank buys when it is correct.

A spectrum is evidence, not an automatic compression policy.

The familiar phrase is approximate because U and V can change dimension. But it captures the geometry.

Both methods reduce sensitivity to small singular values, but they impose different preferences.

Hard truncation is not condemned to be arbitrary. Matan Gavish and David Donoho derived the exact threshold in 2014. For an n-by-n matrix in noise of level sigma, the AMSE-optimal hard threshold is (4/sqrt(3))·sqrt(n)·sigma, about 2.309·sqrt(n)·sigma. When sigma is unknown, the rule becomes 2.858 times the median empirical singular value. Their abstract makes the strongest available claim for it: “it is always better than hard thresholding at any other value, no matter what the matrix is that we are trying to recover, and is always better than ideal Truncated SVD (TSVD), which truncates at the true rank of the low-rank matrix we are trying to recover.” Read that second clause slowly. Truncating at the true rank is provably not optimal. Thresholding at their value guarantees an AMSE of at most 3·n·r·sigma², against 5·n·r·sigma² for truncating at the true rank. Data-Driven Science and Engineering restates the rule with a worked case — n = 600, sigma = 1, cutoff tau approximately 56.6 — and disposes of the habit it replaces. Of energy-based truncation it says: “Although crude, this technique is commonly used.”

The cost of no stabilization at all is also on public record. The US National Institute of Standards and Technology publishes a certified least-squares benchmark named Filip: 82 observations, a 10th-degree polynomial with 11 parameters, classified “Higher Level of Difficulty”. The certified intercept is B0 = -1467.48961422980, the residual standard deviation 0.334801051324544E-02, the R-squared 0.996727416185620. The certified answers exist; the question is whether software can reach them. Allin Cottrell benchmarked the gretl econometrics package against the NIST values and recorded 0 correct significant digits on Filip with the standard solver: “gretl refuses to produce estimates due to a high degree of multicollinearity (the popular commercial econometrics program Eviews 3.1 also baulks at this regression).” Two shipping regression packages, one certified dataset, zero correct digits. Only the multiple-precision GMP plugin reached 12. That is what dividing at full inverse strength by singular values close to zero does to a problem that looks well posed.