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 (f∗g)(x)=F^−1{f~(k) g~(k)}B (f~∗g~)(k)=F^{f(x) g(x)}\begin{aligned} \boxed{ \begin{aligned} A \: (f * g)(x) &= \hat{\mathcal{F}}{}^{-1}\Big\{ \tilde{f}(k) \: \tilde{g}(k) \Big\} \\ B \: (\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)}=B∫−∞∞f~(k)(A∫−∞∞g(x′) eiskx′dx′)e−iskxdk=A∫−∞∞g(x′)(B∫−∞∞f~(k) e−isk(x−x′)dk)dx′=A∫−∞∞g(x′) f(x−x′)dx′=A (f∗g)(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 \: (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)}=A∫−∞∞f(x)(B∫−∞∞g~(k′) e−isxk′dk′)eiskxdx=B∫−∞∞g~(k′)(A∫−∞∞f(x) eisx(k−k′)dx)dk′=B∫−∞∞g~(k′) f~(k−k′)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 \: (\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 t≥0t \ge 0, the convolution theorem can also be stated using the Laplace transform:

(f∗g)(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^{(f∗g)(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^{(f∗g)(t)}=∫0∞(∫0∞g(t′) f(t−t′)dt′)e−stdt=∫0∞(∫0∞f(t−t′) e−stdt) 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 τ=t−t′\tau = t - t', yielding:

L^{(f∗g)(t)}=∫0∞(∫0∞f(τ) e−s(τ+t′)dτ) g(t′)dt′=∫0∞(∫0∞f(τ) e−sτdτ) g(t′) e−st′dt′=∫0∞f~(s) g(t′) e−st′dt′=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.