Rank and the Four Subspaces

Discover: fine-tuning a giant with a sliver of its parameters

GPT-3 has 175 billion parameters. Fine-tuning all of them for a new task produces a new 175-billion-parameter model, and a company with a hundred tasks would have to store a hundred of them. In 2021 a team at Microsoft proposed a way out called LoRA, low-rank adaptation. Freeze every pretrained weight matrix $W_0$, and learn only a correction $\Delta W$ (read “delta W”), written as a product of two thin matrices:

Here $W_0$ is $d \times k$, $B$ is $d \times r$ and $A$ is $r \times k$, where $r$ is tiny. The paper uses values like $r = 4$ for matrices with $d = k = 12{,}288$, and reports that even $r = 1$ or $2$ can be enough. On GPT-3 that cuts the number of trainable parameters by a factor of about 10,000, while performing on par with full fine-tuning on the benchmarks they tested.

That sounds too good to be true, so check the arithmetic yourself.

$BA$ is a full-size matrix, but it can't be any matrix. Its columns are all combinations of just $r$ columns of $B$, so it only ever reaches an $r$-dimensional slice of the space. That number, the true dimension of what a matrix can produce, is its rank. To see why LoRA works, you need to know what a matrix keeps, what it throws away, and how the two are related.

Learn: the column space, everything A can reach

Let $A$ be an $m \times n$ matrix, so it takes inputs $\mathbf{x} \in \mathbb{R}^n$ to outputs $A\mathbf{x} \in \mathbb{R}^m$. Its column space is the set of every output it can produce:

Read it as “C of A is the set of all A x, for x in R n”. Since $A\mathbf{x}$ is a combination of the columns of $A$ weighted by the entries of $\mathbf{x}$ (Chamber 4), the column space is exactly the span of the columns (Chamber 3). It's a subspace of $\mathbb{R}^m$: it contains $\mathbf{0}$, and sums and multiples of outputs are outputs again.

This answers the question Chamber 5 kept circling. $A\mathbf{x} = \mathbf{b}$ has a solution exactly when $\mathbf{b}$ is in $C(A)$. Take

Two independent columns span a plane in $\mathbb{R}^3$: the plane where the third entry is the sum of the first two. A right-hand side on that plane has a solution, and one off it has none.

To find a basis for $C(A)$ in general, row reduce and look at where the pivots land: the pivot columns of the original $A$ form a basis. Careful: of $A$, not of its echelon form. Row operations change the columns themselves (and so the column space), but they never change which combinations of columns add up to zero, since those combinations are the solutions of $A\mathbf{x} = \mathbf{0}$, and row operations never change solutions. So a column that depends on earlier ones in the echelon form depended on the same ones, with the same weights, in $A$.

Learn: the null space, everything A destroys

The null space is the set of inputs that $A$ sends to zero:

Read it as “N of A, the set of x such that A x equals zero”. It's a subspace of $\mathbb{R}^n$, the input side: if $A\mathbf{x} = \mathbf{0}$ and $A\mathbf{y} = \mathbf{0}$, then $A(\mathbf{x} + \mathbf{y}) = \mathbf{0}$ and $A(c\mathbf{x}) = \mathbf{0}$. It's also called the kernel, written $\ker A$. The null space is what the transformation destroys. Two inputs that differ by a null-space vector $\mathbf{v}$, say $\mathbf{x}$ and $\mathbf{x} + \mathbf{v}$, give exactly the same output, because $A(\mathbf{x} + \mathbf{v}) = A\mathbf{x} + A\mathbf{v} = A\mathbf{x}$. A layer $\mathbf{h} = W\mathbf{x}$ in a neural network literally cannot tell them apart.

Finding the null space is Chamber 5's elimination with $\mathbf{b} = \mathbf{0}$. Here it is in full for

1. 1

   Reduce to reduced row echelon form

   One operation does it: $R_2 \leftarrow R_2 - 2R_1$ gives

   $$R = \begin{bmatrix} 1 & 2 & 0 & 3 \\ 0 & 0 & 1 & 2 \end{bmatrix}.$$

   The pivots are in columns 1 and 3, so $x_1$ and $x_3$ are pivot variables and $x_2$ and $x_4$ are free variables.

2. 2

   Write the pivot variables in terms of the free ones

   $R\mathbf{x} = \mathbf{0}$ says $x_1 + 2x_2 + 3x_4 = 0$ and $x_3 + 2x_4 = 0$, so

   $$x_1 = -2x_2 - 3x_4, \qquad x_3 = -2x_4.$$
3. 3

   One special solution per free variable

   Set one free variable to $1$ and the others to $0$. With $x_2 = 1, x_4 = 0$ you get $\mathbf{s}_1 = (-2, 1, 0, 0)$. With $x_2 = 0, x_4 = 1$ you get $\mathbf{s}_2 = (-3, 0, -2, 1)$. Check the second in the original $A$: $-3 + 0 + 0 + 3 = 0$ and $-6 + 0 - 2 + 8 = 0$.

4. 4

   Every solution is a combination of them

   Any solution has some values $x_2 = t_1$ and $x_4 = t_2$, and the pivot variables follow, so $\mathbf{x} = t_1 \mathbf{s}_1 + t_2 \mathbf{s}_2$. The null space is the plane $N(A) = \operatorname{span}\{\mathbf{s}_1, \mathbf{s}_2\}$ inside $\mathbb{R}^4$.

This also completes the story of Chamber 5's “infinitely many solutions”. If $\mathbf{x}_p$ is any one solution of $A\mathbf{x} = \mathbf{b}$ (a particular solution), then every solution is $\mathbf{x}_p + \mathbf{x}_n$ with $\mathbf{x}_n \in N(A)$, because $A(\mathbf{x}_p + \mathbf{x}_n) = \mathbf{b} + \mathbf{0} = \mathbf{b}$, and the difference of two solutions always lands in the null space. The line of solutions in Chamber 5's workbench was a copy of the null space, shifted away from the origin.

Learn: rank

The rank of $A$ is the number of pivots elimination finds:

Each pivot column contributes one independent direction to the column space, so the rank is the dimension of everything $A$ can reach. Two facts make rank the single most useful number about a matrix.

Row rank equals column rank. The rows of $A$ span a subspace of $\mathbb{R}^n$, the row space $C(A^\top)$. Row operations only replace rows by combinations of rows, reversibly, so they never change the row space. In the echelon form, the non-zero rows hold one pivot each and are independent, so the row space has dimension $r$ too: the rank also counts the independent rows. That holds even for a $3 \times 1000$ matrix. So among those $1000$ columns, at most $3$ can be independent.

The rank is at most $\min(m, n)$, since there is at most one pivot per row and at most one per column. A matrix that reaches this limit has full rank:

• Full column rank ($r = n$): every column has a pivot, there are no free variables, and $N(A) = \{\mathbf{0}\}$. Then $A\mathbf{x} = \mathbf{b}$ has at most one solution.
• Full row rank ($r = m$): every row has a pivot, so no row can turn into $0 = 1$. Then $A\mathbf{x} = \mathbf{b}$ has at least one solution, for every $\mathbf{b}$.
• Square and full rank ($r = m = n$): both at once. That's exactly an invertible matrix from Chamber 5.

Now put the definitions to work. The matrices in the lab range from $2 \times 2$ to $3 \times 4$. Some are honest, and some hide a dependency between their rows. Find each rank by eliminating in your head or by spotting the dependency.

Learn: rank–nullity and the four subspaces

In the null space example, $A$ had $4$ columns: $2$ were pivot columns and $2$ were free, and the null space came out 2-dimensional. That's no coincidence.

Theorem (rank–nullity). For any $m \times n$ matrix $A$, $\operatorname{rank}(A) + \dim N(A) = n.$

Proof. Let $R$ be the reduced row echelon form of $A$. Row operations don't change the solutions of $A\mathbf{x} = \mathbf{0}$ (Chamber 5), so $N(A) = N(R)$, and the rank $r$ is the number of pivots in $R$. Each of the $n$ columns of $R$ is either a pivot column or a free column, never both, so there are exactly $n - r$ free columns. It remains to show that $\dim N(A) = n - r$, and we do it by exhibiting a basis with $n - r$ vectors.

For each free column $j$, let $\mathbf{s}_j$ be the special solution: set $x_j = 1$, every other free variable to $0$, and solve for the pivot variables. (Each row of $R$ has a single pivot, so it expresses one pivot variable in terms of the free ones, and the solution exists and is unique.) We check the two properties a basis needs.

• They span $N(A)$. Take any $\mathbf{x} \in N(A)$ and form $\mathbf{y} = \sum_{\text{free } j} x_j \mathbf{s}_j$. The vector $\mathbf{y}$ is in the null space (a combination of null-space vectors), and it has the same free entries as $\mathbf{x}$. The pivot entries of a null-space vector are determined by its free entries, so $\mathbf{y} = \mathbf{x}$.
• They're independent. In $\sum_j c_j \mathbf{s}_j$, look at the entry in free position $j$. Only $\mathbf{s}_j$ has a $1$ there, and every other special solution has a $0$, so that entry is $c_j$. If the combination is the zero vector, every $c_j$ is $0$.

So the $n - r$ special solutions form a basis of $N(A)$, and $\dim N(A) = n - r$. $\blacksquare$

The theorem is an accounting identity for input directions. Each of the $n$ dimensions of the input is either kept, contributing to the output (a pivot), or destroyed, lost to the null space (a free variable). Nothing is lost without a trace and nothing is double-counted.

Apply the theorem to $A^\top$ as well and you have all four fundamental subspaces, as Gilbert Strang calls them:

There's a hidden geometry here. $A\mathbf{x} = \mathbf{0}$ says every row of $A$ has dot product $0$ with $\mathbf{x}$ (Chamber 2), so every null-space vector is perpendicular to the whole row space. The input space $\mathbb{R}^n$ splits into two perpendicular pieces, of dimensions $r$ and $n - r$, and the output space $\mathbb{R}^m$ does the same. Chamber 7 builds least squares on exactly this picture.

Learn: rank one, and low-rank factorisation

The simplest non-zero matrices are outer products. For $\mathbf{u} \in \mathbb{R}^m$ and $\mathbf{v} \in \mathbb{R}^n$, the $m \times n$ matrix $\mathbf{u}\mathbf{v}^\top$ (read “u v transpose”) has entries $(\mathbf{u}\mathbf{v}^\top)_{ij} = u_i v_j$:

Column $j$ is $v_j \mathbf{u}$, so every column is a multiple of $\mathbf{u}$, and every row is a multiple of $\mathbf{v}^\top$. When $\mathbf{u}$ and $\mathbf{v}$ are non-zero the rank is exactly $1$ (you'll prove it below). Nine entries, but six numbers describe them completely: an $m \times n$ rank-one matrix needs only $m + n$ numbers instead of $mn$.

Chamber 4's outer product view of multiplication says that a product is a sum of outer products. If $B$ has columns $\mathbf{b}_1, \ldots, \mathbf{b}_r$ and $A$ has rows $\mathbf{a}_1^\top, \ldots, \mathbf{a}_r^\top$, then

Each term has rank at most $1$, and the rank of a sum is at most the sum of the ranks (the columns of $P + Q$ are combinations of the columns of $P$ and $Q$). So $\operatorname{rank}(BA) \le r$. More generally, a product can never have more rank than either of its factors:

You'll assemble the proof in the last part of this chamber. The converse holds too: any matrix of rank $r$ can be written as $BA$ with $r$ columns in $B$, for instance with its $r$ pivot columns as $B$ and the non-zero rows of its reduced echelon form as $A$. Low rank and a thin factorisation are the same thing.

Now derive LoRA's savings. The full update $\Delta W \in \mathbb{R}^{d \times k}$ has $dk$ entries. The factored update $BA$ has $dr$ entries in $B$ and $rk$ in $A$:

For GPT-3's $d = k = 12{,}288$ with $r = 4$, that's $8/12{,}288 = 1/1536$ per adapted matrix. The price is the constraint $\operatorname{rank}(\Delta W) \le r$. LoRA's authors bet that it's a price worth paying: that the change a pretrained model needs for a new task has a low “intrinsic rank”. They took the idea from work on intrinsic dimension, including Li et al. (2018), the paper from Chamber 3. The experiments say the bet pays off, at least for the tasks they tried.

Read beyond the course

Pick at least one. The first two deepen the linear algebra; the last two take you into LoRA itself.

Papers and lectures

LoRA is one of the most widely used ideas in modern machine learning, and its core is this chamber's linear algebra. Read the abstract and look at Figure 1, which draws $W$, $A$ and $B$ side by side. Then read Section 4.1 in full: it's one page, containing the equation you'll decode below, the initialisation, and the argument that merging $W_0 + BA$ adds no inference cost. Skim Section 4.2, which says which weight matrices to adapt. Then jump to Section 7.2, What is the optimal rank r for LoRA?, where Table 6 shows that $r = 1$ is already competitive on some tasks. Skip Section 3 (on other adaptation methods), the experiment tables in Section 5 and the appendices for now.

Watch

The geometric view of this chamber and the last. Watch for the moment a transformation squashes space onto a line: the line is the column space, the rank is its dimension, and the vectors that land on the origin form the null space.

Gilbert Strang's lecture on the four subspaces from MIT's 18.06. He works out the dimension of each subspace and how to find a basis for it, which is exactly the reasoning of this chamber, done at the blackboard.

Your turn

Start by matching the four subspaces, then translate the notation into NumPy.

Proofs

Put the first proof in order, leaving out the lines that don't belong. It's the rank bound that makes LoRA's updates low-rank. Then write the second yourself.

Code it up

Count LoRA's parameters on GPT-3, classify every small 0/1 matrix by rank, and uncover the low rank hiding in a distance matrix.