Categories: Mathematics.

# Convolution theorem

The convolution theorem states that a convolution in the real domain is equal to a product in the frequency domain. This fact is especially useful for computation, as it allows replacing an $\mathcal{O}(n^2)$ convolution with an $\mathcal{O}(n \log(n))$ transform and product.

## Fourier transform

The convolution theorem is usually expressed as follows, where $\hat{\mathcal{F}}$ is the Fourier transform, and $A$ and $B$ are the constants from its definition:

\begin{aligned} \boxed{ \begin{aligned} A \cdot (f * g)(x) &= \hat{\mathcal{F}}{}^{-1}\Big\{ \tilde{f}(k) \: \tilde{g}(k) \Big\} \\ B \cdot (\tilde{f} * \tilde{g})(k) &= \hat{\mathcal{F}}\Big\{ f(x) \: g(x) \Big\} \end{aligned} } \end{aligned}

We expand the right-hand side of the theorem and rearrange the integrals:

\begin{aligned} \hat{\mathcal{F}}{}^{-1}\Big\{ \tilde{f}(k) \: \tilde{g}(k) \Big\} &= B \int_{-\infty}^\infty \tilde{f}(k) \bigg( A \int_{-\infty}^\infty g(x') \: e^{i s k x'} \dd{x'} \bigg) e^{-i s k x} \dd{k} \\ &= A \int_{-\infty}^\infty g(x') \bigg( B \int_{-\infty}^\infty \tilde{f}(k) \: e^{-i s k (x - x')} \dd{k} \bigg) \dd{x'} \\ &= A \int_{-\infty}^\infty g(x') \: f(x - x') \dd{x'} \\ &= A \cdot (f * g)(x) \end{aligned}

Then we do the same again, this time starting from a product in the $x$-domain:

\begin{aligned} \hat{\mathcal{F}}\Big\{ f(x) \: g(x) \Big\} &= A \int_{-\infty}^\infty f(x) \bigg( B \int_{-\infty}^\infty \tilde{g}(k') \: e^{-i s x k'} \dd{k'} \bigg) e^{i s k x} \dd{x} \\ &= B \int_{-\infty}^\infty \tilde{g}(k') \bigg( A \int_{-\infty}^\infty f(x) \: e^{i s x (k - k')} \dd{x} \bigg) \dd{k'} \\ &= B \int_{-\infty}^\infty \tilde{g}(k') \: \tilde{f}(k - k') \dd{k'} \\ &= B \cdot (\tilde{f} * \tilde{g})(k) \end{aligned}

## Laplace transform

For functions $f(t)$ and $g(t)$ that are only defined for $t \ge 0$, the convolution theorem can also be stated using the Laplace transform:

\begin{aligned} \boxed{ (f * g)(t) = \hat{\mathcal{L}}{}^{-1}\Big\{ \tilde{f}(s) \: \tilde{g}(s) \Big\} } \end{aligned}

Because the inverse Laplace transform $\hat{\mathcal{L}}{}^{-1}$ is usually difficult, the theorem is often stated using the forward transform instead:

\begin{aligned} \boxed{ \hat{\mathcal{L}}\Big\{ (f * g)(t) \Big\} = \tilde{f}(s) \: \tilde{g}(s) } \end{aligned}

We expand the left-hand side. Note that the lower integration limit is 0 instead of $-\infty$, because we choose to set both $f(t)$ and $g(t)$ to zero for $t < 0$:

\begin{aligned} \hat{\mathcal{L}}\Big\{ (f * g)(t) \Big\} &= \int_0^\infty \bigg( \int_0^\infty g(t') \: f(t - t') \dd{t'} \bigg) e^{-s t} \dd{t} \\ &= \int_0^\infty \bigg( \int_0^\infty f(t - t') \: e^{-s t} \dd{t} \bigg) \: g(t') \dd{t'} \end{aligned}

Then we define a new integration variable $\tau = t - t'$, yielding:

\begin{aligned} \hat{\mathcal{L}}\Big\{ (f * g)(t) \Big\} &= \int_0^\infty \bigg( \int_0^\infty f(\tau) \: e^{-s (\tau + t')} \dd{\tau} \bigg) \: g(t') \dd{t'} \\ &= \int_0^\infty \bigg( \int_0^\infty f(\tau) \: e^{-s \tau} \dd{\tau} \bigg) \: g(t') \: e^{-s t'} \dd{t'} \\ &= \int_0^\infty \tilde{f}(s) \: g(t') \: e^{-s t'} \dd{t'} \\ &= \tilde{f}(s) \: \tilde{g}(s) \end{aligned}

## References

1. O. Bang, Applied mathematics for physicists: lecture notes, 2019, unpublished.