Fourier transform

The Fourier transform takes a function and returns another that describes how much of each frequency is present in it ¹, like decomposing a musical chord into the intensities of its pitches ². That output is the frequency domain representation ³. In 1822 Joseph Fourier claimed that any function, continuous or not, can be expanded into a series of sines ⁴. Or, in BetterExplained's words: given a smoothie, it finds the recipe ⁵.

The discrete Fourier transform (DFT) turns a finite list of samples into a list of the same length giving the amplitude and phase of each frequency ¹. The fast Fourier transform (FFT) computes the same DFT by factoring its matrix into sparse pieces ², cutting the time to O(n log n) ³. James Cooley and John Tukey published the general FFT in 1965 ⁴, though Gauss had a very similar method in unpublished 1805 work ⁵; Gilbert Strang called it the most important numerical algorithm of our lifetime ⁶.

Audio: splitting a sound into its pitches is the textbook picture ¹. Fast cosine transforms, close cousins, run JPEG and MP3 encoding and decoding ²; JPEG applies one to each 8×8 block of pixels ³, because a DCT, like a Fourier transform, produces a spatial frequency spectrum ⁴. The Fourier transform is also used in magnetic resonance imaging (MRI) ⁵.