diff options
-rw-r--r-- | content/know/category/mathematics.md | 6 | ||||
-rw-r--r-- | content/know/category/physics.md | 4 | ||||
-rw-r--r-- | content/know/concept/index.md | 4 | ||||
-rw-r--r-- | latex/know/concept/convolution-theorem/source.md | 91 | ||||
-rw-r--r-- | latex/know/concept/dirac-delta-function/source.md | 2 | ||||
-rw-r--r-- | latex/know/concept/fourier-transform/source.md | 8 | ||||
-rw-r--r-- | latex/know/concept/parsevals-theorem/source.md | 64 |
7 files changed, 173 insertions, 6 deletions
diff --git a/content/know/category/mathematics.md b/content/know/category/mathematics.md index 76106f2..23b115d 100644 --- a/content/know/category/mathematics.md +++ b/content/know/category/mathematics.md @@ -6,8 +6,14 @@ title = "Category: mathematics" Alphabetical list of concepts in this category. +## C +* [Convolution theorem](/know/concept/convolution-theorem/) + ## D * [Dirac delta function](/know/concept/dirac-delta-function/) ## F * [Fourier transform](/know/concept/fourier-transform/) + +## P +* [Parseval's theorem](/know/concept/parsevals-theorem/) diff --git a/content/know/category/physics.md b/content/know/category/physics.md index ff6b4e8..9458bfd 100644 --- a/content/know/category/physics.md +++ b/content/know/category/physics.md @@ -9,6 +9,9 @@ Alphabetical list of concepts in this category. ## B * [Bloch's theorem](/know/concept/blochs-theorem/) +## C +* [Convolution theorem](/know/concept/convolution-theorem/) + ## F * [Fourier transform](/know/concept/fourier-transform/) @@ -17,6 +20,7 @@ Alphabetical list of concepts in this category. * [Dirac notation](/know/concept/dirac-notation/) ## P +* [Parseval's theorem](/know/concept/parsevals-theorem/) * [Pauli exclusion principle](/know/concept/pauli-exclusion-principle/) * [Probability current](/know/concept/probability-current/) diff --git a/content/know/concept/index.md b/content/know/concept/index.md index 84df249..ed73007 100644 --- a/content/know/concept/index.md +++ b/content/know/concept/index.md @@ -9,6 +9,9 @@ Alphabetical list of concepts in this knowledge base. ## B * [Bloch's theorem](/know/concept/blochs-theorem/) +## C +* [Convolution theorem](/know/concept/convolution-theorem/) + ## D * [Dirac delta function](/know/concept/dirac-delta-function/) * [Dirac notation](/know/concept/dirac-notation/) @@ -17,6 +20,7 @@ Alphabetical list of concepts in this knowledge base. * [Fourier transform](/know/concept/fourier-transform/) ## P +* [Parseval's theorem](/know/concept/parsevals-theorem/) * [Pauli exclusion principle](/know/concept/pauli-exclusion-principle/) * [Probability current](/know/concept/probability-current/) 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}$$ |