Skip to content
Last Dictionary
Plane
Mathematics & StatisticsVision, Speech & PerceptionDeep Learning

Fourier transform

nounAlso: Fourier analysis, Fourier series, fast Fourier transform, FFT, discrete Fourier transform, DFT, frequency domain

In plain wordsA way of breaking a signal — a sound, an image, any pattern over time or space — into the simple waves of different frequencies that add up to it, much as a prism splits white light into colors.

  1. The operation that rewrites a function of time or space as a continuous weighted sum of sinusoids of every frequency, giving its frequency-domain representation: each weight is a complex number whose magnitude and angle are that component's amplitude and phase. Its discrete version (DFT), computed in O(n log n) time by the fast Fourier transform (FFT), is among the most used algorithms in computing. The convolution theorem — convolution in one domain is multiplication in the other — lets large convolutionsconvolution, n.: An operation that slides a small grid of weights across an image or signal, multiplying and adding at each spot, to measure how strongly a pattern appears at every location. be computed quickly and links CNNsconvolutional neural network, n.: A kind of neural network built for images and other grid-like data. It slides small pattern detectors across the input, finding edges first, then shapes, then whole objects. to signal processing. In AI, Fourier ideas appear in audio front ends (spectrogramsspectrogram, n.: A picture of sound that shows time from left to right, pitch from bottom to top, and loudness as brightness or color, so that speech and music can be seen as patterns. and mel spectrogramsmel spectrogram, n.: A version of a sound picture whose pitch axis is squeezed to match human hearing, giving more detail to low sounds than to high ones; the usual way AI models take in audio. via the short-time Fourier transform), sinusoidal positional encodingspositional encoding, n.: Extra information added to each word so a transformer knows where it sits in the text. Without it, 'dog bites man' and 'man bites dog' would look the same to the model. and rotary embeddingsrotary positional embedding, n.: A way of telling a transformer where each word is by rotating parts of its internal numbers by an angle that grows with position, so the model can read off how far apart two words are., random Fourier features for kernel methods and neural fields, FFT-based token mixing (FNet), Fourier neural operators for solving equations, and the 'spectral bias' by which networks learn low-frequency functions first.

    Replacing self-attention with a 2-D Fourier transform kept most of the accuracy at a fraction of the cost.

f^(ξ)=∫−∞∞f(x) e−2πixξ dx\hat{f}(\xi) = \int_{-\infty}^{\infty} f(x)\, e^{-2\pi i x \xi}\, dx

Origin

Joseph Fourier claimed that arbitrary functions can be expanded in trigonometric series in his 1807 memoir on heat conduction, published in Théorie analytique de la chaleur (1822). 'Fourier transform' was in English use by the 1920s. James Cooley and John Tukey's 1965 fast Fourier transform, anticipated in unpublished work by Gauss around 1805, made digital spectral analysis practical.

Related

See also
  • convolutionconvolution, n.: An operation that slides a small grid of weights across an image or signal, multiplying and adding at each spot, to measure how strongly a pattern appears at every location.
  • spectrogramspectrogram, n.: A picture of sound that shows time from left to right, pitch from bottom to top, and loudness as brightness or color, so that speech and music can be seen as patterns.
  • positional encodingpositional encoding, n.: Extra information added to each word so a transformer knows where it sits in the text. Without it, 'dog bites man' and 'man bites dog' would look the same to the model.
  • rotary positional embeddingrotary positional embedding, n.: A way of telling a transformer where each word is by rotating parts of its internal numbers by an angle that grows with position, so the model can read off how far apart two words are.
  • Taylor seriesTaylor series, n.: A way of approximating a complicated curve near a chosen point by adding up simple pieces: a constant, a straight-line slope, a bend, and so on.
  • samplingsampling, n.: Picking some items at random from a larger set or from a range of possibilities — surveying 1,000 voters, say, or letting an AI choose its next word by a weighted lottery.

Sources

  1. Cooley, J. W. & Tukey, J. W. (1965). An Algorithm for the Machine Calculation of Complex Fourier Series. Mathematics of Computation, 19(90).

Mentioned in

big O notationbig O notation, n.: Shorthand for how the cost of a computation grows as the problem gets bigger. Saying attention costs 'O(n²)' means doubling the length of the text roughly quadruples the work., convolutionconvolution, n.: An operation that slides a small grid of weights across an image or signal, multiplying and adding at each spot, to measure how strongly a pattern appears at every location., samplingsampling, n.: Picking some items at random from a larger set or from a range of possibilities — surveying 1,000 voters, say, or letting an AI choose its next word by a weighted lottery., spectrogramspectrogram, n.: A picture of sound that shows time from left to right, pitch from bottom to top, and loudness as brightness or color, so that speech and music can be seen as patterns., neural operatorneural operator, n.: A neural network that learns how a whole physical system responds, such as how a fluid flows given its starting state, so it can stand in for slow simulations and answer new cases quickly., Taylor seriesTaylor series, n.: A way of approximating a complicated curve near a chosen point by adding up simple pieces: a constant, a straight-line slope, a bend, and so on.