Categories: Mathematics.

Convolution theorem

The convolution theorem states that a convolution in the direct domain is equal to a product in the frequency domain. This is especially useful for computation, 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 constants from its definition:

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

To prove this, we expand the right-hand side of the theorem and rearrange the integrals:

\[\begin{aligned} \hat{\mathcal{F}}^{-1}\{\tilde{f}(k) \: \tilde{g}(k)\} &= B \int_{-\infty}^\infty \tilde{f}(k) \Big( A \int_{-\infty}^\infty g(x') \exp(i s k x') \dd{x'} \Big) \exp(-i s k x) \dd{k} \\ &= A \int_{-\infty}^\infty g(x') \Big( B \int_{-\infty}^\infty \tilde{f}(k) \exp(- i s k (x - x')) \dd{k} \Big) \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 thing again, this time starting from a product in the \(x\)-domain:

\[\begin{aligned} \hat{\mathcal{F}}\{f(x) \: g(x)\} &= A \int_{-\infty}^\infty f(x) \Big( B \int_{-\infty}^\infty \tilde{g}(k') \exp(- i s x k') \dd{k'} \Big) \exp(i s k x) \dd{x} \\ &= B \int_{-\infty}^\infty \tilde{g}(k') \Big( A \int_{-\infty}^\infty f(x) \exp(i s x (k - k')) \dd{x} \Big) \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)\) which 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}\{\tilde{f}(s) \: \tilde{g}(s)\}} \end{aligned}\]

Because the inverse Laplace transform \(\hat{\mathcal{L}}^{-1}\) is quite unpleasant, the theorem is often stated using the forward transform instead:

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

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

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

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

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

© "Prefetch". Licensed under CC BY-SA 4.0.