blob: a14e96069d916a94d20a38e4c61f297e1d5a5317 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
---
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}$$
<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.
|
