Low-rank approximation — Linear algebra for LLMs

The SVD is a sum of rank-1 pieces

\displaystyle A = \sigma_1 u_1 v_1^\top + \sigma_2 u_2 v_2^\top + \dots + \sigma_r u_r v_r^\top

$U\Sigma V^\top$ written as a sum of outer products: Part 2’s fourth view of a matrix product. Each piece is rank 1, and they come sorted from the biggest $\sigma$ down.

Write

A = \sum_i \sigma_i\, u_i v_i^\top

, largest

\sigma_i

first.

Our two pieces

+

=

$\sigma_1 u_1 v_1^\top = 1.5\begin{bmatrix} 1 & 1 \\ 3 & 3 \end{bmatrix}$ carries most of $A$ ; the second piece is the correction.

Keep the top $k$

\displaystyle A_k = \sum_{i=1}^{k} \sigma_i\, u_i v_i^\top

Eckart–Young theorem: truncating the SVD gives the best rank- $k$ approximation there is, measured in the Frobenius or the spectral norm. No other rank- $k$ matrix is closer.

Write

Best rank-

k

approximation: keep the top

k

singular triples (Eckart–Young).

How much you lose

\displaystyle \|A - A_k\|_F = \sqrt{\sigma_{k+1}^2 + \dots + \sigma_r^2}

\displaystyle \|A - A_1\|_F = \sigma_2 = \sqrt5 \approx 2.24, \qquad \|A\|_F = \sqrt{50}

The error is exactly the singular values you dropped. Here the first piece keeps $\sigma_1^2 / (\sigma_1^2 + \sigma_2^2) = 45/50 = 90\%$ of the “energy” $\|A\|_F^2$ .

Write

Error = the dropped

\sigma

’s; energy kept =

\sum_{i \le k} \sigma_i^2 / \sum_i \sigma_i^2

.

Storage

\displaystyle m \times n \;\longrightarrow\; k(m + n) \;\; (\text{store } U_k\Sigma_k \text{ and } V_k)

\displaystyle 4096 \times 4096,\ k = 64\!: \; 524{,}288 \text{ vs } 16{,}777{,}216 \;(3.1\%)

If the singular values fall off fast, a few directions hold most of the matrix, and storing two thin factors is far cheaper.

✏️ Your turn

Rank-1 approximation

\sigma_1 = 5,\ u_1 = [0.6, 0.8],\ v_1 = [1, 0]

Write $A_1 = \sigma_1 u_1 v_1^\top$ .

Work it out on paper, then go to the next card to check.

Answer

\displaystyle 5\begin{bmatrix} 0.6 \\ 0.8 \end{bmatrix}\begin{bmatrix} 1 & 0 \end{bmatrix} = \begin{bmatrix} 3 & 0 \\ 4 & 0 \end{bmatrix}

Every column is a multiple of $u_1$ , every row a multiple of $v_1^\top$ : rank 1.

Where low rank shows up

In a transformer

LoRA learns a low-rank update to a weight (next deck).
Compression: replacing a weight by a truncated SVD shrinks it, at some cost in accuracy.
Attention heads are low-rank by construction (Part 3).
Measuring the singular values of weights or activations is a standard way to see how many directions really matter.

📌 Recap

Low-rank approximation in one card

$A = \sum_i \sigma_i u_i v_i^\top$ , sorted by $\sigma_i$ .
Truncating to $k$ terms is the best rank- $k$ approximation.
Error: $\|A - A_k\|_F = \sqrt{\sum_{i > k}\sigma_i^2}$ .
Storage: $mn \to k(m + n)$ .

Write

The four lines above.