The best approximation there is

Most results in this subject are inequalities. The forward error is at most κ times the backward error; the growth factor is at most 2ⁿ⁻¹; an eigenvalue moves by at most the size of the perturbation. Bounds, with slack in them, usually a lot of slack.

Eckart and Young’s theorem is not like that. Among all matrices of rank k, the one closest to A in the 2-norm is the one obtained by keeping the k largest singular values of A and discarding the rest, and the distance to it is

‖A − Aₖ‖₂ = σₖ₊₁

with an equals sign. Not bounded by the next singular value: equal to the next singular value.

An equality is a better check than a bound #

The sharpness is not merely aesthetic. It changes what the theorem can be used for.

A bound can only be violated in one direction, so a computation that satisfies it has been weakly tested — half the ways of being wrong would still pass. An equality can be violated in either direction, and a computation that reproduces it to nine digits has been tested about as hard as a figure on this site can be.

So the low-rank figure computes both sides independently. The left side is measured: build Aₖ from the decomposition, subtract it from A, and take the 2-norm of the difference — which itself requires another singular value computation, of a different matrix. The right side is read off the original spectrum. They must agree to 10⁻⁹, and the worst discrepancy across nine values of k is printed on the figure.

The Frobenius norm gives a second equality for free: ‖A − Aₖ‖_F is the square root of the sum of the squares of all the discarded singular values. Two norms, two closed forms, two measurements, and four numbers that have to line up.

And nothing else is closer #

The theorem says Aₖ is the best rank-k approximation, and “best” is a claim about every other rank-k matrix — an infinite set, which cannot be checked by enumeration.

What can be done is to try. Thirty random rank-three matrices are generated, scaled to the same Frobenius norm as A, and their distances to A measured. Every one is further away than the SVD’s rank-three approximation, and the assertion requires it.

That is not a proof and it is not offered as one. It is the check that would catch an implementation in which the singular values were sorted the wrong way, or the wrong columns of U and V were combined, or the reconstruction dropped a factor — all of which would still produce a rank-three matrix, and all of which would fail this immediately.

What the SVD is for #

The decomposition A = UΣVᵀ writes any matrix as a rotation, a scaling along axes, and another rotation. Four things follow, and they are why it is the central object of the subject.

It gives the best low-rank approximation, which is the theorem above, and which is what principal component analysis, latent semantic indexing and image compression all are.

It gives the condition number, σ₁/σₙ, which is the definition used everywhere on this site.

It gives the numerical rank, or rather the spectrum from which the rank decision is made — rank is a decision is about that, and about how the evidence for it degrades.

It gives the least-squares solution in a form that survives rank deficiency: the pseudoinverse, which sets the reciprocals of the discarded singular values to zero rather than to infinity, and which returns the minimum-norm solution when there are many.

Everything in that list is a statement about the singular values, and the singular values are what makes them all the same subject.

Computing it well #

The route this site uses is one-sided Jacobi: orthogonalise the columns of A in pairs by plane rotations until they are mutually orthogonal, at which point their norms are the singular values and the normalised columns are U.

The reason is the small end of the spectrum, and the comparison is stark. On a matrix constructed with κ = 10¹², one-sided Jacobi recovers every singular value with relative error below 4.4·10⁻⁶ — and that floor is the assembly’s rounding, not the method’s. The alternative route through the eigenvalues of AᵀA gets the three smallest wrong by a relative error of 1.0, which is to say they are gone.

Since half of what a spectrum is used for concerns the small end — the rank decision, the condition number, the pseudoinverse — the choice of method is not a matter of taste. It is the difference between answering the question and answering a different one.

The cost is real: Jacobi is several times slower than the bidiagonalisation-plus-QR route that LAPACK runs by default. LAPACK offers gesvj for exactly this reason, and it is the right call when the small singular values matter.

Two routes to the singular values themselves #

The SVD figure carries the same discipline as everything else here, and the second route is a classical identity.

The singular values of A are the square roots of the eigenvalues of AᵀA. That is exactly the route criticised above for accuracy — and as a check it is fine, because the check is on the large singular values where both methods agree to fifteen digits, and it uses a completely different algorithm to get there. On the four-by-three test matrix, each σᵢ² is required to equal the corresponding eigenvalue of AᵀA to 10⁻¹¹.

Separately, A = UΣVᵀ is reconstructed and required to reproduce A to 10⁻¹⁴, and both U and V are required to be orthonormal to 10⁻¹⁴. That is the site’s rule applied to the SVD: a decomposition is not drawn without the numbers that say it decomposes what it was given.

Three checks, three arithmetics. A bug that survived all of them would have to be a bug in the matrix multiplication itself.

Where the approximation is used #

Briefly, because the applications are what make the theorem worth having.

Compression. An m×n matrix costs mn numbers; its rank-k approximation costs k(m+n+1). For an image with a rapidly decaying spectrum that is a large saving with a known, exact error — σₖ₊₁, not an estimate of it.

Denoising. If the signal is low-rank and the noise is not, the noise spreads across all the singular values while the signal concentrates in the first few. Truncating removes most of the noise and little of the signal, and the gap in the spectrum says how well it will work before it is tried.

Dimension reduction. Principal component analysis is the SVD of a centred data matrix, and the proportion of variance explained by k components is the ratio of the sum of the first k squared singular values to the total. The scree plot everybody looks at is the spectrum in the figures on this page.

In all three the same question decides everything: how fast do the singular values decay? A spectrum that falls off a cliff makes the approximation excellent and the rank decision easy. One that decays gently makes both hard, and the gap is what says which case applies.

What is asserted here #

For every k from one to nine: the measured 2-norm error equals σₖ₊₁ to a relative 10⁻⁹, and the measured Frobenius error equals the tail of the spectrum to the same. Two equalities, checked at nine values, by measurements that share no arithmetic with the closed forms.

The Frobenius error must never fall below the 2-norm error, which is a structural inequality that a transposition or an index slip would violate.

Thirty random rank-three matrices must all be further from A than the SVD’s rank-three approximation.

And on the construction side, a matrix built with a prescribed spectrum must return that spectrum: every singular value recovered to a relative 10⁻⁴ at κ = 10¹², with the tolerance bracketed above the assembly’s own noise of 4.4·10⁻⁶ and below the 1.0 that the AᵀA route produces. That bracketing is the point — the tolerance sits between something that cannot fire on correct code and something that would miss the failure it exists to catch, and it is written where it was measured rather than chosen as a round number.

The Frobenius case, and why both norms matter #

Eckart–Young holds in two norms and the two say different things, which is worth separating because applications use both.

In the 2-norm, the error of the best rank-k approximation is σₖ₊₁ — the single largest discarded value. This is a worst-direction statement: it says how badly the approximation can fail for the most unfavourable vector, and it is the right quantity when the matrix is going to be applied to something and the worst case matters.

In the Frobenius norm, the error is the square root of the sum of the squares of all discarded singular values. This is an aggregate statement, and it is the right quantity when the matrix is data and the question is how much of it is retained. The proportion of the squared Frobenius norm kept by the first k terms is exactly the “proportion of variance explained” in a principal component analysis.

Both are checked here, against their closed forms, and the Frobenius error is required never to fall below the 2-norm one — which is a structural inequality that an index error would violate and neither equality alone would catch.

Why the theorem is unusual #

It is worth dwelling on the sharpness, because most of this site is about inequalities with slack in them and the contrast is instructive.

Eckart–Young is an equality because the SVD diagonalises the problem. Once A is written as UΣVᵀ with U and V orthogonal, the distance from A to any matrix is unchanged by removing U and V — the Frobenius and 2-norms are both invariant under orthogonal transformations — so the question reduces to approximating a diagonal matrix by a rank-k one. And for a diagonal matrix the answer is obvious: keep the largest entries.

The whole content of the theorem is the reduction, and the reduction is available because orthogonal transformations preserve the norms. That is the same property that makes orthogonal steps stable in a reflection cannot stop being one, used here for a different purpose: not to avoid amplifying error, but to make a hard optimisation trivial.

What the spectrum’s shape says #

Since the approximation error is exactly the tail of the spectrum, the whole question of “how well can this matrix be approximated” is answered by one plot.

A spectrum that falls off a cliff — a few large values then a drop of many orders of magnitude — means the matrix is essentially low rank, the approximation is excellent, and the rank decision is easy. This is the case for a matrix that is genuinely a sum of a few outer products plus noise.

A spectrum that decays geometrically means the approximation improves steadily with k and there is a real trade-off. This is the common case for smooth kernels and for image data.

A flat spectrum means no low-rank approximation is any good, because discarding any direction costs as much as discarding any other. A random matrix has this shape, which is why random data does not compress.

Reading that shape is the first thing to do with any matrix intended for approximation, and it costs one SVD. Rank is a decision is about the same plot read for a different purpose.

Where the decomposition is unaffordable #

A full SVD costs O(mn²) and is impossible for the matrices that most want approximating. Two routes around it are worth naming, since foundation stops here and the expansion begins there.

Krylov methods — Lanczos bidiagonalisation — compute the largest few singular values and vectors without touching the whole matrix, needing only the ability to multiply by A and Aᵀ. They are what svds does, and they are excellent when k is small and the spectrum has a gap.

Randomised SVD multiplies A by a random matrix with k + p columns, orthogonalises the result, and factorises the much smaller projection. The error bound holds with high probability rather than certainly, and for a matrix with rapid decay it is close to optimal at a fraction of the cost. The probabilistic guarantee is a genuinely different object from anything in this foundation, and it inherits the seeded-generator discipline directly: an error that holds with probability 0.999 is a claim that has to be counted rather than asserted.

Both are in this site’s expansion, and both rest on the theorem measured here: they are approximations to the best approximation, and σₖ₊₁ is what they are being compared against.

Two neighbours complete the field. Rank is a decision is about choosing k, and symmetry is worth more than precision is about the one spectral question where the stability is not automatic. Together with the condition number is an amplifier and the valley with no bottom, they are five essays about the same small number being small.

What the theorem does not say #

Three qualifications, because Eckart–Young is quoted more often than it is bounded.

It is about the 2-norm and the Frobenius norm, and more generally about any unitarily invariant norm. It is not true in the 1-norm or the max-norm, where the best low-rank approximation is a genuinely hard combinatorial problem and the SVD’s answer can be beaten.

It says nothing about structure. If A is nonnegative, or sparse, or has a particular pattern, the best rank-k approximation in the SVD sense will generally have none of those properties. Nonnegative matrix factorisation and sparse PCA exist because the constraint matters more than the optimality, and both are much harder problems for exactly that reason.

It is about approximating the matrix, not about recovering a signal. If A is a low-rank truth plus noise, the best rank-k approximation to A is not the truth — the retained singular values are inflated by the noise, and the retained subspace is rotated away from the true one. How far is a question with a well-developed answer in random matrix theory, and it is a different question from the one the theorem answers.

All three are the same caution in different clothes: the theorem is exactly sharp about a precisely stated question, and the question is “which rank-k matrix is closest to this one”. Anything else requires its own argument.