Low-rank Approximation
Welcome to the Low-Rank Structure unit, four lectures on one observation: the matrices that show up in machine learning are usually close to matrices of much smaller rank, and the SVD is how we 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 throw the smallest ones away instead of dividing by them, and we prove that doing so is the best move available.
The obvious way to spend a rank budget is greedy: keep the \(k\) largest terms of the SVD and drop the rest. Greedy choices are usually decent rather than optimal; today’s theorem says that here greedy is exactly optimal, and the proof explains what makes this problem the exception.
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 a single pair of directions, and \(\sigma_i\) says how much of \(\mathbf{A}\) that one pair accounts for. 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.
It is still a guess, and it should not feel obvious. Nothing so far says that the \(k\) best directions to keep together are the \(k\) that are individually largest, and a competitor is not restricted to the SVD at all: it may hand us any rank-\(k\) matrix, built from directions no singular vector points along. Settling this needs a way to measure how far apart two matrices are.
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}\), and the identity says the singular values divide it up between the directions: direction \(i\) owns \(\sigma_i^2\) of the energy and nothing else owns any of it. Now we can ask the question precisely.
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 proves that second statement with a genuinely different tool, a pigeonhole argument about the dimensions of two subspaces.)
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. Here is the mechanical picture before the algebra. A matrix of rank \(k\) can only place its columns inside some \(k\)-dimensional subspace, so the best it can possibly do is project the columns of \(\mathbf{A}\) onto that subspace, and the whole problem becomes choosing the subspace that catches the most of \(\mathbf{A}\).
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 the subspace catches.
Now expand that captured energy in the SVD, one move per line: \[ \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\).
So the captured energy is a weighted sum of the \(\sigma_i^2\), where direction \(i\) gets the weight \(\|\mathbf{P}\mathbf{u}_i\|^2\), the fraction of the unit vector \(\mathbf{u}_i\) that survives the 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’s error is the energy of every direction it dropped, and nothing else: it depends only on how large their singular values are, not on which directions they were. 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. The proof also answers the objection the greedy guess raised. A competitor may aim its \(k\) dimensions anywhere in \(\mathbb{R}^n\), and that freedom gains nothing, because the energy any \(k\)-dimensional subspace can catch is capped by the \(k\) largest singular values no matter how it is aimed. What the theorem does not say is how much a given budget actually costs us, since that depends entirely on the numbers \(\sigma_{k+1},\ldots,\sigma_r\) we chose to leave behind.
Tail Energy, by Hand
The quantity \(\sqrt{\sum_{i=k+1}^r \sigma_i^2}\) is called the tail energy, and it is small enough to compute by hand, exactly as we will 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
Two of the most common uses of low-rank approximation come out of that observation.
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 genuinely low-rank signal plus noise spread thinly across every direction. The signal’s energy concentrates in the top few singular values while the noise contributes a little to all \(r\) of them, so truncating to rank \(k\) discards far more noise than signal. Noise is the flat spectrum from the previous section, and a flat spectrum is precisely what truncation destroys.
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.
Looking Forward
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).
If you carry one sentence out of today, carry this one: whatever rank you keep, the error of the best approximation is exactly the tail of singular values you discarded.