Span, Basis and Dimension

Discover: how many numbers does a network really need?

A small network that classifies handwritten digits (the MNIST dataset), with layers of 784, 200, 200 and 10 neurons, has 199,210 parameters. Normal training adjusts every one of them. In 2018 four researchers at Uber AI Labs asked an odd question: what if we only let the network move in a few directions? They froze a random starting point and a random matrix, and trained a much shorter vector instead:

Read it aloud: “theta D equals theta-nought D plus P times theta d.” The bracketed superscripts are labels, not powers (Mathematics for ML, Chamber 1): they say which space each vector lives in. $\theta^{(D)}$ is the full list of $D$ parameters, $\theta^{(D)}_0$ is a random starting point, $P$ is a random matrix with $D$ rows and $d$ columns, and $\theta^{(d)}$ is a short vector of just $d$ numbers. Only $\theta^{(d)}$ is trained.

With $d = 750$, the digit classifier already reached 90% of the accuracy of the normally trained network. Out of 199,210 directions, 750 random ones were enough. That raises questions this chamber answers. Which settings of the weights can such a network actually reach? What exactly is a “direction”, and when do 750 of them really give 750 different ones? And why 750, not 10 or 100,000? The words for these ideas are span, independence and dimension.

Learn: the span of a set of vectors

In Chamber 1 you built linear combinations: scale some vectors, then add them up. The span asks the natural next question: what are all the vectors you can build that way?

The set-builder braces are the ones from Mathematics for ML, Chamber 2. The coefficients $c_i$ are free: positive, negative, zero, fractions, anything real. Now picture the geometry:

• One non-zero vector $\mathbf{v}$: its span is every multiple $c\mathbf{v}$, a line through the origin.
• Two vectors in $\mathbb{R}^2$ that don't lie along the same line: their span is the whole plane.
• Two such vectors in $\mathbb{R}^3$: a plane through the origin, a flat sheet inside space.
• The zero vector alone: its span is $\{\mathbf{0}\}$, the single point at the origin.

Is a given vector in the span? That's a question about finding coefficients. Is $\mathbf{x} = (4, 7)$ in the span of $\mathbf{u} = (1, 2)$ and $\mathbf{v} = (1, 1)$? We need numbers $c_1, c_2$ with

Subtracting the first equation from the second gives $c_1 = 3$, and then $c_2 = 1$. Check: $3(1, 2) + 1(1, 1) = (4, 7)$. So yes, it's in the span.

Now try $\mathbf{x} = (1, 2, 4)$ with $\mathbf{u} = (1, 0, 1)$ and $\mathbf{v} = (0, 1, 1)$ in $\mathbb{R}^3$. Any combination is $c_1\mathbf{u} + c_2\mathbf{v} = (c_1, c_2, c_1 + c_2)$. The first two entries force $c_1 = 1$ and $c_2 = 2$, and then the third entry is $3$, not $4$. No coefficients work, so $(1, 2, 4)$ is not in the span. The span of $\mathbf{u}$ and $\mathbf{v}$ is a plane (the points whose third entry is the sum of the first two), and $(1, 2, 4)$ floats just above it.

Learn: subspaces, and a first proof

Lines and planes through the origin share a property: you can't escape them by adding or scaling. Add two vectors on a line through the origin and you land on the same line. Stretch one and you stay on it. Sets with that property get a name.

In $\mathbb{R}^2$ the subspaces are exactly $\{\mathbf{0}\}$, the lines through the origin, and the whole plane. The line $y = x + 1$ is not a subspace, because it misses the origin. Neither is a disc around the origin: scale any point by 100 and you leave it.

Here's a theorem with a complete proof. It says a span is always one of these well-behaved sets.

Claim. For any vectors $\mathbf{v}_1, \ldots, \mathbf{v}_k$ in $\mathbb{R}^n$, the set $S = \mathrm{span}\{\mathbf{v}_1, \ldots, \mathbf{v}_k\}$ is a subspace.

Proof. We check the three conditions in turn.

Zero. Choose every coefficient to be $0$: $0\,\mathbf{v}_1 + \cdots + 0\,\mathbf{v}_k = \mathbf{0}$. So $\mathbf{0} \in S$.

Addition. (You met this step in Chamber 1's proof puzzle: combinations of combinations are combinations.) Take any $\mathbf{x}, \mathbf{y} \in S$. By the definition of span, there are numbers $a_1, \ldots, a_k$ and $b_1, \ldots, b_k$ with $\mathbf{x} = a_1\mathbf{v}_1 + \cdots + a_k\mathbf{v}_k$ and $\mathbf{y} = b_1\mathbf{v}_1 + \cdots + b_k\mathbf{v}_k$. (Two different lists of letters, because $\mathbf{x}$ and $\mathbf{y}$ may need different coefficients.) Adding, and grouping the terms for each $\mathbf{v}_i$,

which is again a linear combination of the $\mathbf{v}_i$. So $\mathbf{x} + \mathbf{y} \in S$.

Scaling. For $\mathbf{x}$ as above and any $c \in \mathbb{R}$, we have $c\,\mathbf{x} = (c a_1)\,\mathbf{v}_1 + \cdots + (c a_k)\,\mathbf{v}_k$, another linear combination. So $c\,\mathbf{x} \in S$.

All three conditions hold, so $S$ is a subspace. $\blacksquare$

Notice the rhythm of the argument: unpack the definition (“in the span” means “equals some combination”), do a line of algebra, then repack the definition. Most proofs in linear algebra move to this beat.

Learn: linear independence

Some lists of vectors carry dead weight. In the list $\mathbf{u} = (1, 2)$, $\mathbf{v} = (2, 4)$, the second vector is just $2\mathbf{u}$, so including it reaches nothing new: $\mathrm{span}\{\mathbf{u}, \mathbf{v}\} = \mathrm{span}\{\mathbf{u}\}$, a line. Linear independence is the precise way to say “no dead weight”.

Why does this capture dead weight? Suppose $c_1\mathbf{v}_1 + \cdots + c_k\mathbf{v}_k = \mathbf{0}$ with some coefficient non-zero; renumber so that it's $c_k \neq 0$. Divide by $c_k$ and rearrange:

So $\mathbf{v}_k$ is a combination of the others, and dropping it doesn't shrink the span. Dependent means redundant; independent means every vector pulls its weight. For $(1, 2)$ and $(2, 4)$ the witness is $2(1, 2) - 1(2, 4) = (0, 0)$.

Two consequences are worth remembering. Any list that contains $\mathbf{0}$ is dependent, because $1 \cdot \mathbf{0} = \mathbf{0}$ uses a non-zero coefficient. And two vectors are dependent exactly when one is a multiple of the other, which means they lie on a common line through the origin.

A test for two vectors in the plane

In Chamber 1 you solved $a\mathbf{u} + b\mathbf{v} = \mathbf{t}$ by elimination and met the number $D = u_1v_2 - u_2v_1$. Chamber 1 left you a claim to check: $D = 0$ exactly when the two vectors share a line. Now we can prove it, and turn $D$ into a complete test for independence. Write $\mathbf{u} = (u_1, u_2)$ and $\mathbf{v} = (v_1, v_2)$, set the target to $\mathbf{0}$, and look for coefficients with $c_1\mathbf{u} + c_2\mathbf{v} = \mathbf{0}$. That's one equation per entry:

Eliminate exactly as in Chamber 1. Multiply (1) by $v_2$ and (2) by $v_1$, then subtract the second result from the first. The $c_2$ terms cancel, leaving

To eliminate $c_1$ instead, multiply (1) by $u_2$ and (2) by $u_1$, then subtract the first result from the second:

The same number appears in both. Chamber 1 promised that it would come back as the determinant, and here it is, a little early, written for the pair as

If $\det[\mathbf{u}\ \mathbf{v}] \neq 0$, divide both equations by it: $c_1 = 0$ and $c_2 = 0$. The only combination giving $\mathbf{0}$ is the trivial one, so the vectors are independent.

If $\det[\mathbf{u}\ \mathbf{v}] = 0$, they are dependent, and we can write down a witness. Take $c_1 = v_2$ and $c_2 = -u_2$. Equation (1) becomes $v_2 u_1 - u_2 v_1 = \det[\mathbf{u}\ \mathbf{v}] = 0$, and equation (2) becomes $v_2 u_2 - u_2 v_2 = 0$. Both hold. That witness is non-zero unless $u_2 = v_2 = 0$; in that case both vectors lie on the $x$-axis and $c_1 = v_1$, $c_2 = -u_1$ works instead (or $c_1 = 1$, $c_2 = 0$ if both vectors are $\mathbf{0}$).

So, for two vectors in the plane:

For example, $(2, 3)$ and $(4, 6)$ give $2 \cdot 6 - 3 \cdot 4 = 0$: dependent, and indeed $(4, 6) = 2(2, 3)$. But $(2, 3)$ and $(4, 5)$ give $10 - 12 = -2$: independent.

Geometrically, $\det[\mathbf{u}\ \mathbf{v}]$ is the signed area of the parallelogram with sides $\mathbf{u}$ and $\mathbf{v}$. A flat parallelogram has zero area, and that's exactly when the vectors are dependent. Chamber 5 builds determinants for matrices of any size. For now, it's your independence meter.

Now play with it. Drag the two vectors and watch the span. The lab asks you to hit a target with a combination $a\mathbf{u} + b\mathbf{v}$, and then to make the span collapse.

Learn: bases and coordinates

Span tells you how much you can reach, and independence tells you there's no waste. Put them together and you get the most useful idea in the chamber.

The standard basis $\mathbf{e}_1 = (1, 0)$, $\mathbf{e}_2 = (0, 1)$ from Chamber 1 is a basis of $\mathbb{R}^2$, but far from the only one. $\mathbf{b}_1 = (1, 1)$ and $\mathbf{b}_2 = (1, -1)$ form another: $\det[\mathbf{b}_1\ \mathbf{b}_2] = 1 \cdot (-1) - 1 \cdot 1 = -2 \neq 0$, so they are independent, and two independent vectors in the plane span all of it.

The pay-off of a basis is coordinates. Every $\mathbf{x}$ in $U$ can be written as $\mathbf{x} = c_1\mathbf{b}_1 + \cdots + c_n\mathbf{b}_n$ (because the basis spans), and in only one way (because it's independent). Chamber 1 proved this for the standard basis; you'll assemble the proof for any basis in Your turn. Those unique coefficients are the coordinates of $\mathbf{x}$ in the basis $\mathcal{B}$, written

and read “the coordinates of x in basis B”.

Worked example: find the coordinates of $\mathbf{x} = (5, 1)$ in $\mathcal{B} = ((1, 1), (1, -1))$. We need $c_1(1, 1) + c_2(1, -1) = (5, 1)$, that is, $c_1 + c_2 = 5$ and $c_1 - c_2 = 1$. Adding the equations gives $2c_1 = 6$, so $c_1 = 3$ and $c_2 = 2$:

In the standard basis the same vector has coordinates $(5, 1)$. One arrow, two descriptions. The vector didn't move; only the ruler changed.

Every spanning list contains a basis. Walk through the list in order, and throw away each vector that's already in the span of the vectors you've kept. What survives still spans the same set, since you only threw away redundant vectors. And it's independent: if some combination of the survivors gave $\mathbf{0}$ with a non-zero coefficient, the last survivor with a non-zero coefficient would be a combination of earlier survivors, and you would have thrown it away. Problem 3 below asks you to run this sifting algorithm on a table of features.

Learn: dimension

A plane through the origin has infinitely many bases, but every one of them has exactly two vectors. That's no accident.

The proof that all bases have the same size takes a page of careful bookkeeping (it's in Axler's Chapter 2, listed below), so we'll take it on trust here. What it buys us is a single number that measures how big a subspace is:

Three rules of thumb follow, and they're worth more than their size. In $\mathbb{R}^n$, more than $n$ vectors are always dependent: three vectors in the plane always carry dead weight. Fewer than $n$ vectors never span: two vectors can't fill space. And $\dim \mathrm{span}\{\mathbf{v}_1, \ldots, \mathbf{v}_k\} \le k$, with equality exactly when the vectors are independent.

A worked example: the plane $U = \{(x, y, z) : x + y + z = 0\}$. You can choose $x$ and $y$ freely, and then $z = -x - y$ is forced. So every vector in $U$ has the form

The two vectors on the right span $U$, and they're independent (look at their first two entries). So they form a basis and $\dim U = 2$. One linear equation in $\mathbb{R}^3$ removed one dimension. Keep that pattern in mind: it's exactly how Li et al. count.

Back to the paper: intrinsic dimension

Before touching a network, Li et al. warm up with a toy problem that you can now solve in your head. Take $D = 1000$ parameters, split them into 10 groups of 100, and require that the first group sums to 1, the second to 2, and so on up to 10. Each requirement is one linear equation, and just like $x + y + z = 0$ above, each removes one dimension. The solutions form a flat set of dimension $s = 990$. The paper defines the intrinsic dimension as what's left over:

Here $d_{\text{int}} = 1000 - 990 = 10$. Out of a thousand numbers, only ten things need to be got right. Now train in a random $d$-dimensional subspace, as in Eq. (2). The $d$ columns of $P$ are random, so they are independent (with probability 1) and the subspace really has dimension $d$. With $d < 10$ the subspace (almost surely) misses the solution set; with $d \ge 10$ it meets it. So sweep $d$ upwards and watch for the first success: it happens at $d = 10$, and it measures $d_{\text{int}}$.

For real networks nobody can count the equations, so the authors sweep $d$ and call a subspace successful when it reaches 90% of the performance of normal training. They call the first such $d$ the intrinsic dimension $d_{\text{int90}}$. Some of their measurements (Table 1):

Two things stand out. The numbers are small, and making the MNIST network wider or deeper barely changed $d_{\text{int90}}$. In the paper's words, every extra parameter “just ends up adding one dimension to the redundancy of the solution, $s$”. Bigger networks have bigger solution sets, not harder problems, and the authors suggest this may be one reason large models are easy to train.

Read beyond the course

Papers and lectures

The intrinsic-dimension paper is unusually readable, and you can get most of it today. Read the abstract. Then read Section 2 up to the end of Section 2.1, about two pages: the toy problem, Eq. (1), Eq. (2), and the paragraph on how $P$ is built (its columns are scaled to length 1 but not made exactly orthogonal). Look at Figure 1, then read the first two paragraphs of Section 3.1 and Table 1. Skip Section 2.2's thresholds, the reinforcement-learning section and the supplementary material for now. The short discussion of compressing a network to 750 numbers in Section 3.1 is a fun bonus.

Watch

Grant Sanderson animates exactly the picture from the lab: two vectors whose combinations sweep out the plane, until they line up and the span collapses to a line. Watch for the three-dimensional case in the second half, where a third vector either adds a new direction or stays trapped in the plane of the first two.

Your turn

You've met span, independence, bases and dimension. Now use them: match sets of vectors to their spans and notation to code, assemble a proof and write one, then solve three problems in code.

Proofs

The first proof explains why coordinates in a basis are well defined: put its lines in order and leave out the two that don't belong. The second you write yourself.

Code it up

Three problems in the Project Euler style: each has a single answer. The second applies the intrinsic-dimension paper's toy problem, and the third runs the sifting algorithm from this chamber.