Low-rank Approximation

The Low-Rank Structure unit studies matrices that are close to matrices of much smaller rank and uses the SVD to find the closest one. We met the SVD in the Decompositions lecture as a way to factor any matrix, and last lecture’s double-descent spike turned out to be a story about the smallest singular values. Today we discard the smallest singular values and prove that the resulting approximation is optimal. For a rank budget \(k\), truncated SVD keeps the \(k\) largest terms and drops the rest. The Eckart–Young–Mirsky theorem proves that this choice minimizes the approximation error and expresses the minimum using the discarded singular values.

Truncating the SVD

Recall the outer-product form of the SVD from the Decompositions lecture. Any matrix \(\mathbf{A}\in\mathbb{R}^{n\times d}\) of rank \(r\) splits into a sum of \(r\) rank-one pieces: \[ \mathbf{A} = \sum_{i=1}^r \sigma_i \mathbf{u}_i\mathbf{v}_i^\top , \] with singular values \(\sigma_1\geq\sigma_2\geq\cdots\geq\sigma_r>0\), orthonormal left singular vectors \(\mathbf{u}_i \in \mathbb{R}^n\), and orthonormal right singular vectors \(\mathbf{v}_i \in \mathbb{R}^d\). Each term is a full \(n\times d\) matrix built from one pair of directions and scaled by \(\sigma_i\). The rank-\(k\) truncated SVD keeps the \(k\) largest of those pieces: \[ \mathbf{A}_k = \sum_{i=1}^k \sigma_i \mathbf{u}_i \mathbf{v}_i^\top . \] As long as \(k\leq r\), the matrix \(\mathbf{A}_k\) has rank exactly \(k\), since its columns are combinations of the \(k\) independent directions \(\mathbf{u}_1,\ldots,\mathbf{u}_k\). It is assembled from the directions along which \(\mathbf{A}\) stretches the most, so it is a sensible guess at the best rank-\(k\) approximation.

This construction is not yet a proof of optimality. The best \(k\) directions considered jointly need not be the \(k\) individually largest ones, and a competing rank-\(k\) matrix can use directions that are not singular vectors. Optimality requires a measure of the distance between two matrices.

The Eckart–Young–Mirsky Theorem

The usual way to measure the size of a matrix is the Frobenius norm, which treats the matrix as one long vector of its \(nd\) entries: \[ \|\mathbf{M}\|_F^2 = \sum_{i=1}^n\sum_{j=1}^d \big[\mathbf{M}\big]_{i,j}^2 . \] So \(\|\mathbf{A}-\mathbf{B}\|_F\) squares every entry the approximation gets wrong and adds them up, in the same way mean squared error scores a vector of predictions. (The other standard choice is the spectral norm \(\|\mathbf{M}\|_2\) from the Depth-enablers lecture, the largest factor by which \(\mathbf{M}\) stretches any vector, which counts only the worst direction rather than all of them.)

The SVD makes this norm easy to compute, because the rank-one pieces are orthonormal under the Frobenius inner product \(\langle \mathbf{M},\mathbf{N}\rangle_F = \mathrm{trace}(\mathbf{M}^\top\mathbf{N})\): \[ \langle \mathbf{u}_i\mathbf{v}_i^\top, \mathbf{u}_j\mathbf{v}_j^\top\rangle_F = (\mathbf{u}_i^\top\mathbf{u}_j)(\mathbf{v}_i^\top\mathbf{v}_j) = \begin{cases} 1 & i = j \\ 0 & i \neq j \end{cases} \] by orthonormality of the singular vectors. A sum of orthogonal pieces has squared length equal to the sum of the squared lengths, which is the Pythagorean theorem applied in the space of matrices: \[ \|\mathbf{A}\|_F^2 = \Big\|\sum_{i=1}^r \sigma_i\mathbf{u}_i\mathbf{v}_i^\top\Big\|_F^2 = \sum_{i=1}^r \sigma_i^2 . \] This total is called the energy of \(\mathbf{A}\). Direction \(i\) contributes \(\sigma_i^2\), and orthogonality makes the contributions add without cross terms.

Claim (Eckart–Young–Mirsky, Frobenius case): Among all matrices \(\mathbf{B}\in\mathbb{R}^{n\times d}\) of rank at most \(k\), the truncated SVD \(\mathbf{A}_k\) minimizes \(\|\mathbf{A}-\mathbf{B}\|_F\), and the error it achieves is the energy of the discarded directions: \[ \|\mathbf{A}-\mathbf{A}_k\|_F = \sqrt{\sum_{i=k+1}^r \sigma_i^2}. \] (The same \(\mathbf{A}_k\) is optimal in the spectral norm too, with \(\|\mathbf{A}-\mathbf{A}_k\|_2=\sigma_{k+1}\).) Problem 15 takes this worst-case result as given and asks what changes when approximation error is weighted by the input distribution instead.

Proof of Claim

Achievability. The error of the truncation is exactly the pieces we dropped, \(\mathbf{A}-\mathbf{A}_k = \sum_{i=k+1}^r \sigma_i\mathbf{u}_i\mathbf{v}_i^\top\), so the energy identity applied to that shorter sum gives: \[ \|\mathbf{A}-\mathbf{A}_k\|_F^2 = \sum_{i=k+1}^r \sigma_i^2 . \] The truncation keeps the energy of the top \(k\) directions and loses the energy of every direction it discarded.

Optimality. A matrix of rank \(k\) has columns in some \(k\)-dimensional subspace. For a fixed subspace, projecting the columns of \(\mathbf{A}\) onto it gives the smallest error, so the optimization selects the subspace that retains the most energy.

Fix any matrix \(\mathbf{B}\) of rank at most \(k\), let \(S = \mathrm{col}(\mathbf{B}) \subseteq \mathbb{R}^n\) be its column space, of dimension at most \(k\), and let \(\mathbf{P}\) be the orthogonal projection onto \(S\). Every column of \(\mathbf{B}\) lies in \(S\), and the closest point of \(S\) to a given vector is its projection, which is the perpendicular-dropping argument from the Linear Model lecture applied one column at a time: \[ \|\mathbf{A}-\mathbf{B}\|_F^2 = \sum_{j=1}^d \big\|[\mathbf{A}]_{,j} - [\mathbf{B}]_{,j}\big\|^2 \geq \sum_{j=1}^d \big\|[\mathbf{A}]_{,j} - \mathbf{P}[\mathbf{A}]_{,j}\big\|^2 = \|\mathbf{A}-\mathbf{P}\mathbf{A}\|_F^2 , \] where the first and last equalities are the Frobenius norm read column by column. So we may as well take \(\mathbf{B} = \mathbf{P}\mathbf{A}\) and search over subspaces instead of over matrices. The residual \(\mathbf{A}-\mathbf{P}\mathbf{A}\) is orthogonal to \(\mathbf{P}\mathbf{A}\) under the Frobenius inner product, so Pythagoras splits the error again: \[ \|\mathbf{A}-\mathbf{P}\mathbf{A}\|_F^2 = \|\mathbf{A}\|_F^2 - \|\mathbf{P}\mathbf{A}\|_F^2 . \] The first term does not depend on \(S\), so minimizing the error is the same as maximizing \(\|\mathbf{P}\mathbf{A}\|_F^2\), the energy retained by the subspace.

Expand that captured energy in the SVD: \[ \begin{align*} \|\mathbf{P}\mathbf{A}\|_F^2 &= \mathrm{trace}\big(\mathbf{A}^\top\mathbf{P}^\top\mathbf{P}\mathbf{A}\big) \\&= \mathrm{trace}\big(\mathbf{P}\mathbf{A}\mathbf{A}^\top\big) \\&= \sum_{i=1}^r \sigma_i^2\,\mathrm{trace}\big(\mathbf{P}\mathbf{u}_i\mathbf{u}_i^\top\big) \\&= \sum_{i=1}^r \sigma_i^2\,\|\mathbf{P}\mathbf{u}_i\|^2 . \end{align*} \] The first equality writes the Frobenius norm as a trace, the second uses \(\mathbf{P}^\top\mathbf{P} = \mathbf{P}\) (projecting twice is the same as projecting once) together with the cyclic property of the trace, the third substitutes the outer-product form \(\mathbf{A}\mathbf{A}^\top = \sum_i \sigma_i^2\mathbf{u}_i\mathbf{u}_i^\top\) from the Decompositions lecture, and the fourth uses \(\mathrm{trace}(\mathbf{P}\mathbf{u}\mathbf{u}^\top) = \mathbf{u}^\top\mathbf{P}\mathbf{u} = \|\mathbf{P}\mathbf{u}\|^2\).

The captured energy is a weighted sum of the \(\sigma_i^2\), with coefficient \(\|\mathbf{P}\mathbf{u}_i\|^2\) equal to the squared length of direction \(\mathbf{u}_i\) after projection. Those weights obey two constraints. Each is at most \(1\), since a projection never lengthens a vector, and together they add up to at most \(k\): \[ \sum_{i=1}^r \|\mathbf{P}\mathbf{u}_i\|^2 \leq \sum_{i=1}^n \|\mathbf{P}\mathbf{u}_i\|^2 = \mathrm{trace}(\mathbf{P}) = \dim(S) \leq k , \] where we extended \(\mathbf{u}_1,\ldots,\mathbf{u}_r\) to an orthonormal basis of \(\mathbb{R}^n\) (which only adds nonnegative terms) and used that the trace of an orthogonal projection is the dimension it projects onto. The subspace therefore has \(k\) units of weight to hand out, no direction may take more than one unit, and a unit spent on direction \(i\) is worth \(\sigma_i^2\). Since the \(\sigma_i^2\) are sorted, no allocation beats spending a full unit on each of the \(k\) largest: \[ \|\mathbf{P}\mathbf{A}\|_F^2 = \sum_{i=1}^r \sigma_i^2\|\mathbf{P}\mathbf{u}_i\|^2 \leq \sum_{i=1}^k \sigma_i^2 . \] Substituting back, every matrix \(\mathbf{B}\) of rank at most \(k\) satisfies: \[ \|\mathbf{A}-\mathbf{B}\|_F^2 \geq \|\mathbf{A}\|_F^2 - \sum_{i=1}^k\sigma_i^2 = \sum_{i=k+1}^r\sigma_i^2 , \] which is exactly the error the truncation achieves. Choosing \(S = \mathrm{span}(\mathbf{u}_1,\ldots,\mathbf{u}_k)\) meets the bound: it gives weight \(1\) to the top \(k\) directions and \(0\) to the rest, and projecting \(\mathbf{A}=\sum_j\sigma_j\mathbf{u}_j\mathbf{v}_j^\top\) onto that span keeps every term with \(j\leq k\) and kills the others, leaving \(\mathbf{P}\mathbf{A} = \mathbf{A}_k\).

The truncation error depends only on the singular values of the discarded directions, not on the directions themselves. It is zero exactly when \(\mathbf{A}\) already has rank \(k\) or less, and it is large exactly when the spectrum is flat, since then every direction carries a comparable share of the energy and discarding \(r-k\) of them costs a comparable share of it. A competitor may choose any \(k\)-dimensional subspace in \(\mathbb{R}^n\), but no such subspace captures more energy than the one spanned by the top \(k\) singular vectors. The approximation error still depends on the discarded values \(\sigma_{k+1},\ldots,\sigma_r\).

Tail Energy, by Hand

The quantity \(\sqrt{\sum_{i=k+1}^r \sigma_i^2}\) is called the tail energy. We compute it by hand in class. Suppose a \(4\times 4\) matrix has singular values \(\sigma = (10, 6, 3, 1)\). Truncating at \(k=2\) keeps \(\sigma_1,\sigma_2\) and discards \(\sigma_3,\sigma_4\), so the best rank-\(2\) approximation error any matrix can achieve is: \[ \|\mathbf{A}-\mathbf{A}_2\|_F = \sqrt{\sigma_3^2+\sigma_4^2} = \sqrt{9+1} = \sqrt{10} \approx 3.16 . \] Compare this against the total, \(\|\mathbf{A}\|_F = \sqrt{100+36+9+1}=\sqrt{146}\approx 12.08\): the rank-\(2\) approximation captures \(\frac{100+36}{146}\approx 93\%\) of the matrix’s energy while discarding half its rank.

Half the rank is gone and \(93\%\) of the energy survives because the spectrum \((10,6,3,1)\) is top-heavy. The flat spectrum \((6,6,6,6)\) has the same rank and nearly the same total energy, \(144\) against \(146\), and yet truncating it at \(k=2\) keeps only half of that energy, and by the theorem no rank-\(2\) matrix does better. Whether low-rank approximation is worth doing is a question about the shape of the spectrum, not about the size of the matrix.

Compression and Denoising

The spectral shape determines whether truncation is useful for compression and denoising.

Compression. Storing \(\mathbf{A}_k\) means storing \(k\) triples \((\sigma_i,\mathbf{u}_i,\mathbf{v}_i)\), so the storage relative to the original matrix is: \[ \frac{k(n+d+1)}{nd} . \] The ratio is small whenever \(k \ll \min(n,d)\), and the approximation is only faithful when the energy is concentrated in the first few singular values, as it typically is for real images, audio, and video.

Denoising. Suppose \(\mathbf{A}\) is a low-rank signal plus noise spread across many directions. When the signal’s energy is concentrated in the leading singular values and the noise is spread across the spectrum, truncating to rank \(k\) discards more noise than signal.

The class demo runs this exact truncation on a real image and on a video, showing how few singular values it takes to recognize each one.

From Matrices to Data Embeddings

Next lecture points today’s theorem at data. If each data point is a row of a matrix, then a rank-\(k\) approximation of that matrix is a compressed representation of the entire dataset, with every point replaced by \(k\) numbers. When the rows are centered, \(\|\mathbf{A}\|_F^2\) is \(n\) times the total variance in the data, so today’s “energy captured by the top \(k\) directions” is next lecture’s “variance explained by the top \(k\) components.” That technique is principal component analysis, and Eckart–Young–Mirsky is the reason it is the reconstruction-optimal linear embedding. The two lectures after it truncate different matrices: the update to a weight matrix during finetuning (LoRA), and the gradient itself before a step is taken (Muon).

For any retained rank \(k\), the error of the best approximation is the tail energy of the discarded singular values.