The Fourier Transform: From Sines to Signals

The Fourier transform is everywhere — in your phone's WiFi, in JPEG compression, in quantum mechanics. At its core it answers a deceptively simple question: what frequencies make up this signal?

The Core Idea

Any periodic signal $f(t)$ can be written as a sum of sines and cosines:

The coefficients $a_n$ and $b_n$ tell us how much of each frequency is present. Computing them is the Fourier transform.

Interactive: Fourier Series Approximation

The pink wave below is a square wave — famously impossible to represent with a finite number of sines. Watch what happens as we add more harmonics:

The ripples near the discontinuities that never quite go away are called Gibbs phenomenon. Even with infinite harmonics they persist — peaking at about 9% overshoot.

The Continuous Fourier Transform

Moving from discrete harmonics to a continuous spectrum, the Fourier transform of $f$ is:

And the inverse recovers $f$ from its spectrum:

This is profound: you can freely move between the time domain and frequency domain.

Computing it in Python

The standard algorithm is the Fast Fourier Transform (FFT) — $O(n \log n)$ instead of the naive $O(n^2)$.

import numpy as np
import matplotlib.pyplot as plt
 
# Generate a noisy signal
t = np.linspace(0, 1, 1000, endpoint=False)
signal = np.sin(2 * np.pi * 50 * t) + 0.5 * np.sin(2 * np.pi * 120 * t)
signal += 0.2 * np.random.randn(len(t))   # add noise
 
# Compute the FFT
freqs = np.fft.fftfreq(len(t), d=t[1] - t[0])
spectrum = np.abs(np.fft.fft(signal))
 
# Plot only positive frequencies
pos = freqs > 0
plt.plot(freqs[pos], spectrum[pos])
plt.xlabel("Frequency (Hz)")
plt.ylabel("|X(f)|")
plt.title("Frequency Spectrum")
plt.show()

The two peaks at 50 Hz and 120 Hz pop out clearly, even though the signal looked like noise in the time domain.

The Convolution Theorem

One of the Fourier transform's killer applications is convolution. In the time domain:

This is expensive — $O(n^2)$. But in the frequency domain it becomes pointwise multiplication:

This is why image blurring, audio filtering, and polynomial multiplication can all be done in $O(n \log n)$.

def fast_convolve(f, g):
    """Convolve two signals using FFT — O(n log n)."""
    n = len(f) + len(g) - 1
    F = np.fft.rfft(f, n=n)
    G = np.fft.rfft(g, n=n)
    return np.fft.irfft(F * G, n=n)

Further Reading

• Stein & Shakarchi, Fourier Analysis: An Introduction
• 3Blue1Brown's visual explanation on YouTube
• Cooley & Tukey's 1965 paper introducing the FFT algorithm