the Eckart-Young theorem
/ EK-art YUNG /
When you compress a matrix by keeping its top-k singular triplets (truncated SVD), a natural worry nags: is this really the BEST you can do with rank k, or might some cleverer rank-k matrix be closer to the original? The Eckart-Young theorem settles it with a clean and surprisingly strong answer: there is no cleverer choice. Among ALL matrices of rank at most k, the truncated SVD is the closest one to A. This is the theorem that elevates the SVD from a useful factorization to THE tool for low-rank approximation, with a guarantee of optimality.
Precisely: let A = sum sigma_i u_i v_i^T be the SVD, and let A_k = sum_{i=1}^{k} sigma_i u_i v_i^T be the truncation to the top k terms. Then for any matrix B of rank at most k, ||A - B|| >= ||A - A_k||, and the minimum is achieved by A_k. Moreover the theorem tells you EXACTLY how good the best approximation is: in the 2-norm the error equals the first discarded singular value, ||A - A_k||_2 = sigma_{k+1}, and in the Frobenius norm it is the square root of the sum of all the discarded singular values squared, sqrt(sigma_{k+1}^2 + sigma_{k+2}^2 + ...). So the singular values you throw away are not just an estimate of the error — they ARE the error. (The Frobenius-norm version is sometimes credited to Mirsky, hence Eckart-Young-Mirsky.)
This is the theoretical bedrock under PCA, image and signal compression, noise reduction, latent semantic analysis, recommender systems, and reduced-order modeling — every one of them is, at heart, an Eckart-Young best low-rank approximation. It also tells you how to CHOOSE the rank: look at the singular values, find where they drop off a cliff, and cut there, because sigma_{k+1} is your guaranteed approximation error. The honest limits: optimality holds for the 2-norm and Frobenius norm (unitarily invariant norms), not necessarily for other measures of fit; and it is optimality in a least-squares sense, which can be skewed by outliers — robust low-rank approximation under other loss functions is a harder, separate problem. But within its scope, Eckart-Young is one of the cleanest optimality results in all of applied mathematics.
Suppose A has singular values 50, 30, 5, 0.2, 0.1. The best rank-2 approximation keeps the 50 and 30 triplets; Eckart-Young guarantees its 2-norm error is exactly sigma_3 = 5, and its Frobenius error is sqrt(5^2 + 0.2^2 + 0.1^2) ~= 5.005. No rank-2 matrix beats this. If instead you want error below 1, you need rank 3 (then the 2-norm error is sigma_4 = 0.2). The singular values directly read off both the achievable accuracy and the rank required.
The truncated SVD is provably the best rank-k approximation, and the discarded singular values ARE the approximation error.
Optimality is in the 2-norm and Frobenius norm (unitarily invariant norms) and in a least-squares sense — it is NOT guaranteed under other loss functions, and it is sensitive to outliers, which is why robust/sparse low-rank methods exist. Also, the best rank-k approximation is unique only when sigma_k is strictly greater than sigma_{k+1}; a tie leaves freedom in the choice.