From c2327bcc3571ead88ba2b0ce40656211a888f640 Mon Sep 17 00:00:00 2001
From: Prefetch
Date: Sun, 21 Feb 2021 16:46:21 +0100
Subject: Add "Convolution theorem" and "Parseval's theorem"

---
 latex/know/concept/convolution-theorem/source.md  | 91 +++++++++++++++++++++++
 latex/know/concept/dirac-delta-function/source.md |  2 +-
 latex/know/concept/fourier-transform/source.md    |  8 +-
 latex/know/concept/parsevals-theorem/source.md    | 64 ++++++++++++++++
 4 files changed, 159 insertions(+), 6 deletions(-)
 create mode 100644 latex/know/concept/convolution-theorem/source.md
 create mode 100644 latex/know/concept/parsevals-theorem/source.md

(limited to 'latex/know')

diff --git a/latex/know/concept/convolution-theorem/source.md b/latex/know/concept/convolution-theorem/source.md
new file mode 100644
index 0000000..347787f
--- /dev/null
+++ b/latex/know/concept/convolution-theorem/source.md
@@ -0,0 +1,91 @@
+% Convolution theorem
+
+
+# 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}$$
diff --git a/latex/know/concept/dirac-delta-function/source.md b/latex/know/concept/dirac-delta-function/source.md
index cb98c41..4de0cfd 100644
--- a/latex/know/concept/dirac-delta-function/source.md
+++ b/latex/know/concept/dirac-delta-function/source.md
@@ -41,7 +41,7 @@ $$\begin{aligned}
 
 The last one is especially important, since it is equivalent to the
 following integral, which appears very often in the context of
-Fourier transforms:
+[Fourier transforms](/know/concept/fourier-transform/):
 
 $$\begin{aligned}
     \boxed{
diff --git a/latex/know/concept/fourier-transform/source.md b/latex/know/concept/fourier-transform/source.md
index 58830df..3e25980 100644
--- a/latex/know/concept/fourier-transform/source.md
+++ b/latex/know/concept/fourier-transform/source.md
@@ -63,10 +63,9 @@ on whether the analysis is for forward ($s > 0$) or backward-propagating
 
 ## Derivatives
 
-The FT of a derivative has a very interesting property, let us take a
-look. Below, after integrating by parts, we remove the boundary term by
-assuming that $f(x)$ is localized, i.e. $f(x) \to 0$ for
-$x \to \pm \infty$:
+The FT of a derivative has a very interesting property.
+Below, after integrating by parts, we remove the boundary term by
+assuming that $f(x)$ is localized, i.e. $f(x) \to 0$ for $x \to \pm \infty$:
 
 $$\begin{aligned}
     \hat{\mathcal{F}}\{f'(x)\}
@@ -75,7 +74,6 @@ $$\begin{aligned}
     &= A \big[ f(x) \exp(i s k x) \big]_{-\infty}^\infty - i s k A \int_{-\infty}^\infty f(x) \exp(i s k x) \dd{x}
     \\
     &= (- i s k) \tilde{f}(k)
-    \qedhere
 \end{aligned}$$
 
 Therefore, as long as $f(x)$ is localized, the FT eliminates derivatives
diff --git a/latex/know/concept/parsevals-theorem/source.md b/latex/know/concept/parsevals-theorem/source.md
new file mode 100644
index 0000000..41af734
--- /dev/null
+++ b/latex/know/concept/parsevals-theorem/source.md
@@ -0,0 +1,64 @@
+% Parseval's theorem
+
+
+# Parseval's theorem
+
+**Parseval's theorem** relates the inner product of two functions to the
+inner product of their [Fourier transforms](/know/concept/fourier-transform/).
+There are two equivalent ways of stating it,
+where $A$, $B$, and $s$ are constants from the Fourier transform's definition:
+
+$$\begin{aligned}
+    \boxed{
+        \braket{f(x)}{g(x)} = \frac{2 \pi B^2}{|s|} \braket{\tilde{f}(k)}{\tilde{g}(k)}
+    }
+    \\
+    \boxed{
+        \braket{\tilde{f}(k)}{\tilde{g}(k)} = \frac{2 \pi A^2}{|s|} \braket{f(x)}{g(x)}
+    }
+\end{aligned}$$
+
+For this reason many physicists like to define their Fourier transform
+with $|s| = 1$ and $A = B = 1 / \sqrt{2\pi}$, because then the FT nicely
+conserves the total probability (quantum mechanics) or the total energy
+(optics).
+
+To prove this, we insert the inverse FT into the inner product
+definition:
+
+$$\begin{aligned}
+    \braket{f}{g}
+    &= \int_{-\infty}^\infty \big( \hat{\mathcal{F}}^{-1}\{\tilde{f}(k)\}\big)^* \: \hat{\mathcal{F}}^{-1}\{\tilde{g}(k)\} \dd{x}
+    \\
+    &= B^2 \int
+    \Big( \int \tilde{f}^*(k_1) \exp(i s k_1 x) \dd{k_1} \Big)
+    \Big( \int \tilde{g}(k) \exp(- i s k x) \dd{k} \Big)
+    \dd{x}
+    \\
+    &= 2 \pi B^2 \iint \tilde{f}^*(k_1) \tilde{g}(k) \Big( \frac{1}{2 \pi} \int_{-\infty}^\infty \exp(i s x (k_1 - k)) \dd{x} \Big) \dd{k_1} \dd{k}
+    \\
+    &= 2 \pi B^2 \iint \tilde{f}^*(k_1) \: \tilde{g}(k) \: \delta(s (k_1 - k)) \dd{k_1} \dd{k}
+    \\
+    &= \frac{2 \pi B^2}{|s|} \int_{-\infty}^\infty \tilde{f}^*(k) \: \tilde{g}(k) \dd{k}
+    = \frac{2 \pi B^2}{|s|} \braket{\tilde{f}}{\tilde{g}}
+\end{aligned}$$
+
+Where $\delta(k)$ is the [Dirac delta function](/know/concept/dirac-delta-function/).
+We can just as well do it in the opposite direction, with equivalent results:
+
+$$\begin{aligned}
+    \braket{\tilde{f}}{\tilde{g}}
+    &= \int_{-\infty}^\infty \big( \hat{\mathcal{F}}\{f(x)\}\big)^* \: \hat{\mathcal{F}}\{g(x)\} \dd{k}
+    \\
+    &= A^2 \int
+    \Big( \int f^*(x_1) \exp(- i s k x_1) \dd{x_1} \Big)
+    \Big( \int g(x) \exp(i s k x) \dd{x} \Big)
+    \dd{k}
+    \\
+    &= 2 \pi A^2 \iint f^*(x_1) g(x) \Big( \frac{1}{2 \pi} \int_{-\infty}^\infty \exp(i s k (x_1 - x)) \dd{k} \Big) \dd{x_1} \dd{x}
+    \\
+    &= 2 \pi A^2 \iint f^*(x_1) \: g(x) \: \delta(s (x_1 - x)) \dd{x_1} \dd{x}
+    \\
+    &= \frac{2 \pi A^2}{|s|} \int_{-\infty}^\infty f^*(x) \: g(x) \dd{x}
+    = \frac{2 \pi A^2}{|s|} \braket{f}{g}
+\end{aligned}$$
-- 
cgit v1.2.3