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 O(n2)\mathcal{O}(n^2) convolution with an O(nlog(n))\mathcal{O}(n \log(n)) transform and product.

Fourier transform

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

A(fg)(x)=F^1{f~(k)g~(k)}B(f~g~)(k)=F^{f(x)g(x)}\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:

F^1{f~(k)g~(k)}=Bf~(k)(Ag(x)eiskxdx)eiskxdk=Ag(x)(Bf~(k)eisk(xx)dk)dx=Ag(x)f(xx)dx=A(fg)(x)\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 xx-domain:

F^{f(x)g(x)}=Af(x)(Bg~(k)eisxkdk)eiskxdx=Bg~(k)(Af(x)eisx(kk)dx)dk=Bg~(k)f~(kk)dk=B(f~g~)(k)\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)f(t) and g(t)g(t) that are only defined for t0t \ge 0, the convolution theorem can also be stated using the Laplace transform:

(fg)(t)=L^1{f~(s)g~(s)}\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 L^1\hat{\mathcal{L}}{}^{-1} is usually difficult, the theorem is often stated using the forward transform instead:

L^{(fg)(t)}=f~(s)g~(s)\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)f(t) and g(t)g(t) to zero for t<0t < 0:

L^{(fg)(t)}=0(0g(t)f(tt)dt)estdt=0(0f(tt)estdt)g(t)dt\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 τ=tt\tau = t - t', yielding:

L^{(fg)(t)}=0(0f(τ)es(τ+t)dτ)g(t)dt=0(0f(τ)esτdτ)g(t)estdt=0f~(s)g(t)estdt=f~(s)g~(s)\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.