Matrix Approximation

Given a matrix $A$ of rank $r$, the best rank-$k$ approximation (for $k < r$) is the matrix $A_k$ that minimizes $\|A - A_k\|$ among all rank-$k$ matrices. The answer is a celebrated result: the Eckart–Young theorem says $A_k = \sum_{i=1}^k \sigma_i \mathbf{u}_i \mathbf{v}_i^\top$ — just keep the top $k$ singular values and corresponding singular vectors from the full SVD.

This is optimal under both the Frobenius norm $\|A - A_k\|_F = \sqrt{\sigma_{k+1}^2 + \dots + \sigma_r^2}$ and the spectral norm $\|A - A_k\|_2 = \sigma_{k+1}$. The approximation error is directly controlled by the discarded singular values — if they are small, you have compressed without losing much, and if they decay quickly, you can use small $k$ very effectively.

This is the most useful theorem in data compression. An $m \times n$ matrix requires $mn$ numbers; its rank-$k$ approximation requires only $k(m + n + 1)$ numbers (store $U_k$, $\Sigma_k$, $V_k$). For images, recommendation matrices, or learned weight matrices, the singular values often decay exponentially, so $k \ll \min(m, n)$ gives nearly lossless compression.

Principal Component Analysis is the application to data. Given a centered data matrix $X \in \mathbb{R}^{n\times d}$, the rank-$k$ SVD approximation gives the best $k$-dimensional affine reconstruction. The principal components are the top-$k$ right singular vectors; projecting onto them yields the low-dimensional representation.

Worked example — compression savings: An $1000 \times 1000$ image matrix requires $10^6$ numbers. A rank-10 SVD approximation requires only $10(1000 + 1000 + 1) \approx 20{,}000$ numbers — a 50× compression. If the singular values decay quickly (as in most natural images), the visual quality loss is minimal.

Worked example — LoRA parameter count: A transformer attention layer with $d = 4096$ has a $4096 \times 4096$ weight matrix: $\approx 16.7$M parameters. A LoRA update $UV^\top$ with rank $r = 8$: $U \in \mathbb{R}^{4096 \times 8}, V \in \mathbb{R}^{8 \times 4096}$, totaling $2 \cdot 4096 \cdot 8 \approx 65{,}000$ parameters — 250× fewer trainable weights, which is why LoRA makes fine-tuning cheap.

In modern deep learning, Low-Rank Adaptation (LoRA) freezes a large pretrained weight matrix $W$ and learns a low-rank update $W + UV^\top$ with $U, V$ skinny. This is the same rank-$k$ parameterization, used as a *cheap fine-tuning* strategy: millions of parameters become thousands, with minimal loss in quality. Matrix approximation is the quiet backbone of efficient AI.