Chapter 10 of 0–21

The Fourier basis

Describing any list of 113 numbers as a mix of waves — and why periodic means sparse.

The network's weights and activations are lists of 113 numbers — one per input number. This chapter introduces a way to describe any such list as a mix of waves. It is the lens through which the paper reads the whole network.

A basis made of waves

Chapter 3 said that in an orthonormal basis, the weights of a vector are just dot products. The Fourier basis of 113-dimensional space is an orthonormal basis made of waves [25]: the constant vector, and for each frequency k = 1, …, 56 a cosine and a sine wave,

for x = 0, …, 112. That is 1 + 2·56 = 113 vectors, as many as the dimension. The factors \sqrt{1/113} and \sqrt{2/113} give every vector length 1; one can check that any two different ones have dot product 0. We stack them as the rows of a 113 × 113 matrix F, in the order Const, cos 1, sin 1, cos 2, sin 2, …, sin 56 — the order used in the paper's code [6].

Writing a list of 113 numbers in this basis — computing its dot product with each wave — is the discrete Fourier transform; each dot product is a Fourier coefficient. Because F is orthonormal, the coefficients are F v and the original is recovered as F^\top (F v) = v.

Periodic means sparse

A vector is sparse if only a few of its entries are large. The key intuition, as the ARENA course puts it, is that a function that looks periodic in the ordinary basis is sparse in the Fourier basis [3]: a wave of frequency 14 is one basis vector (well, a mix of cos 14 and sin 14), so its transform has only two non-zero coefficients, while a random-looking list spreads over all 113.

Press ▶ next to “phase shift” to slide the wave along: the picture moves, but its Fourier coefficients stay on cos k and sin k; only their balance changes.

This is why the Fourier basis is the right lens: if the network's weights turn out to be sparse in it, the network is using a few specific waves — and we can name them.

Two inputs: the 2D Fourier basis

Activations depend on two numbers, a and b: they form a 113 × 113 grid. The 2D Fourier basis consists of products of a wave in a with a wave in b, F_i(a)\,F_j(b), for all 113 × 113 pairs (i, j). Transforming a grid G into it means C = F\,G\,F^\top: transform along a, then along b.

Three kinds of 2D basis functions will matter:

• Constant: Const(a)·Const(b) — the same value everywhere.
• A linear term: a wave in one input only, e.g. \cos(w_k a)\cdot\text{Const}(b) — vertical or horizontal stripes.
• A quadratic term: a product of waves in both inputs, e.g. \cos(w_k a)\cos(w_k b) — a checkerboard of blobs.

Press ▶ next to “index in a” to run through all 113 waves in a.

The combination that matters most is diagonal stripes. By the angle-addition identity of chapter 9,

so a grid that depends only on a + b at frequency k is the difference of two quadratic terms — in the normalised basis it is the unit vector \big(\cos_k\!\otimes\cos_k - \sin_k\!\otimes\sin_k\big)/\sqrt2, and likewise \sin(w_k(a+b)) is \big(\sin_k\!\otimes\cos_k + \cos_k\!\otimes\sin_k\big)/\sqrt2 (here ⊗ means “product of a wave in a and a wave in b”) [6] [3]. These two cos/sin(w_k(a+b)) directions are the main characters of the rest of the story.