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}$$
+
+<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.
-- 
cgit v1.2.3