All matrices below are real and finite-dimensional. The proof uses the singular value decomposition and the orthogonality facts developed earlier in the course.
Two ways to measure an approximation
Suppose is replaced by a simpler matrix of rank at most . The two norms below answer different questions, even though the same truncated SVD will minimize both.
Definition 4.4.1
(Spectral norm, Frobenius norm and truncated SVD)
For , the spectral norm is , the worst stretch over unit inputs. The Frobenius norm is , the square root of the combined squared entries.
Take a full SVD with singular values , , and orthonormal singular vectors . The rank- truncation is
The empty sum is zero. Each summand has rank at most one, so . The spectral norm is controlled by one direction only, while the Frobenius norm adds up every discarded direction; that is why the two minimum errors look different in the statement below.
Theorem 4.4.2
(Eckart–Young best low-rank approximation)
Let and be as above. For every with ,
When , and both minimum errors are zero.
The proof has three parts: compute the errors of the candidate , prove the spectral lower bound, and prove the Frobenius lower bound. These are approximation statements; dropping a small singular value changes the matrix and may change an inverse problem.
First compute the error of the candidate
Lemma 4.4.3
(Error of the truncation)
For , , and for , .
Proof
(Errors of the candidate in singular coordinates)
Orthogonal changes of coordinates preserve Euclidean lengths and the Frobenius norm. For Frobenius, one direct proof is and for orthogonal ; left orthogonal multiplication is similar. In singular coordinates, is diagonal-rectangular with remaining entries . Its Frobenius norm squared is their squared sum. For a diagonal-rectangular matrix the largest stretch of a unit vector is its largest diagonal magnitude: an upper bound follows by summing squares, and choosing the matching coordinate vector attains it. Thus its spectral norm is when .
Why no other rank- matrix improves the worst case
Proof
(Spectral lower bound by a vanishing vector)
Suppose . Let , of dimension . The restriction of to has image dimension at most . Rank–nullity therefore gives a nonzero with ; normalize . Writing , orthonormality gives and
The spectral norm is the maximum over all unit inputs, so it is at least . The candidate achieves that lower bound. This dimension argument remains valid if some singular values are zero or repeated; no inverse of is assumed.
Proof X-ray
Where the spectral bound comes from
Two facts carry the argument. First, has dimension while has rank at most , so the restriction cannot be injective; this is the only place the rank hypothesis on is used. Second, on the coefficients are all at least , because the singular values are ordered; this is the only place the ordering is used. The non-obvious move is to choose the test vector inside rather than to compare with directly: the unknown matrix then disappears from . The argument closes because the lower bound equals the error of , whose kernel contains . If had only dimensions, could be injective on it and no nonzero with would be forced.
Why the sum of squared errors is also minimal
Proof
(Frobenius lower bound by projecting onto the row space)
Let be the row space of and the orthogonal projection onto . Then and . The two matrices and are orthogonal in the Frobenius inner product: their trace product contains . Consequently
Extend to an orthonormal basis of , and set for . Put . Orthogonal projection gives , and . In the basis,
The second identity holds because for and the remaining lie in the kernel; equivalently take traces in the SVD basis.
For , ordering the singular values gives
The middle inequality uses . Rearranging (3) now yields . For , and the same bound is immediate. Together with (2), this proves the Frobenius inequality in (1). The proof does not assume the best matrix shares singular vectors with ; it applies to every admissible .
Counterexample mode
Keeping the largest column is not the best rank-one approximation
A tempting shortcut claims that, for a rank-one approximation, one may keep the column of largest norm and set the others to zero. Take . Then has characteristic polynomial , so and . By (1), every rank-one has and . The second column has the larger norm. Keeping it gives , of rank one, with , so both errors equal . The shortcut is not optimal; the truncated SVD uses the singular directions , not the coordinate columns of .
Worked examples
Worked example 4.4.4
(Distinguishing the two errors)
Let . Find a best rank-one approximation and its error in both norms; repeat for rank at most two.
The displayed diagonal entries are the singular values in descending order. A best rank-one approximation is . Its error is , so while . For rank at most two, and both errors equal . The theorem proves these values are minimal among all matrices of the indicated rank, not merely among diagonal candidates.
Worked example 4.4.5
(Repeated singular values and non-uniqueness)
For , exhibit two different best rank-one approximations and compute their errors.
Take and . Both have rank one. Their errors have diagonal entries and respectively; each has spectral norm and Frobenius norm . Formula (1) proves both are best in both norms. A tie between the first two singular values allows different singular directions to be retained; uniqueness cannot be inferred from the phrase “a truncated SVD.”
Worked example 4.4.6
(The extreme ranks zero and full)
For take and .
For the only approximant is , so the error is itself: and , matching (1) with . For the truncation is and both errors are zero; the spectral formula is not used here because there is no singular value .
Common mistakes
Common mistake
(Expecting the same error in both norms)
For and the spectral error is but the Frobenius error is . The truncation is optimal in both norms, but the optimal values are different numbers: the spectral error reports only the largest discarded value, the Frobenius error all of them.
Quick checks
Quick check
(A matrix has singular values . What are the spectral and Frobenius errors of its best rank-one approximation?)
Discard .
Solution · Answer
By (1) with , the spectral error is and the Frobenius error is .
Quick check
(A matrix has rank . For which with is the spectral error of equal to zero?)
Which singular values vanish?
Solution · Answer
Here and , . For the spectral error is , and gives . For the errors are . So and .
Quick check
(For , can a matrix of rank one satisfy ?)
Compare with .
Solution · Answer
No. By (1) with , every rank-at-most-one has . The bound is attained by and also by .