Low-Rank Approximation

Definition

Low-rank approximation is the problem of representing a matrix $A$ by another matrix $B$ of prescribed rank $r$ that is as close to $A$ as possible. Under the least-squares (Frobenius-norm) criterion, the Eckart-Young theorem (Eckart-Young 1936) shows the optimum is the truncated singular value decomposition: keep the $r$ largest singular values of $A$ and zero the rest. It is the mathematical foundation of principal components, factor analysis, and reduced-rank regression.

Key Ideas

• Eckart-Young theorem. For $A=\sum_k s_k u_k v_k'$ (SVD, $s_1\ge s_2\ge\cdots$), the rank-$r$ minimizer of $\|A-B\|_F$ is $B_r=\sum_{k\le r}s_k u_k v_k'$, with error $\|A-B_r\|_F^2=\sum_{k>r}s_k^2$. Mirsky (1960) later showed the same truncation is optimal for every unitarily invariant norm (including the spectral norm).
• SVD as the enabling device. The entries of a rank-$r$ matrix are not free parameters, so naive normal equations fail; expressing $A$ in "canonic form" (its SVD) decouples the problem and yields the closed-form solution. The existence of this canonic form — orthogonal $P,Q$ with $P'AQ$ nonnegative diagonal (Horst's "basic structure") — was stated but not proved by Eckart-Young; Johnson (1963) supplied the general proof for arbitrary real matrices (earlier sources covered only the square nonsingular case).
• Existence and (usual) uniqueness. A minimizer always exists and is unique unless $s_r=s_{r+1}$ (a tie at the truncation boundary), where the top-$r$ singular subspace is not identified.
• Equivalence to PCA. Applied to a centered data matrix, the truncated SVD gives the principal components; applied to a covariance matrix, it gives the leading eigen-directions — so PCA is optimal low-rank approximation.

Why It Matters

• Bedrock of factor models. The postulate that a data matrix is low-rank-plus-noise (Factor Model, Dynamic Factor Model) is made precise and optimal by Eckart-Young; principal-components / diffusion-index forecasting (large-$N$ macro panels) rests on it.
• Reduced-rank structure. Reduced-rank regression, cointegration (a reduced-rank coefficient matrix), and canonical-correlation methods all invoke low-rank optimality.
• Compression and denoising. Truncating small singular values compresses and denoises matrices (images, covariance matrices, recommender systems), trading a controlled amount of squared error for a large drop in rank.
• Linear autoencoders learn PCA (Baldi-Hornik 1989). The simplest neural network — a linear autoencoder minimising squared reconstruction error through a rank-$p$ bottleneck — has the Eckart-Young low-rank projection as its unique minimum (projection onto the top-$p$ principal subspace), and all other critical points are saddle points. So PCA/optimal-low-rank is reached not only by the SVD but also by gradient descent on a benign (no non-global local minima) non-convex landscape — an early and influential instance of the "only saddles, no bad minima" picture in deep-learning theory.

Open Questions

• Beyond Frobenius/unitarily-invariant norms. Low-rank approximation under weighted, element-wise $\ell_1$ (robust PCA), or missing-data criteria is generally non-convex with no closed-form SVD solution.
• Choosing the rank $r$. The theorem is conditional on $r$; selecting it (scree/eigenvalue thresholds, information criteria, cross-validation) is a separate, model-dependent problem.

Related

• Factor Model
• Dynamic Factor Model
• Covariance Matrix Estimation
• Eckart-Young (1936) The Approximation of One Matrix by Another of Lower Rank
• Johnson (1963) On a Theorem Stated by Eckart and Young
• Baldi-Hornik (1989) Neural Networks and Principal Component Analysis
• Attention Mechanism
• Carl Eckart
• Gale Young
• Richard M. Johnson
• Pierre Baldi
• Kurt Hornik