Recovering Signals from Noise with the Fast Fourier Transform

Every measurement in the physical world is corrupted by noise. A radio telescope listening for faint pulsar signals, a seismometer recording tremors through kilometers of rock, a microphone in a crowded room — all of them face the same fundamental challenge: the signal you care about is buried under random fluctuations you do not. The Fast Fourier Transform (FFT) is one of the most powerful tools ever devised for separating signal from noise, and understanding how it works will change the way you think about data.

The Problem: Signal Buried in Noise

Imagine you are recording a musical note. The sound is a clean sinusoidal oscillation — but your microphone also picks up electrical hum, thermal noise from the circuitry, and ambient sound from the environment. The result is a messy, jagged waveform. Looking at it in the time domain, it is nearly impossible to tell what the original signal was.

This is not just an engineering annoyance. In fields from medical imaging to gravitational wave detection, the signal-to-noise ratio can be less than one — meaning the noise is louder than the signal. Yet physicists and engineers routinely extract meaningful information from such data. How?

The answer lies in a 200-year-old insight from Joseph Fourier.

---

---

Fourier's Insight

In 1807, Fourier made a remarkable claim: any periodic function can be decomposed into a sum of sine and cosine waves of different frequencies and amplitudes. This means that no matter how complex a signal looks in the time domain, it has an equivalent representation in the frequency domain — a spectrum showing which frequencies are present and how strong each one is.

The continuous Fourier transform maps a time-domain function $f(t)$ to its frequency-domain representation $\hat{f}(\xi)$:

$\hat{f}(\xi) = \int_{-\infty}^{\infty} f(t)\, e^{-2\pi i \xi t}\, dt$

Geometrically, you can think of this as wrapping the signal around a circle at each candidate frequency $\xi$ and measuring how much the wrapped signal clusters to one side. If the signal contains energy at that frequency, the integral does not cancel out — it produces a large value. If not, positive and negative contributions cancel and the result is near zero.

This is what makes frequency-domain analysis so powerful for denoising: a structured signal concentrates its energy at a few specific frequencies, while random noise spreads its energy across all frequencies. In the frequency domain, the signal stands out as sharp peaks above a flat noise floor.

From Continuous to Discrete: The DFT

Real instruments do not record continuous functions — they sample at discrete time intervals. If we have $N$ samples taken at a sampling rate $f_s$, the Discrete Fourier Transform (DFT) is:

$X[k] = \sum_{n=0}^{N-1} x[n]\, e^{-2\pi i kn/N}$

Each output $X[k]$ tells you the amplitude and phase of the frequency component at $f_k = k \cdot f_s / N$. The Nyquist theorem tells us we can only faithfully represent frequencies up to $f_s / 2$ — any higher frequencies will be aliased (folded back) into lower ones. This is why audio is sampled at 44,100 Hz: it captures frequencies up to about 22 kHz, the upper limit of human hearing.

The DFT as written above requires $O(N^2)$ operations — for each of the $N$ output frequencies, you sum over all $N$ input samples. For a million data points, that is a trillion operations. Impractical for real-time processing.

The Fast Fourier Transform (FFT)

In 1965, James Cooley and John Tukey published an algorithm that changed scientific computing forever. The Cooley-Tukey FFT exploits symmetry in the DFT to reduce the computation from $O(N^2)$ to $O(N \log N)$.

The key idea is divide and conquer. Split the $N$-point DFT into two $N/2$-point DFTs — one for even-indexed samples and one for odd-indexed samples. Each half-size DFT can be split again, recursively, until you reach trivial 2-point transforms. The results are combined using twiddle factors $e^{-2\pi i k/N}$ that rotate the complex coefficients appropriately.

For $N = 2048$ samples, the naive DFT needs about 4.2 million complex multiplications. The FFT needs only about 11,000 — a speedup of nearly 400x. This is why the FFT has been called one of the most important algorithms of the 20th century.

The Power Spectrum

The FFT gives us complex-valued coefficients $X[k]$. To see which frequencies dominate, we compute the power spectrum:

$P[k] = \frac{|X[k]|^2}{N}$

Each value $P[k]$ represents the power (energy per unit time) at frequency $f_k$. Sharp peaks in the power spectrum correspond to strong periodic components in the signal. The noise floor — the baseline level across all frequencies — represents the distributed energy of random noise.

Denoising by Spectral Filtering

The denoising strategy is beautifully simple:

1. Transform the noisy signal to the frequency domain using the FFT
2. Identify the signal peaks: frequencies where the power exceeds a threshold
3. Zero out all FFT coefficients below the threshold — these are dominated by noise
4. Inverse transform back to the time domain to recover the clean signal

This works because noise is broadband (spread across all frequencies) while most real signals are narrowband (concentrated at specific frequencies). By keeping only the high-power frequency bins, you retain the signal and discard most of the noise.

The choice of threshold is critical. Too low, and you let noise through. Too high, and you clip the signal itself. In practice, more sophisticated methods like Wiener filtering or wavelet denoising adapt the threshold to the local noise level — but the basic principle remains the same.

Things to Try

1. Start with defaults (220 Hz + 440 Hz, noise = 1.5). Notice how the power spectrum shows two clear peaks above the noise floor. The recovered signal closely matches the clean original.

2. Crank up the noise to 3.0. The time-domain signal becomes unrecognizable, but the frequency peaks still stand out in the power spectrum. Adjust the threshold to recover the signal — this is how radio astronomers detect faint signals in cosmic static.

3. Add a third frequency by setting Amplitude 3 to 1.0 (880 Hz). Watch three peaks appear in the spectrum. This demonstrates how the FFT cleanly separates multiple frequency components that overlap in time.

4. Set two frequencies very close together (e.g., 200 Hz and 210 Hz). The power spectrum shows two distinct peaks — the FFT's frequency resolution is $f_s / N = 1$ Hz, so it can resolve components just 1 Hz apart (with 1 second of data).

5. Set the threshold to zero and observe how the recovered signal retains all the noise. Then slowly raise it — you will see the noise floor vanish from the filtered spectrum while the peaks remain.

Real-World Applications

• Audio engineering: noise reduction in recordings, spectral equalization, and auto-tune all rely on the FFT to decompose sound into frequency components.

• Medical imaging (MRI): magnetic resonance imaging acquires data directly in the frequency domain (k-space). The image you see is literally the inverse FFT of the raw measurements.

• Telecommunications: OFDM (Orthogonal Frequency-Division Multiplexing), the encoding used in WiFi and 4G/5G, uses the FFT to modulate and demodulate thousands of data subcarriers simultaneously.

• Gravitational wave detection: LIGO's detectors measure mirror displacements smaller than a proton. The signals are extracted from overwhelming instrumental noise using matched filtering in the frequency domain — powered by the FFT.

• Crystallography: X-ray diffraction patterns are the Fourier transform of a crystal's electron density. Inverting them reveals molecular structures, including the double helix of DNA.

The FFT did not just speed up an existing calculation — it made entirely new fields of science possible. Any time you listen to compressed audio, view an MRI scan, or connect to WiFi, you are using an algorithm that Joseph Fourier could never have imagined, built on mathematics he understood perfectly.