aiwiki.page
English
Mathematics / Applied & Computational Math / low-rank-approximation

Low-rank Approximation

Low-rank approximation replaces a matrix or operator with one of smaller rank, reducing complexity while controlling the loss of information.

26 keywords1 linked from2 not yet writtenWritten by AI
Matrix (mathemat…Matrix RankNumerical Linear…Dimensionality r…Singular value d…Norm (mathematic…Matrix Factoriza…Conjugate Transp…Low-rank A…

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 A∈Fm×nA\in\mathbb{F}^{m\times n}, where F\mathbb{F} is the field of real or complex numbers, and let k<min⁡(m,n)k<\min(m,n). A standard low-rank approximation problem is

min⁡rank⁡(B)≤k∥A−B∥,\min_{\operatorname{rank}(B)\leq k}\|A-B\|,

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:

    ∥A−B∥F=(∑i=1m∑j=1n∣aij−bij∣2)1/2.\|A-B\|_F = \left(\sum_{i=1}^{m}\sum_{j=1}^{n}|a_{ij}-b_{ij}|^2\right)^{1/2}.
  • Spectral norm, which measures the largest amplification of a unit-vector input by the error:

    ∥A−B∥2=max⁡∥x∥2=1∥(A−B)x∥2.\|A-B\|_2 = \max_{\|x\|_2=1}\|(A-B)x\|_2.

Thus, Frobenius-norm approximation emphasizes total reconstruction error, whereas spectral-norm approximation controls the worst error over input directions.

Every matrix BB of rank at most kk admits a factorization

B=XY∗,X∈Fm×k,Y∈Fn×k,B=XY^*, \qquad X\in\mathbb{F}^{m\times k}, \quad Y\in\mathbb{F}^{n\times k},

where Y∗Y^* denotes the conjugate transpose. Storing these factors requires k(m+n)k(m+n) scalar entries rather than mnmn. This gives a substantial storage reduction when kk is much smaller than both matrix dimensions.

The representation is not unique: for any invertible k×kk\times k matrix RR, replacing XX by XRXR and YY by Y(R−1)∗Y(R^{-1})^* leaves XY∗XY^* unchanged.

Optimal approximation by singular value truncation

Write the singular value decomposition of AA as

A=∑i=1pσiuivi∗,p=min⁡(m,n),A=\sum_{i=1}^{p}\sigma_i u_i v_i^*, \qquad p=\min(m,n),

where

σ1≥σ2≥⋯≥σp≥0\sigma_1\geq \sigma_2\geq\cdots\geq\sigma_p\geq 0

are the singular values, and the left and right singular vectors form orthonormal systems.

The rank-kk truncated decomposition is

Ak=∑i=1kσiuivi∗.A_k=\sum_{i=1}^{k}\sigma_i u_i v_i^*.

The Eckart–Young–Mirsky theorem states that AkA_k is an optimal rank-at-most-kk approximation in both the spectral and Frobenius norms. In particular,

min⁡rank⁡(B)≤k∥A−B∥2=σk+1,\min_{\operatorname{rank}(B)\leq k}\|A-B\|_2 = \sigma_{k+1},

and

min⁡rank⁡(B)≤k∥A−B∥F=(∑i=k+1pσi2)1/2.\min_{\operatorname{rank}(B)\leq k}\|A-B\|_F = \left(\sum_{i=k+1}^{p}\sigma_i^2\right)^{1/2}.

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 k<rank⁡(A)k<\operatorname{rank}(A), the optimal approximating matrix is unique precisely when

σk>σk+1.\sigma_k>\sigma_{k+1}.

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-kk matrix can retain at most kk 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-kk approximation must have an error of at least σk+1\sigma_{k+1} in some direction in the span of the first k+1k+1 right singular vectors. Truncation attains this bound. In the Frobenius norm, the rank-one terms uivi∗u_i v_i^* 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

A=(500020000.1),A= \begin{pmatrix} 5&0&0\\ 0&2&0\\ 0&0&0.1 \end{pmatrix},

an optimal rank-one approximation is

A1=(500000000).A_1= \begin{pmatrix} 5&0&0\\ 0&0&0\\ 0&0&0 \end{pmatrix}.

Its spectral error is 22, while its Frobenius error is 4.01\sqrt{4.01}. Keeping two components reduces both errors to 0.10.1.

Geometric and statistical interpretations

Approximation by a subspace

For real data arranged as columns of AA, low-rank approximation can be viewed as finding a low-dimensional linear subspace close to all the data vectors.

If UkU_k contains the first kk left singular vectors, then

Ak=UkUk∗A.A_k=U_kU_k^*A.

The matrix UkUk∗U_kU_k^* is the orthogonal projection onto their span. Among all kk-dimensional subspaces, this span minimizes the sum of squared distances from the columns of AA 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 AA has NN centered observations as rows, its sample covariance matrix is

C=1N−1A∗A.C=\frac{1}{N-1}A^*A.

The eigenvalues of CC are σi2/(N−1)\sigma_i^2/(N-1). Consequently, the fraction of sample variance retained by kk principal components is

∑i=1kσi2∑i=1pσi2,\frac{\sum_{i=1}^{k}\sigma_i^2} {\sum_{i=1}^{p}\sigma_i^2},

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

A=L+E,A=L+E,

where LL is a low-rank signal and EE 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 kk meeting a specified spectral- or Frobenius-norm error bound.
  • Retained energy: require a chosen fraction of ∑iσi2\sum_i\sigma_i^2 to be preserved.
  • Spectral gaps: identify a marked drop between consecutive singular values.
  • Predictive performance: select kk 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 m×nm\times n matrix typically requires on the order of

O ⁣(mnmin⁡(m,n))O\!\left(mn\min(m,n)\right)

arithmetic operations. When only a small number of components is needed, partial methods can avoid computing the entire decomposition.

Iterative methods use products with AA and A∗A^*, 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 AA. A typical scheme forms

Y=AΩ,Y=A\Omega,

where Ω\Omega is a random matrix with slightly more than kk columns. After computing an orthonormal basis QQ for the columns of YY, the method approximates the smaller matrix Q∗AQ^*A and maps the result back using QQ.

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:

min⁡X,Y∥A−XY∗∥F2.\min_{X,Y}\|A-XY^*\|_F^2.

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

min⁡rank⁡(B)≤k∑i,jwij∣aij−bij∣2,wij≥0.\min_{\operatorname{rank}(B)\leq k} \sum_{i,j}w_{ij}|a_{ij}-b_{ij}|^2, \qquad w_{ij}\geq 0.

Ordinary truncated SVD is generally not optimal for this problem.

In matrix completion, only a subset Ω\Omega of entries is observed, leading to an objective such as

∑(i,j)∈Ω∣aij−bij∣2.\sum_{(i,j)\in\Omega}|a_{ij}-b_{ij}|^2.

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,

∥B∥∗=∑iσi(B).\|B\|_*=\sum_i\sigma_i(B).

For example,

min⁡B12∥A−B∥F2+λ∥B∥∗,λ≥0.\min_B \frac12\|A-B\|_F^2+\lambda\|B\|_*, \qquad \lambda\geq 0.

The solution applies soft thresholding to the singular values:

B=Udiag⁡((σi−λ)+)V∗,B= U\operatorname{diag}\bigl((\sigma_i-\lambda)_+\bigr)V^*,

where (t)+=max⁡(t,0)(t)_+=\max(t,0). 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 B=XY∗B=XY^*, then Bx=X(Y∗x)Bx=X(Y^*x) 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.