The Fourier Transform: A Visual and Mathematical Primer

The Fourier Transform is one of those rare mathematical tools that feels like it should not work — yet it does, with uncanny precision, across domains as different as quantum mechanics, image compression, and audio engineering.

What Problem Does It Solve?

Suppose you record a musical chord. Your microphone captures a single waveform: a jagged, complicated function of time. Hidden inside that wave are individual notes — pure sine waves at specific frequencies. The Fourier Transform is the operation that decomposes the composite signal into its constituent frequencies.

Formally, given a function $f (t)$ , its Fourier Transform $\hat{f} (ξ)$ is:

$\hat{f} (ξ) = \int_{- \infty}^{\infty} f (t) e^{- 2 π i ξ t} d t$

The inverse transform recovers $f$ from $\hat{f}$ :

$f (t) = \int_{- \infty}^{\infty} \hat{f} (ξ) e^{2 π i ξ t} d ξ$

The key insight is that any reasonably well-behaved function can be written as a (possibly infinite) sum of sines and cosines.

The Discrete Fourier Transform

In practice, we work with sampled, finite signals. Given $N$ samples $x_{0}, x_{1}, \dots, x_{N - 1}$ , the Discrete Fourier Transform (DFT) is:

$X_{k} = n = 0 \sum N - 1 x_{n} \cdot e^{- 2 π ik n / N}, k = 0, 1, \dots, N - 1$

Computing this naïvely takes $O (N^{2})$ operations. The Fast Fourier Transform (FFT), due to Cooley and Tukey (1965), reduces this to $O (N lo g N)$ — an improvement that made real-time audio processing possible.

Complexity Comparison

Algorithm	Time Complexity	For $N = 1 0^{6}$
Naïve DFT	$O (N^{2})$	$1 0^{12}$ ops
FFT	$O (N lo g N)$	$2 \times 1 0^{7}$ ops
Speed-up	—	$\approx 50, 000 \times$

Implementing FFT in Python

Here is a clean, recursive implementation of the Cooley-Tukey radix-2 FFT:

import numpy as np
from typing import Sequence

def fft(x: Sequence[complex]) -> list[complex]:
    """Recursive Cooley-Tukey FFT (radix-2, decimation-in-time)."""
    N = len(x)
    if N <= 1:
        return list(x)

    # Split into even and odd indices
    even = fft(x[0::2])
    odd  = fft(x[1::2])

    # Twiddle factors: W_N^k = e^{-2πik/N}
    T = [
        np.exp(-2j * np.pi * k / N) * odd[k]
        for k in range(N // 2)
    ]

    return (
        [even[k] + T[k] for k in range(N // 2)] +
        [even[k] - T[k] for k in range(N // 2)]
    )


# Example: find frequencies in a signal
sample_rate = 1000  # Hz
duration    = 1.0   # second
t = np.linspace(0, duration, int(sample_rate * duration), endpoint=False)

# Two-tone signal: 50 Hz + 120 Hz
signal = np.sin(2 * np.pi * 50 * t) + 0.5 * np.sin(2 * np.pi * 120 * t)

spectrum = fft(signal)
freqs    = np.fft.fftfreq(len(signal), d=1 / sample_rate)

# Peak frequencies
magnitudes = np.abs(spectrum)
peaks = freqs[magnitudes > 200]  # threshold
print(f"Dominant frequencies: {sorted(set(abs(peaks)))} Hz")
# → Dominant frequencies: [50.0, 120.0] Hz

The Convolution Theorem

One of the most powerful applications of the Fourier Transform is its relationship to convolution. If $⋆$ denotes convolution:

$F {f ⋆ g} = \hat{f} \cdot \overset{g}{^}$

This means convolution in the time domain becomes pointwise multiplication in the frequency domain. Computing a convolution directly takes $O (N^{2})$ ; via FFT it takes $O (N lo g N)$ .

This is why image blurring, audio effects, and polynomial multiplication all use FFT under the hood.

Key Properties

Property	Statement
Linearity	$F {a f + b g} = a \hat{f} + b \overset{g}{^}$
Time shift	$F {f (t - t_{0})} (ξ) = e^{- 2 π i ξ t_{0}} \hat{f} (ξ)$
Frequency shift	$F {e^{2 π i ξ_{0} t} f (t)} (ξ) = \hat{f} (ξ - ξ_{0})$
Parseval’s theorem	$\int ∥ f (t) ∥^{2} d t = \int ∥ \hat{f} (ξ) ∥^{2} d ξ$
Convolution	$F {f ⋆ g} = \hat{f} \cdot \overset{g}{^}$

Conclusion

The Fourier Transform is the mathematical lens that reveals the hidden frequency structure of any signal. Whether you’re compressing a JPEG, designing a digital filter, or solving a partial differential equation, the same elegant idea applies: decompose into simple waves, operate in frequency space, reconstruct.

“The deep study of nature is the most fruitful source of mathematical discoveries.” — Joseph Fourier, Théorie Analytique de la Chaleur, 1822

That’s still true two centuries later.