Fourier transform

The continuous version for non-periodic signals: $\hat f(\xi) = \int f(t)\,e^{-2\pi i\xi t}\,\dd t$ gives the amount of each frequency $\xi$. It turns convolution into multiplication and differentiation into multiplication by $2\pi i\xi$ — which is why filtering, compression and solving linear PDEs are easier in frequency space.

Linear, time-invariant systems — filters, lenses, rooms, transmission lines, the heat equation — do not mix frequencies: a sinusoid goes in, the same sinusoid comes out, scaled and shifted. In the frequency domain such a system is just a multiplication, so the Fourier transform diagonalizes it.

Wind the signal around a circle at frequency $\xi$ (multiply by $e^{-2\pi i\xi t}$) and compute the centre of mass. If the signal has a component at $\xi$, the winding piles it up on one side and the centre moves away from zero; otherwise everything averages out. $\hat f(\xi)$ is that centre of mass. A narrow signal needs many frequencies (wide spectrum); a pure tone has a single spike — the time–frequency uncertainty principle.

Key properties: $\widehat{f * g} = \hat f\,\hat g$ (convolution theorem), $\widehat{f'}(\xi) = 2\pi i\xi\,\hat f(\xi)$, $\int|f|^2 = \int|\hat f|^2$ (Plancherel). The discrete Fourier transform of $N$ samples, $X_k = \sum_{n=0}^{N-1} x_n e^{-2\pi i kn/N}$, is computed in $O(N\log N)$ by the FFT.

A 3-second recording of A440 plus a little noise: its DFT shows a sharp peak at 440 Hz (and 880, 1320… if the instrument has harmonics). A guitar tuner is literally this computation followed by argmax.

Audio codecs, image compression, Wi-Fi and 4G/5G (OFDM), MRI reconstruction, radar, spectroscopy, fast polynomial and integer multiplication, large convolutions — all run on Fourier transforms computed by the FFT, one of the most important algorithms ever written.