How much can you discard?

Source scope: §3.15, PDF pages 24, 25. Numerical examples, experiments, added derivations, and practice are teaching supplements unless identified as source results.

Keep the largest effects

Suppose a matrix has singular values $4,2,1$. Keeping only the first term gives a rank-one approximation. Its largest omitted stretch is $2$; its squared Frobenius error is $2^2+1^2=5$. Keeping the second term reduces those errors to $1$ and $1$.

Theorem 5 (Eckart–Young–Mirsky). Let $\|\cdot\|$ be a unitarily invariant matrix norm. Suppose $A\in\mathbb R^{m\times n}$ with $m\ge n$ has SVD $A=\sum_{i=1}^n\sigma_i u_iv_i^T$. For an integer $0\le k\le\operatorname{rank}(A)$, define

Then $\|A-A_k\|\le\|A-\widetilde A\|$ for every $m\times n$ matrix $\widetilde A$ with rank at most $k$. “Best rank-$k$” means an allowed rank of at most $k$, not a claim of uniqueness. Repeated singular values can yield multiple best approximations. The source omits the general proof and proves only the spectral-norm case. For $m<n$, apply the result to $A^T$ and transpose back (teaching extension).

Source proof for the spectral norm

For $k<n$, the omitted SVD terms give

Let $\operatorname{rank}(\widetilde A)\le k$. Rank–nullity gives $\dim\operatorname{null}(\widetilde A)\ge n-k$. The space $S=\operatorname{span}(v_1,\ldots,v_{k+1})$ has dimension $k+1$. Their dimensions sum to at least $n+1$, so their intersection cannot be zero in $\mathbb R^n$. Choose a unit vector $z$ in that intersection. Write $z=\sum_{i=1}^{k+1}\alpha_i v_i$; orthonormality gives $\sum_i\alpha_i^2=1$.

Since $\widetilde Az=0$ and $v_i^Tz=\alpha_i$ for $i\le k+1$, we get

The first inequality tests one unit input in a maximum over all inputs. Pythagoras gives the next square root; ordering the singular values gives the lower bound. This completes the proof. At $k=n$ the intersection argument is unnecessary: $A_k=A$ and its error is zero. This boundary clarification avoids referring to a nonexistent $v_{n+1}$.

Energy, error, and storage

The source measures retained squared Frobenius energy by

For $4,2,1$, rank one retains $16/21$, while rank two retains $20/21$. For the zero matrix this ratio is $0/0$ and is undefined; its reconstruction error is still zero.

Teaching supplement. Storing $U_k$, the $k$ singular values, and $V_k$ uses $k(m+n+1)$ scalar entries instead of $mn$. Small matrices may take more storage in factor form. The experiment reconstructs an original synthetic grayscale image with a known SVD; its cells are matrix entries, not samples from an external photograph. Squared Frobenius error equals omitted energy, while spectral error is the largest omitted singular value. High energy retention does not guarantee that every visually important feature survives.

Transfer

For singular values $5,5,0$, rank one retains half the energy and has spectral error $5$. The repeated leading values explain why selecting a particular first singular direction need not give the only optimum.

Explore the relationship