Why is the truncated SVD the best rank-k approximation of a matrix?

## The matrix as a sum of layers Multiplying out `A = U S V^T` gives `A = sigma_1 u_1 v_1^T + sigma_2 u_2 v_2^T + ... + sigma_r u_r v_r^T` where r is the rank and each term is a rank-1 matrix: an outer product of a left and a right singular vector, scaled by a singular value. The terms are ordered by decreasing sigma, so the sum lists the matrix's structure from most to least important. Truncating after k terms defines `A_k = sum from i = 1 to k of sigma_i u_i v_i^T` which has rank k (assuming `sigma_k > 0`). ## Eckart-Young The **Eckart-Young theorem** (extended to all unitarily invariant norms by Mirsky) states that A_k is a *global minimizer* of the approximation error over the entire set of matrices of rank at most k: `||A - A_k|| <= ||A - B||` for every B with rank(B) <= k This holds in the Frobenius norm (the entrywise root-sum-of-squares) and in the spectral norm (the largest singular value of the difference). The remarkable part is that the same truncation is optimal for both, and that you get it by *deleting terms* rather than by solving an optimization problem. There is nothing to fit or tune. The errors are known in closed form: - `||A - A_k||_F = sqrt(sigma_{k+1}^2 + sigma_{k+2}^2 + ... + sigma_r^2)` - `||A - A_k||_2 = sigma_{k+1}` Both follow immediately from the fact that `A - A_k` is itself the SVD sum of the discarded layers, so its singular values are precisely the discarded singular values. ## Why deleting the smallest works The layers are mutually orthogonal: the left singular vectors are orthonormal and so are the right ones, so different rank-1 terms do not interfere. Energy therefore adds in squares, `||A||_F^2 = sigma_1^2 + ... + sigma_r^2`, and every layer contributes independently. Discarding a layer costs exactly its squared singular value and nothing more, so removing the smallest ones is the cheapest way to shed r - k layers. Any other rank-k matrix has to spend its budget of k directions somewhere, and no other choice of directions captures more energy than the leading singular directions. ## What it buys in storage For an m-by-n matrix the truncated form stores k left singular vectors of length m, k right singular vectors of length n, and k singular values: `k(m + n + 1)` numbers versus `m n` for the full matrix. A grayscale image of 1000 by 1000 pixels holds 1,000,000 numbers; at k = 50 the truncated form holds 50 * 2001 = 100,050, about a tenth, and the image is often still recognisable, because most of the picture's energy sits in the first few dozen singular values. The break-even is `k(m + n + 1) = m n`, so once k approaches the smaller dimension the representation saves nothing. ## When it does not help Everything above is optimal, but optimal is not the same as good. If the spectrum is flat, meaning `sigma_1` through `sigma_r` are comparable in size, then the discarded tail is large for any k well below r and the best rank-k approximation is still a bad approximation. The theorem tells you the error exactly; it does not promise the error is small. Deciding whether a matrix has exploitable low-rank structure means looking at how fast the singular values decay, not at the theorem. ## Uniqueness A_k is the unique minimizer when `sigma_k > sigma_{k+1}`. If those two are equal there is a tie over which layer to keep, and several distinct rank-k matrices attain the same minimal error. The minimum error value is unique regardless. ## Common mistakes Calling truncation a heuristic with no guarantee; reporting the Frobenius error as the plain sum of the discarded singular values instead of the root of the sum of their squares; confusing dropping small singular values with dropping rows or columns of the matrix, which is a completely different and generally much worse approximation; and assuming a low-rank form always saves space regardless of k and the matrix shape.