Convolution theorem for FT with importance

Statement

If F(s) and G(s) are the Fourier transforms of f(x) and g(x), then the Fourier transform of the convolution (f * g)(x) = ∫ f(u) g(x − u) du is the product:

F{f * g} = F(s) · G(s)

(With the 1/√(2π) normalisation the right side carries an extra factor √(2π).)

Importance

1. Convolution becomes multiplication. Direct convolution needs an integral for every x. In the frequency domain it needs only a product, which is far easier.
2. Linear systems and filters. The output of a linear time-invariant system is y = h * x (h is the impulse response). By the theorem Y(s) = H(s)X(s), so the system is described by its frequency response H(s). Filtering in signal processing is done this way.
3. Fast computation. With the FFT, convolution of long sequences costs O(N log N) instead of O(N²).
4. Solving equations. Integral equations of convolution type and some differential equations are reduced to algebraic ones.
5. Inverse transforms. The inverse of a product F(s)G(s) can be obtained as the convolution f * g.

Example

Let f(x) = g(x) = e^{−x²}. Then F(s) = G(s) = √π e^{−s²/4}, so

F(s)G(s) = π e^{−s²/2}

The inverse transform of this product is f * g = √(π/2) e^{−x²/2}. The same result follows from the direct integral ∫ e^{−u²} e^{−(x−u)²} du, but the frequency-domain route is much shorter. It also shows that the convolution of two Gaussians is again a Gaussian.