Convolution Theorem

Convolution in time equals multiplication in frequency, so filtering means transform, scale each tone, and transform back.

Sliding convolution in time becomes pointwise scaling in frequency, and the inverse transform returns the filtered signal

Why Does This Exist?

Smoothing, edge detection, and reverberation are all convolutions: each output mixes neighboring inputs through a kernel. Direct sliding costs $O(nm)$ for $n$ samples and kernel length $m$ : a $10$ -second audio track against a $2$ -second reverb needs $10^{10}$ multiplies. The convolution theorem rewrites the operation as $\widehat{f * g} = \hat{f} \cdot \hat{g}$ : transform both, multiply pointwise, invert. Cost drops to $O(n \log n)$ , and filter design becomes drawing a frequency response instead of tuning taps. Continuous spectra are the parent Fourier page; fast transforms are DFT and FFT.

The one idea you need first

Convolution $(f * g)[t] = \sum_s f[s] g[t-s]$ slides one signal past the other accumulating products. Exponentials are its eigenfunctions: convolving a tone returns the same tone scaled, which is why tones diagonalize the operation.

Think of It Like This

Stamping with shaped sponges

Pressing a star sponge across paper (sliding convolution) paints stars everywhere slowly. Instead, photograph the sponge's pattern once (transform the kernel), photograph the paper once (transform the signal), multiply the photos pixelwise (cheap scaling per tone), and develop the result (invert). Same gallery wall, fraction of the stamping.

Filter design is choosing the sponge photo: keep star pixels (passband), black out the rest (stopband). Deconvolution tries to divide the photos back apart, which blows up where the sponge photo is near black.

How It Actually Works

For suitable $f, g$ : $\mathcal{F}\{f * g\} = \mathcal{F}\{f\} \cdot \mathcal{F}\{g\}$ pointwise. Filtering pipeline: FFT both to length $n + m$ , multiply binwise by the frequency response $H_k$ , inverse FFT. Cost $O(n \log n)$ versus $O(nm)$ direct. The crossover sits near $m \approx 64$ taps for typical FFT constants.

Frequency response $H_k$ is the filter's fingerprint: $|H_k| \approx 1$ passes tone $k$ , $|H_k| \approx 0$ stops it. Deconvolution divides by $H_k$ (Wiener adds noise-floor regularization $S_n/S_s$ to tame near-zero bins).

Worked example

Signal length $n = 8{,}000$ , kernel $m = 500$ . Direct: $8{,}000 \times 500 = 4.0$ million multiplies. FFT route: pad to $8{,}192$ , two forward plus one inverse FFT at $8{,}192 \times 13 \approx 106{,}000$ each, plus $8{,}192$ multiplies: about $330{,}000$ operations. Ratio $4{,}000{,}000 / 330{,}000 \approx 12$ : twelve times faster, widening with $m$ . A $3$ -tap smoother $[1/3, 1/3, 1/3]$ has response $H_k = (1 + 2\cos(2\pi k/n))/3$ : $|H_0| = 1$ (DC passes), first null where $\cos = -1/2$ : tone at $n/3$ removed exactly.

Code

1def direct_conv(xs: list[float], h: list[float]) -> list[float]:2    n, m = len(xs), len(h)3    return [sum(xs[t - s] * h[s] for s in range(m) if 0 <= t - s < n) for t in range(n)]4
5
6xs = [1.0, 2.0, 3.0, 4.0, 5.0]7print(direct_conv(xs, [1 / 3, 1 / 3, 1 / 3]))  # moving average8# -> [0.333, 1.0, 2.0, 3.0, 4.0] (edges use fewer taps)

Interior outputs average full windows ( $2.0$ , $3.0$ , $4.0$ ); edges average available taps, showing boundary handling explicitly.

Watch Out For

Circular versus linear convolution mix-ups

FFT multiplication implements circular convolution: tails wrap around. Forgetting zero-padding to $n + m - 1$ smears the track's end into its start. Symptoms: clicks at block boundaries in audio, glowing frame edges in images. Pad first, always.

Inverting near-zero response bins

Deconvolution divides by $H_k \approx 0$ where the filter killed tones, amplifying noise thousandfold there. Naive inverses of smoothed observations explode. Regularize (Wiener: divide by $|H|^2 + \text{noise}/\text{signal}$ ) and distrust recovered bins the forward filter stopped.

The Quick Version

Convolution in time is multiplication in frequency, pointwise per tone.
The $8{,}000 \times 500$ example runs about $12$ times faster via FFT.
Crossover to FFT methods sits near $64$ taps for standard constants.
Filter design draws the response $H_k$ ; the $3$ -tap smoother nulls tone $n/3$ .
Pad to $n + m - 1$ or circular wrap corrupts boundaries.
Deconvolution needs Wiener regularization where responses approach zero.