From 6ce0bb9a8f9fd7d169cbb414a9537d68c5290aae Mon Sep 17 00:00:00 2001
From: Prefetch
Date: Fri, 14 Oct 2022 23:25:28 +0200
Subject: Initial commit after migration from Hugo
---
source/know/concept/convolution-theorem/index.md | 116 +++++++++++++++++++++++
1 file changed, 116 insertions(+)
create mode 100644 source/know/concept/convolution-theorem/index.md
(limited to 'source/know/concept/convolution-theorem')
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}$$
+
+
+
+
+
+
+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}$$
+
+
+
+
+## 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}$$
+
+
+
+
+
+
+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}$$
+