Convolution Theorem

⚠️AI-Generated

This file was generated by AI and may require review.

The convolution theorem states that convolution in one domain corresponds to multiplication in the other domain under the Fourier transform.

Statement

For functions $f$ and $g$ with Fourier transforms $F$ and $G$:

$$ \mathcal{F}\{f * g\} = F \cdot G $$

Equivalently (by duality):

$$ \mathcal{F}\{f \cdot g\} = F * G $$

Proof Sketch

Starting from the definition of convolution:

$$ (f * g)(t) = \int_{-\infty}^{\infty} f(\tau) g(t - \tau) \, d\tau $$

Taking the Fourier transform of both sides and using the shift property of the Fourier transform leads to the product of transforms.

Why It Matters

The convolution theorem is one of the most powerful results in signal processing because:

  1. Computational efficiency: Convolution in the time domain is $O(N^2)$; multiplication in frequency domain is $O(N)$. Using FFT, the overall cost becomes $O(N \log N)$.

  2. System analysis: For a linear shift-invariant (LSI) system with impulse response $h(t)$:

    • Output = Input * Impulse response: $y(t) = x(t) * h(t)$
    • In frequency domain: $Y(f) = X(f) \cdot H(f)$

    The transfer function $H(f)$ completely characterizes the system.

  3. Filter design: Design filters by specifying frequency response, then inverse transform.

Applications

  • Fast convolution: FFT-based convolution for large signals
  • Image processing: Blurring, sharpening, edge detection
  • Spectral analysis: Understanding how filtering affects frequency content
  • Deconvolution: Recovering signals from blurred measurements

See Also