diff options
Diffstat (limited to 'source/know/concept/convolution-theorem')
-rw-r--r-- | source/know/concept/convolution-theorem/index.md | 116 |
1 files changed, 116 insertions, 0 deletions
diff --git a/source/know/concept/convolution-theorem/index.md b/source/know/concept/convolution-theorem/index.md new file mode 100644 index 0000000..d6c578b --- /dev/null +++ b/source/know/concept/convolution-theorem/index.md @@ -0,0 +1,116 @@ +--- +title: "Convolution theorem" +date: 2021-02-22 +categories: +- Mathematics +layout: "concept" +--- + +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](/know/concept/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}$$ + +<div class="accordion"> +<input type="checkbox" id="proof-fourier"/> +<label for="proof-fourier">Proof</label> +<div class="hidden"> +<label for="proof-fourier">Proof.</label> +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 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}$$ +</div> +</div> + + +## 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](/know/concept/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 +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}$$ + +<div class="accordion"> +<input type="checkbox" id="proof-laplace"/> +<label for="proof-laplace">Proof</label> +<div class="hidden"> +<label for="proof-laplace">Proof.</label> +We expand 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}$$ +</div> +</div> + + + +## References +1. O. Bang, + *Applied mathematics for physicists: lecture notes*, 2019, + unpublished. |