Eckart-Young Optimality in the Frobenius Norm

The Approximation Problem

A matrix can contain many directions of variation even when we want a simpler representation using only a few. The truncated singular value decomposition gives a natural way to retain the most significant singular directions. The Eckart–Young theorem establishes more than the usefulness of that construction: among every matrix of rank at most \(k\), the truncation has the smallest possible Frobenius-norm error.

Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\), and set \(q=\min(m,n)\). Its singular values are ordered \(\sigma_1\ge\cdots\ge\sigma_q\ge0\). In a full singular value decomposition (SVD), \(\mathbf{A}=\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{\top}\), where \(\mathbf{U}\in\mathbb{R}^{m\times m}\) and \(\mathbf{V}\in\mathbb{R}^{n\times n}\) are orthogonal. The \(m\times n\) matrix \(\boldsymbol{\Sigma}\) has the singular values on its diagonal and zero elsewhere. Write \(\mathbf{u}_i\) and \(\mathbf{v}_i\) for the corresponding left and right singular vectors. Singular values beyond the rank \(r=\operatorname{rank}\mathbf{A}\) are zero.

The optimization is over matrices of rank at most \(k\), not necessarily rank exactly \(k\). This distinction covers, for example, a matrix \(\mathbf{A}\) whose rank is already less than \(k\). The Frobenius norm treats all entries together; it is not the sum of their absolute values.

Why Orthogonal Coordinates Preserve the Error

The SVD expresses \(\mathbf{A}\) in orthonormal coordinates. To compare an arbitrary candidate \(\mathbf{B}\) with \(\mathbf{A}\), transform both into these coordinates. If \(\mathbf{U}\) and \(\mathbf{V}\) are orthogonal, then \(\mathbf{U}^{\top}\mathbf{U}=\mathbf{I}_m\) and \(\mathbf{V}^{\top}\mathbf{V}=\mathbf{I}_n\).

Proof. The squared Frobenius norm is the sum of the squared Euclidean norms of the columns. Multiplication on the left by \(\mathbf{Q}\) preserves each column norm, because \(\|\mathbf{Q}\mathbf{x}\|^2=\mathbf{x}^{\top}\mathbf{Q}^{\top}\mathbf{Q}\mathbf{x}=\|\mathbf{x}\|^2\). It is also the sum of the squared norms of the rows. Multiplication on the right by \(\mathbf{R}\) preserves each row norm: for a row \(\mathbf{x}^{\top}\), \(\|\mathbf{x}^{\top}\mathbf{R}\|^2=\mathbf{x}^{\top}\mathbf{R}\mathbf{R}^{\top}\mathbf{x}=\|\mathbf{x}\|^2\). Applying these two facts gives the claimed equality. \(\square\)

For any candidate \(\mathbf{B}\), set \(\mathbf{C}=\mathbf{U}^{\top}\mathbf{B}\mathbf{V}\). Orthogonal invariance gives \(\|\mathbf{A}-\mathbf{B}\|_F=\|\boldsymbol{\Sigma}-\mathbf{C}\|_F\). Also, \(\operatorname{rank}\mathbf{C}=\operatorname{rank}\mathbf{B}\): multiplication on the right by \(\mathbf{V}\) does not change the image, since \(\mathbf{V}\) maps onto \(\mathbb{R}^n\), and multiplication on the left by \(\mathbf{U}^{\top}\) preserves the dimension of that image. Thus the problem reduces to approximating the diagonal-shaped matrix \(\boldsymbol{\Sigma}\) by a low-rank matrix \(\mathbf{C}\).

The Energy Bound for a Rank Constraint

We need a bound on how much of \(\mathbf{A}\)'s squared Frobenius norm can lie in a subspace of dimension at most \(k\). Let \(\mathbf{P}\) be the orthogonal projection onto the column space of \(\mathbf{C}\). Then \(\mathbf{P}\mathbf{C}=\mathbf{C}\), and \(\operatorname{rank}\mathbf{P}=\operatorname{rank}\mathbf{C}\le k\). The residual \(\boldsymbol{\Sigma}-\mathbf{C}\) contains a component perpendicular to this column space; that component cannot be removed by choosing \(\mathbf{C}\).

Proof. First suppose \(k=0\). Then \(\mathbf{P}=\mathbf{O}\), so the left side and the empty sum are both zero. Now suppose \(k\ge1\). Pad the singular values with zeros to obtain \(\lambda_i=\sigma_i^2\) for \(i\le q\) and \(\lambda_i=0\) for \(q<i\le m\). These numbers satisfy \(\lambda_1\ge\cdots\ge\lambda_m\ge0\). Define \(\alpha_i=\|\mathbf{P}\mathbf{u}_i\|^2\) for the \(m\) orthonormal columns of \(\mathbf{U}\). Orthogonal projection gives \(0\le\alpha_i\le1\). Moreover, if \(\mathbf{w}_1,\dots,\mathbf{w}_d\) is an orthonormal basis for the range of \(\mathbf{P}\), then \(\mathbf{P}\mathbf{u}_i=\sum_{j=1}^{d}(\mathbf{w}_j^{\top}\mathbf{u}_i)\mathbf{w}_j\). Therefore \(\sum_{i=1}^{m}\alpha_i=\sum_{j=1}^{d}\sum_{i=1}^{m}(\mathbf{w}_j^{\top}\mathbf{u}_i)^2=\sum_{j=1}^{d}\|\mathbf{w}_j\|^2=d\le k\), where the inner sum equals \(\|\mathbf{w}_j\|^2\) because the columns of \(\mathbf{U}\) are an orthonormal basis.

Using \(\mathbf{A}=\sum_{i=1}^{q}\sigma_i\mathbf{u}_i\mathbf{v}_i^{\top}\) and the orthonormality of the \(\mathbf{v}_i\), expansion of the Frobenius norm gives \(\|\mathbf{P}\mathbf{A}\|_F^2=\sum_{i=1}^{m}\lambda_i\alpha_i\). For \(i>k\), \(\lambda_i\le\lambda_k\). Hence \(\sum_{i=1}^{m}\lambda_i\alpha_i\le\sum_{i=1}^{k}\lambda_i\alpha_i+\lambda_k\sum_{i=k+1}^{m}\alpha_i\). Since \(\sum_i\alpha_i\le k\), the last expression is at most \(k\lambda_k+\sum_{i=1}^{k}(\lambda_i-\lambda_k)\alpha_i\). Each \(\lambda_i-\lambda_k\ge0\), and \(\alpha_i\le1\), so this is at most \(k\lambda_k+\sum_{i=1}^{k}(\lambda_i-\lambda_k)=\sum_{i=1}^{k}\lambda_i=\sum_{i=1}^{k}\sigma_i^2\). This proves the bound. \(\square\)

The Eckart–Young Theorem in Frobenius Norm

Proof. For any \(\mathbf{B}\) with rank at most \(k\), transform to SVD coordinates by setting \(\mathbf{C}=\mathbf{U}^{\top}\mathbf{B}\mathbf{V}\). Let \(\mathbf{P}\) project orthogonally onto \(\operatorname{Col}\mathbf{C}\). Then \((\mathbf{I}_m-\mathbf{P})\mathbf{C}=\mathbf{O}\), so \((\mathbf{I}_m-\mathbf{P})(\boldsymbol{\Sigma}-\mathbf{C})=(\mathbf{I}_m-\mathbf{P})\boldsymbol{\Sigma}\). For each column, the projections onto the range of \(\mathbf{P}\) and its perpendicular space are orthogonal. Adding the squared column norms gives \(\|\boldsymbol{\Sigma}-\mathbf{C}\|_F^2\ge\|(\mathbf{I}_m-\mathbf{P})\boldsymbol{\Sigma}\|_F^2\). Orthogonal decomposition also gives \(\|(\mathbf{I}_m-\mathbf{P})\mathbf{A}\|_F^2=\|\mathbf{A}\|_F^2-\|\mathbf{P}\mathbf{A}\|_F^2\). The same identity holds for \(\boldsymbol{\Sigma}\), since the SVD preserves the Frobenius norm. The lemma and \(\|\mathbf{A}\|_F^2=\sum_{i=1}^{q}\sigma_i^2\) therefore imply \(\|\mathbf{A}-\mathbf{B}\|_F^2\ge\sum_{i=1}^{q}\sigma_i^2-\sum_{i=1}^{k}\sigma_i^2=\sum_{i=k+1}^{q}\sigma_i^2\). Finally, \(\mathbf{A}-\mathbf{A}_k=\sum_{i=k+1}^{q}\sigma_i\mathbf{u}_i\mathbf{v}_i^{\top}\). The matrices \(\mathbf{u}_i\mathbf{v}_i^{\top}\) have Frobenius norm \(1\) and are pairwise orthogonal in the Frobenius inner product, because both singular-vector lists are orthonormal. Thus \(\|\mathbf{A}-\mathbf{A}_k\|_F^2=\sum_{i=k+1}^{q}\sigma_i^2\). The truncation attains the lower bound, proving it is a minimizer. \(\square\)

The theorem identifies the minimum error, not necessarily a unique minimizer. When a singular value at the truncation boundary is repeated, different choices of directions within its singular subspace can yield the same error. The guaranteed conclusion is that truncation is optimal.

Worked Applications

Common Mistake and Why the Result Matters

Common mistake: adding discarded singular values instead of their squares. For the first example, one might incorrectly claim the best error is \(\sigma_2+\sigma_3=3+1=4\). But the actual residual is diagonal with entries \(0,3,1\), so its Frobenius norm is \(\sqrt{0^2+3^2+1^2}=\sqrt{10}\), not \(4\). Frobenius errors combine squared entry sizes; the theorem therefore uses the square root of the sum of the squares of the discarded singular values.

The proof explains the optimality in two parts. Orthogonal changes of coordinates preserve the error, so the SVD lets us examine the singular directions directly. Then a rank-\(k\) candidate can capture at most the energy in the \(k\) largest singular directions; the lemma proves that bound even when the candidate uses directions that do not coincide with the singular vectors. The discarded energy is consequently unavoidable. This gives a precise benchmark for any low-rank approximation: no rank-\(k\) matrix can have a smaller Frobenius error than the truncated SVD.