Fourier claims that any signal can be written as a sum of pure sine and cosine waves at different frequencies, each contributing with its own amplitude and phase shift. The Fourier transform is the procedure that recovers that recipe from the signal.

The mechanism behind the recovery is similarity measurement. Two signals sampled at the same points can be compared with a dot product: multiply them value by value and add all the products. The sum is large when the two rise and fall together, and close to zero when they do not. Comparing a signal against one fixed pure wave therefore answers a single question, namely how much of that one frequency the signal contains. Running that comparison once for every candidate frequency produces the whole recipe. Everything below is an elaboration of this one idea.

Three terms are often used interchangeably in the literature and are not interchangeable.

The Fourier transform (FT) is the mathematical object. It acts on a continuous signal defined over an unbounded domain and is written as an integral.

The discrete Fourier transform (DFT) is its finite counterpart. It takes \(N\) samples of a signal, where \(N\) denotes the number of samples, and returns \(N\) coefficients. The integral becomes a sum. This is the version that applies to a numerical grid, and the version implemented in code.

The fast Fourier transform (FFT) is not a third transform. It is an algorithm that computes exactly the DFT, returning the same numbers, in \(\mathcal{O}(N \log N)\) operations instead of the \(\mathcal{O}(N^2)\) of evaluating the DFT sum directly, where \(N\) again denotes the number of samples.

\(S(f) = \int_{-\infty}^{\infty} s(t)\, e^{-j 2\pi f t}\, dt\)(1)

where \(s(t)\) denotes the signal as a function of time, \(t\) denotes time, \(f\) denotes the test frequency in oscillations per unit of time, \(j\) denotes the imaginary unit, \(e^{-j 2\pi f t}\) denotes the pure reference wave at that test frequency, and \(S(f)\) denotes the resulting complex coefficient for that frequency.

The reference wave unpacks through Euler's formula:

\(e^{-j 2\pi f t} = \cos(2\pi f t) - j \sin(2\pi f t)\)(2)

where \(\cos(2\pi f t)\) denotes the real part and \(-\sin(2\pi f t)\) denotes the imaginary part of a point on the unit circle in the complex plane. As \(t\) advances, that point rotates clockwise, completing exactly \(f\) full turns per unit of time, where \(f\) denotes the test frequency. It is a clock hand spinning at a chosen rate.

The three pieces of the formula then read as follows. The factor \(e^{-j 2\pi f t}\) supplies the spinning clock hand. The factor \(s(t)\) stretches or shrinks that hand's length at each instant according to the signal's strength there, which winds the signal around the unit circle at rate \(f\). The integral adds up all of these weighted points, which locates the center of mass of the wound curve up to a scale factor.

The outcome depends on whether the winding rate matches a frequency present in the signal. At a mismatched rate, the signal's peaks land at spread-out angles around the circle, the weighted points sit roughly symmetrically about the origin, and they cancel, leaving \(|S(f)|\) near zero, where \(|S(f)|\) denotes the magnitude of the coefficient. For a beautiful visualization of this, please watch the video by 3Blue1Brown on the Fourier transform.

On a grid, the signal exists only at finitely many sample points, so the integral becomes a sum:

\(S_k = \sum_{i=0}^{N-1} s_i\, e^{-j 2\pi k i / N}, \qquad k = 0, 1, \dots, N-1\)(3)

where \(s_i\) denotes the signal value at grid index \(i\), \(N\) denotes the number of samples, \(k\) denotes the integer frequency index and counts how many full oscillations the reference wave completes across the whole sampled domain, and \(S_k\) denotes the complex coefficient of that frequency. The subscript \(k\) is an index, not an exponent, following the convention used throughout the series.

The reference wave is the same object as before. Writing \(\kappa_k = 2\pi k / N\), where \(\kappa_k\) denotes the phase advance per grid point of mode \(k\).

The frequency index runs over exactly \(N\) evenly spaced integer values, where \(N\) denotes the number of samples.

Consider a 100 by 100 displacement grid holding a sharp circular wavefront from a clap, radiating outward from the center. The transform extends to this case by giving the reference wave a second frequency knob:

\(e^{-j 2\pi (k_x x + k_y y)}\)(4)

where \(x\) and \(y\) denote the two spatial coordinates, \(k_x\) denotes how many oscillations the wave completes per unit length when walking along the \(x\) direction, and \(k_y\) denotes the same quantity for the \(y\) direction.

One such wave, drawn on the grid, is a striped pattern. With \(k_y = 0\) the wave varies only along \(x\) and stays constant along \(y\), which produces vertical stripes. With \(k_x = 0\) the roles swap and the stripes are horizontal. With both nonzero the stripes run diagonally, tilted by the ratio of the two values. Larger values pack the stripes more tightly.

The discrete version sums over both spatial indices:

\(\hat{U}_{k_x, k_y} = \sum_{i=0}^{N_x - 1} \sum_{m=0}^{N_y - 1} u_{i,m}\, e^{-j 2\pi \left( \frac{k_x i}{N_x} + \frac{k_y m}{N_y} \right)}\)(5)

where \(u_{i,m}\) denotes the displacement value stored in the grid cell at column index \(i\) and row index \(m\), \(N_x\) and \(N_y\) denote the number of grid points along each axis, \(k_x\) and \(k_y\) denote the two integer frequency indices, and \(\hat{U}_{k_x, k_y}\) denotes the single complex coefficient for that one striped pattern.

Mechanically this is still a dot product, now between two grids of the same shape. The reference wave is evaluated at every cell, giving a full 100 by 100 grid of complex numbers. That grid is multiplied cell by matching cell with the displacement grid, and all products are added into one scalar. The double sum is nothing more than that element-wise multiply followed by a total sum.

Repeating this for every pair \((k_x, k_y)\), where \(k_x\) ranges over \(N_x\) values and \(k_y\) over \(N_y\) values, produces an output grid with the same dimensions as the input.

Input and output have identical shape, which invites a false reading of the output. But keep in mind, that the Fourier Transform is mapping from a spatial to a frequency domain. The axes of the input grid are positions, but the axes of the output grid are frequency indices, not positions. Cell \((k_x, k_y)\) does not correspond to any location in the room where the clap happened, and it is not the value of anything at a point.

What the cell holds is the answer to one question: how much of this specific striped ripple pattern, a pattern that covers the whole domain at once, is contained in the field. Every cell of the input grid contributed to it, because the dot product summed over all of them. A frequency coefficient is therefore a global property of the entire field. It can never be a local one, and there is no meaningful way to ask where in space a given coefficient lives.

This global character is the reason frequency space is attractive for a neural network. A convolutional kernel reads only a small neighbourhood of cells, so information travels across the grid one kernel width per layer, and covering a large domain requires many layers. A coefficient in frequency space already summarizes the whole domain, so modifying it changes the field everywhere at once. Operating on coefficients gives global reach in a single cheap step, which is the design idea behind the Fourier Neural Operator covered in the next post.