AI Engineering Foundations 20: Fourier Transform — Reading the Same Numbers a Second Way

This is part 20 of the "AI Engineering Foundations" series, working through the math foundations of the 58k-star GitHub course *ai-engineering-from-scratch*, one lesson at a time. The previous post covered complex numbers: the real job of *i* is rotation. This post is entirely about that spinning.

A recording stored in a computer is a list of numbers: air pressure sampled every few milliseconds, ten thousand times. Stock prices are a list of numbers, one per day. An image, flattened, is also a list of numbers. These all share one reading — follow along in time and watch how the value changes at each step. That reading is useful, but some questions it inherently cannot answer. Is this recording a pure tone, or a chord of several tones? Does this stock have a weekly cycle? Is there a repeating texture in the image? These ask "what rhythms does it contain," not "what is the value at step k."

The Fourier transform is the second reading. Same list of numbers, different angle: don't look at each step's value; look at which frequencies of waves are inside, how strong each is, and where each starts.

Checking Against Rotation

As the previous post said, multiplying a complex number by e^{iθ} rotates it by θ. The Fourier transform is built entirely on this rotation.

The method is strikingly direct. To find how much of a "k rotations per N steps" component a signal contains, build a rotating ruler at that speed and let the signal run against it: the signal spins forward, the ruler spins backward. If the signal really contains a wave at that speed, the two stay in phase the whole way; multiply term by term and sum, and a large number accumulates. If not, terms cancel and the sum is near zero. Build N rulers at different speeds and try each; N coefficients come out. That is the discrete Fourier transform, the DFT.

Each coefficient is a complex number. Its magnitude tells you how strong that frequency is; its angle tells you where it starts.

How to read the coefficients: coefficient 0 is DC, the sum of all samples — the average times N. The middle one is the Nyquist frequency, half the sampling rate, the fastest oscillation these samples can represent. For real signals, the second half of the coefficients mirrors the first — all useful information is in a bit more than the first half, which is why spectrograms of real signals only plot half.

A Change of Coordinates, Not a Lost Bit

Multiply the N coefficients back by the rotation factors and divide by N, and the original signal comes back exactly. Not an approximation — exact reconstruction. The Fourier transform doesn't compress or discard anything; it just swaps coordinate systems: the same list of numbers, read horizontally it's time, read vertically it's frequency.

Precisely because it's an unconditional change of coordinates, one thing deserves a pause. Any list of numbers decomposes just as perfectly. A pure tone and white noise both yield N clean coefficients. The course's opening slogan — "every signal is a sum of sinusoids" — holds strictly in the discrete world, so strictly that it's indiscriminate. The decomposition always holds; the *interpretation* requires judgment: you must first ask whether the signal actually contains stable rhythms before the coefficients mean anything. A garbage signal decomposes into sinusoids that each look perfectly respectable — they just sum back to garbage.

Between a Trillion and Twenty Million Sits a Clever Trick

Computing the DFT by definition costs N²: N coefficients, each requiring N multiply-adds. A million samples means a trillion operations.

In 1965, Cooley and Tukey published a trick: split the signal by index into even and odd halves, compute a half-length DFT of each, then stitch them back together with a rotation factor (jargon: *twiddle factor*). Each stitching layer costs O(N), and there are log₂N layers. Total drops from N² to N log N. A million samples: a trillion becomes twenty million — 50,000×. Modern audio, imaging, and communications all stand on that 50,000×.

One detail deserves a close read. The course says: FFT requires the signal length to be a power of two; in practice, zero-pad to the next power of two. I tested this claim against real tools. 999 points, even 127 points — prime counts that can't be split evenly all the way down — fed straight into numpy's FFT, it computes them without complaint, and the results match the brute-force one-by-one multiplication to about 10⁻¹¹. The power-of-two restriction belongs to the classroom's recursive version (the course's own fft function falls back to the slow DFT for odd lengths). Modern libraries handle any length: mixed radix when the length factors into small primes, dedicated algorithms for prime lengths as a fallback. The textbook stated its own teaching implementation's limitation as if it were a limitation of FFT the technique.

I also checked a small number while I was at it: the slide's figure says an 8-point FFT takes "24 multiplications." Count them: it's 12 multiplications; 24 is the number of additions. The conclusion stands; the number was just pinned to the wrong pocket.

Aliasing: Fast Waves Impersonating Slow Ones

Waves faster than Nyquist, once sampled, impersonate slow waves. The course's example: a 90 Hz sine sampled at 100 Hz looks identical to 10 Hz.

I compared them sample by sample. Not "identical" — differing by a minus sign. Each sample of the 90 Hz wave is exactly the negative of the corresponding 10 Hz sample; their magnitude spectra are indistinguishable. What 90 Hz aliases into is strictly −10 Hz; the magnitude spectra of positive and negative frequencies share the same mirror. From these samples alone, no amount of mathematics recovers 90 Hz. That's why ADCs run an anti-aliasing filter before sampling, to block anything too fast. Downsampling feature maps in deep learning without low-pass filtering steps in the same pit; anti-aliasing pooling is the road built around it.

Resolution: To See Finer, Watch Longer

How far apart adjacent bins sit on the spectrum is determined only by observation duration. Watch 1 second: bin width 1 Hz. Watch 2 seconds: 0.5 Hz.

A common misconception: not enough data? Pad with zeros and resolution improves. The course devotes a section to this: no. Zero-padding only interpolates between existing bins; the spectrum looks smoother, but two nearby peaks that couldn't be separated still can't be. I verified the boundary of the criterion experimentally: two tones at 10.5 Hz and 11.5 Hz, exactly 1 Hz apart, computed from 1 second of data, merge into one lump (both frequencies ride on the gaps between bins); from 2 seconds, two clean spikes. To separate two frequencies Δf apart, you need at least 1/Δf seconds of *real* observation. The only way to see finer is to watch longer.

Windows: Not Free

The DFT treats your N samples as one endlessly repeating period. If the signal's head and tail don't join up, there's a jump at the seam, and a jump is an "infinitely fast" change that splatters energy across the whole spectrum. This is spectral leakage:明明 only one frequency, yet the spectrum glows on both sides.

The remedy is putting a hat on the signal: taper both ends to zero, keep the middle. The Hann window pushes the loudest sidelobe down to −31 dB, Hamming to −42 dB, Blackman to −58 dB. I measured each with 4096-point windows: −13.5, −32.3, −42.7, −58.1 dB — matching the course table's −13/−31/−42/−58. The cost: the main peak widens — two close frequencies become harder to tell apart.

Course exercise 4 buries a counterintuitive contrast worth running yourself. Two tones, 10 Hz and 12 Hz, sampled for 1 second, each completing a whole number of cycles. Then the unwindowed spectrum is perfect: two spikes of height 64, every other bin exactly zero, not a number wasted. Add a Hann window and the neighboring bins rise to 32 — the widened main lobe's cost made visible on the spot. Move the frequencies to 10.5 and 12.5 Hz (riding in the gaps), and the situation flips: without a window, leakage everywhere; with a window, saved. Windows aren't free, and they aren't always the right call. When the signal happens to be whole-period, the rectangular window is the correct answer — the course admits this in the exercise hints: "no windowing may actually be best." An exercise hiding a counterexample to the main text's intuition — that's good textbook writing.

Convolution Becomes Multiplication

The most elegant theorem in signal processing: convolution in the time domain equals pointwise multiplication in the frequency domain. Transform the signal and filter, multiply at corresponding positions, transform back — the result is identical to the sliding-window accumulate, with cost dropping from O(NM) to O(N log N).

CNN convolution layers and large-kernel convolutions all take this back door. One architecture, FNet, outright replaces self-attention with the FFT, trading O(N²) for O(N log N). One detail: the DFT computes *circular* convolution, with the signal's ends wrapped around. For ordinary linear convolution, zero-pad both sides to N+M−1 first.

A single FFT frame tells you which frequencies exist, not when they appear. A sweep that goes "5 Hz first, then 50 Hz" and a chord where "both play together" can have nearly identical magnitude spectra. To distinguish them, cut the signal into short segments, window and FFT each, and arrange the result into a time-by-frequency picture — the spectrogram. The mel spectrograms that speech models consume are a variant of this. Cutting into windows means time and frequency cannot both be had: a long window resolves frequency but blurs time; a short window resolves time but smears frequency. This isn't an engineering flaw; it's physics.

Positional Encoding: This Lesson's Nearest Exit

A Transformer's positional encoding is a direct application of this mathematics. Each position is encoded as a stack of sin and cos at different frequencies, laid out geometrically from "one turn per step" to "one turn per ten thousand steps," giving every position a unique fingerprint across all frequency bands.

Exercise 5 asks you to verify a property: the dot product of two positional encodings depends only on the distance, not the absolute positions. I ran it: dot(PE(0), PE(10)) and dot(PE(100), PE(110)) both give 42.8200228985 — identical to six decimal places, differences at the 10⁻¹⁵ level, the level of floating-point mantissas. As distance grows, the dot product shrinks from 62 down to around 19 — rapid decay at first, then settling onto a small plateau held up by the lowest few slow frequencies, never reaching zero. Distant positions' fingerprints really do grow less alike. The previous post's RoPE rotary positional encoding is the complex-number version of the same idea; the two roads meet at "relative position only."

Start with Exercise 3

All five exercises in this lesson are worth running; the smallest is exercise 3. With x = [1, 2, 3, 4, 0, 0, 0, 0] and h = [1, 1, 1, 0, 0, 0, 0, 0], hand-compute the first three terms of the circular convolution: term 0 is 1×1 = 1, term 1 is 1×2 + 1×1 = 3, term 2 is 1×3 + 1×2 + 1×1 = 6. Then verify via the FFT route: transform, multiply, inverse transform — the first three terms come out 1, 3, 6, matching position by position. The first time you see "time-domain convolution equals frequency-domain multiplication" with your own eyes, it's not on a page — it's in your own terminal.