Eckart-Young Optimality in the Operator Norm

The Operator-Norm Approximation Problem

A low-rank approximation replaces a matrix by one whose columns and rows carry fewer independent directions. The truncated singular value decomposition (SVD) supplies a natural candidate: keep the terms associated with the largest singular values and discard the rest. To establish that this candidate is optimal in operator norm, it is not enough to calculate its error. We must also show that no matrix of the permitted rank can have a smaller error.

Throughout, let \(\mathbf{A}\in\mathbb{R}^{m\times n}\), and write \(q=\min(m,n)\). Its singular values are ordered \(\sigma_1\geq\cdots\geq\sigma_q\geq0\). We use the standard SVD form \(\mathbf{A}=\sum_{i=1}^{q}\sigma_i\mathbf{u}_i\mathbf{v}_i^{\top}\), where the \(\mathbf{u}_i\) are orthonormal left singular vectors and the \(\mathbf{v}_i\) are orthonormal right singular vectors. The right singular vectors can be extended to an orthonormal basis of \(\mathbb{R}^n\); directions beyond the \(q\) displayed terms contribute zero to \(\mathbf{A}\).

The rank of a matrix is the dimension of its column space. Since \(\mathbf{A}_k\) is a sum of at most \(k\) rank-one matrices, its rank is at most \(k\). The optimization question is whether this candidate minimizes \(\|\mathbf{A}-\mathbf{B}\|_2\) over all \(\mathbf{B}\) with rank at most \(k\). The answer is yes, and the minimum error is \(\sigma_{k+1}\).

Why the Truncated SVD Has Error \(\sigma_{k+1}\)

First consider the error made by the truncated SVD itself. Subtracting the retained terms leaves precisely the discarded SVD terms:

For any unit vector \(\mathbf{x}\), express its coordinates in an orthonormal basis of right singular vectors. If \(x_i=\mathbf{v}_i^{\top}\mathbf{x}\), orthonormality of the left singular vectors gives \(\|(\mathbf{A}-\mathbf{A}_k)\mathbf{x}\|^2=\sum_{i=k+1}^{q}\sigma_i^2x_i^2\). Each \(\sigma_i\) in this sum is at most \(\sigma_{k+1}\). Consequently, the squared norm is at most \(\sigma_{k+1}^2\sum_{i=k+1}^{q}x_i^2\leq\sigma_{k+1}^2\|\mathbf{x}\|^2\). If \(k<q\) and \(\sigma_{k+1}>0\), taking \(\mathbf{x}=\mathbf{v}_{k+1}\) attains this bound. If \(\sigma_{k+1}=0\), every term in the residual is zero. Thus \(\|\mathbf{A}-\mathbf{A}_k\|_2=\sigma_{k+1}\).

Proof. The case \(k\geq q\) is immediate: \(\operatorname{rank}\mathbf{A}\leq q\leq k\), so choosing \(\mathbf{B}=\mathbf{A}\) gives error zero, and \(\sigma_{k+1}=0\). Now suppose \(0\leq k<q\), and let \(\mathbf{B}\) be any matrix of rank at most \(k\). Let \(L=\operatorname{span}\{\mathbf{v}_1,\ldots,\mathbf{v}_{k+1}\}\), which has dimension \(k+1\) because these right singular vectors are orthonormal. Restrict the linear map defined by \(\mathbf{B}\) to \(L\). Its image has dimension at most \(\operatorname{rank}\mathbf{B}\leq k\). By the Rank-Nullity Theorem, the restriction has a nonzero vector in its kernel; choose such an \(\mathbf{x}\in L\) with \(\|\mathbf{x}\|=1\), so \(\mathbf{B}\mathbf{x}=\mathbf{0}\). Write \(\mathbf{x}=\sum_{i=1}^{k+1}c_i\mathbf{v}_i\). Orthonormality gives \(\sum_{i=1}^{k+1}c_i^2=1\), and the SVD gives \(\mathbf{A}\mathbf{x}=\sum_{i=1}^{k+1}c_i\sigma_i\mathbf{u}_i\). The left singular vectors are orthonormal, so \(\|\mathbf{A}\mathbf{x}\|^2=\sum_{i=1}^{k+1}c_i^2\sigma_i^2\geq\sigma_{k+1}^2\sum_{i=1}^{k+1}c_i^2=\sigma_{k+1}^2\). Since \(\mathbf{B}\mathbf{x}=\mathbf{0}\), we have \(\|(\mathbf{A}-\mathbf{B})\mathbf{x}\|=\|\mathbf{A}\mathbf{x}\|\geq\sigma_{k+1}\). The definition of operator norm therefore gives \(\|\mathbf{A}-\mathbf{B}\|_2\geq\sigma_{k+1}\). This lower bound holds for every permitted \(\mathbf{B}\), while the truncated SVD has rank at most \(k\) and error exactly \(\sigma_{k+1}\), as shown above. Hence it attains the minimum. \(\square\)

The central step in the lower bound is to find a unit vector that \(\mathbf{B}\) sends to zero while keeping it inside the span of the first \(k+1\) right singular vectors. A rank-at-most-\(k\) map cannot be one-to-one on this \((k+1)\)-dimensional space: its image has dimension at most \(k\), so Rank-Nullity guarantees a nonzero kernel. On the other hand, every unit vector in that span is stretched by \(\mathbf{A}\) by at least \(\sigma_{k+1}\). That tension forces the error of every rank-at-most-\(k\) competitor to be at least \(\sigma_{k+1}\).

Worked Operator-Norm Calculations

Common Pitfall: Using the Wrong Matrix Norm

For the first example, a tempting calculation is to combine the two nonzero residual entries using the square root of the sum of their squares and claim an error of \(\sqrt{3^2+1^2}=\sqrt{10}\). That calculation does not give the operator norm; it gives the Frobenius norm of the residual. The operator norm asks for the largest stretch of a single unit vector. For this diagonal residual, the output on a unit vector is \((0,3x_2,x_3)^{\top}\), and its squared norm is \(9x_2^2+x_3^2\leq9\). The largest stretch is therefore \(3\), not \(\sqrt{10}\). The distinction matters because optimality is a statement about a particular norm, and the operator-norm proof uses a unit vector in the kernel of the restricted competitor.

A second error is to argue only that the truncated SVD has the stated error, then conclude it is optimal. That calculation proves attainability, not minimality. Optimality requires a lower bound applying to every rank-at-most-\(k\) matrix. The null-space argument supplies exactly that missing step.