1 files changed, 100 insertions, 0 deletions
diff --git a/content/know/concept/convolution-theorem/index.pdc b/content/know/concept/convolution-theorem/index.pdc
new file mode 100644
index 0000000..fc96f30
--- /dev/null
+++ b/content/know/concept/convolution-theorem/index.pdc
@@ -0,0 +1,100 @@
+---
+title: "Convolution theorem"
+firstLetter: "C"
+publishDate: 2021-02-22
+categories:
+- Mathematics
+
+date: 2021-02-22T21:35:23+01:00
+draft: false
+markup: pandoc
+---
+
+# 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](/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}$$
+
+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}$$