EckartYoung

The Eckart–Young theorem, sometimes called the Eckart–Young–Mendelsohn theorem, is a foundational result in linear algebra that identifies the best low-rank approximation of a matrix. Introduced in 1936 by Carl Eckart and Gale Young, with Mendelsohn’s later contributions sometimes noted, the theorem provides a constructive solution to approximating a matrix with a matrix of smaller rank.

Statement of the theorem: Let A be an m-by-n matrix with singular value decomposition A = U Σ V^T, where Σ = diag(σ1, σ2, ..., σr) contains the nonzero singular values in nonincreasing order (r = rank(A)). For any integer k in {0, 1, ..., r}, the closest matrix to A among all matrices of rank at most k, with respect to the Frobenius norm, is given by A_k = U_k Σ_k V_k^T. Here U_k and V_k consist of the first k columns of U and V, and Σ_k is diag(σ1, ..., σk). The approximation error satisfies ||A − A_k||_F = sqrt(σ_{k+1}^2 + ... + σ_r^2). The same truncation also yields the closest rank-k approximation in the spectral norm, with the error equal to σ_{k+1}.

Significance and applications: The theorem provides a rigorous justification for low-rank approximations used in data compression, principal component analysis, image compression, and various numerical methods. It underpins why truncating the Singular Value Decomposition yields optimal representations under common norms.

See also: singular value decomposition, principal component analysis, low-rank approximation.