Low-rank approximation is the replacement of a matrix or linear operator by another of smaller rank that is close to the original under a specified measure of error. It represents a complicated array of relationships using relatively few independent components. A central technique in numerical linear algebra, it supports data compression, noise reduction, dimensionality reduction, and efficient computation. For fully observed matrices measured in the Frobenius or spectral norm, an optimal approximation is obtained by truncating the singular value decomposition.
Mathematical formulation
Let , where is the field of real or complex numbers, and let . A standard low-rank approximation problem is
where the chosen norm determines how approximation error is measured.
Two common choices are:
Frobenius norm, which measures the aggregate squared error over all entries:
Spectral norm, which measures the largest amplification of a unit-vector input by the error:
Thus, Frobenius-norm approximation emphasizes total reconstruction error, whereas spectral-norm approximation controls the worst error over input directions.
Every matrix of rank at most admits a factorization
where denotes the conjugate transpose. Storing these factors requires scalar entries rather than . This gives a substantial storage reduction when is much smaller than both matrix dimensions.
The representation is not unique: for any invertible matrix , replacing by and by leaves unchanged.
Optimal approximation by singular value truncation
Write the singular value decomposition of as
where
are the singular values, and the left and right singular vectors form orthonormal systems.
The rank- truncated decomposition is
The Eckart–Young–Mirsky theorem states that is an optimal rank-at-most- approximation in both the spectral and Frobenius norms. In particular,
and
More generally, singular value truncation is optimal for every unitarily invariant norm: a norm unchanged by multiplying on either side by a compatible unitary matrix.
For Frobenius-norm approximation, if , the optimal approximating matrix is unique precisely when
If singular values tie across the truncation boundary, different choices of retained singular directions can give different optimal matrices. Spectral-norm minimizers can be nonunique even when there is a strict gap.
Why truncation is optimal
A rank-at-most- matrix can retain at most independent directions of action. The singular vectors identify mutually orthogonal input and output directions, ordered by the strength of the matrix’s action. Retaining the largest singular values therefore preserves the strongest components.
For the spectral norm, any rank- approximation must have an error of at least in some direction in the span of the first right singular vectors. Truncation attains this bound. In the Frobenius norm, the rank-one terms are orthonormal under the matrix inner product, so the squared error of the discarded terms is the sum of their squared singular values.
Example
For
an optimal rank-one approximation is
Its spectral error is , while its Frobenius error is . Keeping two components reduces both errors to .
Geometric and statistical interpretations
Approximation by a subspace
For real data arranged as columns of , low-rank approximation can be viewed as finding a low-dimensional linear subspace close to all the data vectors.
If contains the first left singular vectors, then
The matrix is the orthogonal projection onto their span. Among all -dimensional subspaces, this span minimizes the sum of squared distances from the columns of to their projections.
Relationship to principal component analysis
For appropriately centered data, principal component analysis identifies the same leading singular subspaces. Its reconstruction problem is therefore a Frobenius-norm low-rank approximation problem.
If has centered observations as rows, its sample covariance matrix is
The eigenvalues of are . Consequently, the fraction of sample variance retained by principal components is
provided the denominator is nonzero.
Centering matters: an uncentered low-rank approximation fits a linear subspace through the origin, while centered principal component analysis corresponds to an affine subspace through the sample mean.
Signal and noise
A common model is
where is a low-rank signal and is noise. Truncation can improve estimation when the signal is concentrated in leading singular components and the noise is sufficiently dispersed.
However, the best approximation to the observed matrix need not be the best estimate of the underlying signal. Singular value shrinkage, which reduces retained singular values rather than simply retaining or discarding them, can have better statistical performance under particular noise models.
Choosing the rank
The target rank determines a trade-off between compression and fidelity.
Common criteria include:
- Error tolerance: choose the smallest meeting a specified spectral- or Frobenius-norm error bound.
- Retained energy: require a chosen fraction of to be preserved.
- Spectral gaps: identify a marked drop between consecutive singular values.
- Predictive performance: select using cross-validation on the downstream task.
- Noise modeling: distinguish singular values attributable to signal from those expected under a noise model.
These criteria answer different questions. A rank sufficient for small reconstruction error may not be sufficient for preserving a rare feature or predicting a particular outcome.
The numerical rank of a matrix is the number of singular values regarded as significant relative to a tolerance. Unlike exact rank, numerical rank depends on measurement precision, scaling, and the intended application.
Computational methods
Direct and partial decompositions
A full singular value decomposition of a dense matrix typically requires on the order of
arithmetic operations. When only a small number of components is needed, partial methods can avoid computing the entire decomposition.
Iterative methods use products with and , making them useful for very large matrices, sparse matrices, or operators available only through matrix–vector products. Convergence depends partly on the distribution and separation of singular values.
Rank-revealing QR decompositions also provide low-rank representations. They may offer computational or structural advantages, although they do not generally attain the exact optimal error given by truncated SVD.
Randomized approximation
Randomized methods first construct a smaller subspace that approximately captures the range of . A typical scheme forms
where is a random matrix with slightly more than columns. After computing an orthonormal basis for the columns of , the method approximates the smaller matrix and maps the result back using .
Oversampling improves reliability. Power iterations can improve accuracy when singular values decay slowly, but require additional passes over the data and careful orthogonalization for numerical stability. These methods are especially useful when data movement is expensive or matrix products can be computed efficiently.
Optimization over factors
Another approach minimizes an objective function directly over factors:
This formulation enforces the rank bound without explicitly manipulating a rank constraint. Alternating minimization fixes one factor while updating the other, producing a sequence of least-squares problems.
The objective is not jointly convex in the factors. Although the unweighted, fully observed problem has a known global solution through SVD, constrained and partially observed variants require separate analysis.
Variants and related problems
Weighted approximation and missing entries
When entries have different importance or reliability, the objective may be
Ordinary truncated SVD is generally not optimal for this problem.
In matrix completion, only a subset of entries is observed, leading to an objective such as
Recovering the unobserved entries requires assumptions beyond low rank, including sufficient observation coverage and restrictions preventing the information from being concentrated in a few rows or columns. Treating missing entries as observed zeros changes the problem.
Rank penalties and nuclear-norm regularization
Instead of fixing a rank, an optimization problem can penalize complexity. Direct rank penalties are difficult to optimize in general. A common convex alternative uses the nuclear norm,
For example,
The solution applies soft thresholding to the singular values:
where . This is a form of regularization rather than a fixed-rank constraint.
Structural constraints
Some applications require nonnegative entries, symmetry, positive semidefiniteness, or other structure. These requirements can change the feasible set and eliminate the optimality of ordinary SVD truncation.
Factorizations built from actual rows and columns of the original matrix can be more interpretable than singular-vector factors, though their errors need not equal the optimal truncated-SVD error.
Low-rank approximation also extends to tensors, but tensor rank has several inequivalent definitions. For tensors of order three or higher, a best approximation of a prescribed canonical rank need not exist, unlike the standard finite-dimensional matrix problem.
Applications and limitations
Low-rank representations are used in image compression, recommendation systems, document analysis, reduced-order simulation, and machine learning. They can reduce storage and accelerate matrix–vector multiplication: if , then can be evaluated without forming the full matrix.
Their usefulness depends on spectral decay. If many singular values have comparable size, a small-rank approximation necessarily discards substantial information. Low rank also does not imply sparsity, and singular-vector factors are usually dense.
Frobenius-norm fitting is sensitive to large entrywise errors because residuals are squared. It may also obscure localized or low-energy features. Scaling and preprocessing can substantially change the resulting approximation, while a small gap at the truncation boundary can make the selected subspace sensitive to perturbations.
Historical development
The mathematical foundations connect to early work on orthogonal expansions and integral operators, including Erhard Schmidt’s work in 1907. Carl Eckart and Gale Young established the classical least-squares matrix approximation result in 1936. Leon Mirsky extended the optimality framework to unitarily invariant norms in 1960.
Subsequent work developed efficient numerical decompositions, iterative and randomized algorithms, and methods for incomplete or corrupted data, broadening low-rank approximation from a matrix approximation theorem into a general computational modeling approach.