Rank and low-rank matrices

A column times a row gives a whole matrix with a single pattern in it, a rank-1 matrix. Any matrix is a sum of such pieces, and the singular value decomposition orders them by importance. Keep only a few and you get a small, close approximation. LoRA fine-tunes language models this way.

Key idea: Outer product u vᵀ is rank 1; rank = number of independent directions; SVD writes a matrix as a sum of rank-1 pieces by importance; truncating gives the best low-rank approximation; LoRA: ΔW = BA with r ≪ d
Real world: A times table is rank 1: every row is a multiple of 1, 2, 3, …, so 100 cells come from 20 numbers. A photo can be stored as a few dozen such pieces with little visible loss.
In an LLM: LoRA fine-tunes a 4,096 × 4,096 weight matrix by learning B (4,096 × 16) and A (16 × 4,096): 131,072 numbers instead of 16.8 million, 0.78%, and the update BA still has full size.

One pattern: the outer product

Multiply a column vector $\mathbf{u}$ by a row vector $\mathbf{v}^\top$ and you get a whole matrix, the :

(\mathbf{u}\mathbf{v}^\top)_{ij} = u_i\, v_j

It is matrix multiplication with inner size 1: shape $(m \times 1)(1 \times n) = m \times n$ . Every row is the same row $\mathbf{v}^\top$ scaled by a number, and every column is $\mathbf{u}$ scaled by a number. The whole table contains one pattern, and $m + n$ numbers are enough to rebuild all $m \times n$ .

row 1 of 4

u ╲ vᵀ

210−11

12−10

210−11

add a second rank-1 piece

numbers in the table20

numbers that made it9

rank1

The outer product of u (4 numbers) and vᵀ (5) is a 4 × 5 table: cell (i, j) = u[i] × v[j]. Press play to fill the rest. Row 1 is 1 × v = [2, 1, 0, −1, 1]. Every row is a multiple of the same row v.

u runs down the side and vᵀ across the top, like a times table. Click any number in u or v to change it (it cycles −2 to 2). Press play to fill the table row by row: row i is u[i] times the whole row v.

Rank: how many independent patterns

The of a matrix is the number of independent directions among its rows (it is always the same for its columns). Equivalently, it is the smallest number of outer products that add up to the matrix. An $m \times n$ matrix has rank at most the smaller of $m$ and $n$ .

The transformations lesson gave the picture: a 2 × 2 matrix of rank 2 keeps the plane a plane; one of rank 1 squashes it onto a line, and its determinant is 0. In general, a rank- $r$ matrix sends everything into an $r$ -dimensional subspace, however big its input is.

example · a times table

The 10 × 10 multiplication table has 100 entries, but entry $(i, j)$ is just $i \times j$ : it is the outer product of $[1, 2, \dots, 10]$ with itself, rank 1, rebuilt from 20 numbers (10 if you notice the two are the same). A spreadsheet of “price per item × number of items” for several products and quantities is the same: one pattern, rank 1. Real data is rarely exactly rank 1, but often close to a low rank, and that is what compression exploits.

Every matrix is a sum of rank-1 pieces

The (SVD) writes any matrix $M$ as

M = \sigma_1 \mathbf{u}_1 \mathbf{v}_1^\top + \sigma_2 \mathbf{u}_2 \mathbf{v}_2^\top + \dots + \sigma_r \mathbf{u}_r \mathbf{v}_r^\top,

where the singular values $\sigma_1 \ge \sigma_2 \ge \dots \ge 0$ say how big each piece is, and the vectors $\mathbf{u}_1, \mathbf{u}_2, \dots$ have length 1 and are at right angles to one another, and so are $\mathbf{v}_1, \mathbf{v}_2, \dots$ Keeping just the first $k$ pieces gives the closest matrix of rank $k$ to $M$ (the Eckart–Young theorem). Here is a picture as a matrix:

Loading GPT-2 data…

A rank- $k$ matrix of size $m \times n$ needs $k(m + n)$ numbers in this form (plus $k$ singular values) instead of $mn$ . That saves a lot when $k$ is much smaller than $m$ and $n$ , and saves nothing when it isn’t.

LoRA: fine-tuning with a low-rank update

Fine-tuning a model means changing its weight matrices: $W \to W + \Delta W$ . For a 4,096 × 4,096 matrix, $\Delta W$ has 16.8 million numbers, and a model has hundreds of such matrices. Storing gradients and optimiser state for all of them takes many times the model’s own memory.

(low-rank adaptation) keeps $W$ frozen and learns the change in factored form:

W' = W + \Delta W = W + B A, \qquad B \in \mathbb{R}^{d \times r},\ A \in \mathbb{R}^{r \times d},\ r \ll d

$BA$ is a full-size matrix, but its rank is at most $r$ , and only $B$ and $A$ are trained. $B$ starts at zero, so training starts from exactly the original model.

width d4,096rank r16

full fine-tune16,777,216

LoRA (B and A)131,072

fraction trained0.78%

show a tiny example with numbers (d = 6, r = 2)

A full update of a 4,096 × 4,096 matrix has 16,777,216 numbers. LoRA learns B (4,096 × 16) and A (16 × 4,096): 131,072 numbers, 0.78% as many. Their product BA is a full-size 4,096 × 4,096 update, but of rank at most 16: it can only change W along 16 directions. The bet behind LoRA is that a fine-tune doesn’t need more.

Fine-tuning changes a d × d weight matrix W. LoRA freezes W and learns the change as B (d × r) times A (r × d). Drawn to scale: the thin strips are B and A.

example · LoRA on a 4,096-wide model

In a model with width 4,096 (Llama 2 7B, Mistral 7B), one attention projection is 4,096 × 4,096 = 16,777,216 weights. A rank-16 LoRA learns $B$ (4,096 × 16) and $A$ (16 × 4,096): 131,072 numbers, 0.78% of the matrix. Applied to all the linear layers of a 7B model, a rank-16 LoRA trains about 40 million parameters, around 0.6% of the model, and the adapter file is about 80 MB in 16-bit numbers instead of 14 GB. After training, $BA$ can be added into $W$ once, so the fine-tuned model runs exactly as fast as the original.

Are weight matrices low-rank?

Mostly not. GPT-2 small’s query matrix in layer 0 is 768 × 768 (all heads together); its first 92 SVD pieces hold half of its energy (the sum of squared singular values) and it needs 314 for 90%. A random matrix of the same size needs 140 and 391. So the trained matrix is more concentrated than noise, but nowhere near rank 16. LoRA works because the change needed for a fine-tune is close to low-rank, not the weights themselves. When it isn’t, for example when teaching a model a lot of new knowledge, full fine-tuning does better.

going deeper

Facts

$\operatorname{rank}(AB) \le \min(\operatorname{rank} A, \operatorname{rank} B)$ . So $BA$ with inner size $r$ has rank at most $r$ .
$\operatorname{rank}(A + B) \le \operatorname{rank} A + \operatorname{rank} B$ : adding $k$ rank-1 pieces gives rank at most $k$ .
In SVD form $M = U \Sigma V^\top$ with orthogonal $U$ , $V$ (see rotations) and diagonal $\Sigma$ . Geometrically: rotate, stretch along the axes, rotate.
Truncation error: $\lVert M - M_k \rVert_F^2 = \sum_{i > k} \sigma_i^2$ . The widget’s “error” is the square root of this divided by $\lVert M \rVert_F$ .

In code

import numpy as np
u, v = np.array([1, 2, -1, 0]), np.array([2, 1, 0, -1, 1])
P = np.outer(u, v)                    # 4 × 5, rank 1
np.linalg.matrix_rank(P)              # 1
 
U, s, Vt = np.linalg.svd(M, full_matrices=False)
k = 10
M_k = U[:, :k] * s[:k] @ Vt[:k]       # best rank-k approximation
 
# LoRA with the peft library
from peft import LoraConfig, get_peft_model
cfg = LoraConfig(r=16, lora_alpha=32, target_modules=["q_proj", "k_proj", "v_proj", "o_proj"])
model = get_peft_model(model, cfg)
model.print_trainable_parameters()

In papers

LoRA: Hu et al., 2021. Fine-tuning updates have low “intrinsic dimension”: Aghajanyan et al., 2020.
QLoRA (LoRA on a 4-bit model): Dettmers et al., 2023; see NF4.
Where LoRA falls short of full fine-tuning: Biderman et al., 2024.
Starting LoRA from the top singular vectors: PiSSA, Meng et al., 2024.
Best low-rank approximation: Eckart and Young, 1936.