Edit filter log

'In [[mathematics]], the '''convolution theorem''' states that under suitable conditions the [[Fourier transform]] of a [[convolution]] is the [[pointwise product]] of Fourier transforms. In other words, convolution in one domain (e.g., [[time domain]]) equals point-wise multiplication in the other domain (e.g., [[frequency domain]]). Versions of the convolution theorem are true for various [[List of Fourier-related transforms|Fourier-related transforms]]. Let <math>\ f</math> and <math>\ g</math> be two [[function (mathematics)|function]]s with [[convolution]] <math>\ f*g </math>. (Note that the [[asterisk]] denotes convolution in this context, and not multiplication. The [[tensor product]] symbol <math>\otimes</math> is sometimes used instead.) Let <math>\ \mathcal{F}</math> denote the Fourier transform [[operator (mathematics)|operator]], so <math>\ \mathcal{F}\{f\}</math> and <math>\ \mathcal{F}\{g\}</math> are the Fourier transforms of <math>\ f</math> and <math>\ g</math>, respectively. Then : <math>\mathcal{F}\{f*g\} = \mathcal{F}\{f\} \cdot \mathcal{F}\{g\}</math> where <math>\cdot</math> denotes point-wise multiplication. It also works the other way around: : <math>\mathcal{F}\{f \cdot g\}= \mathcal{F}\{f\}*\mathcal{F}\{g\}</math> By applying the inverse Fourier transform <math>\mathcal{F}^{-1}</math>, we can write: : <math>f*g= \mathcal{F}^{-1}\big\{\mathcal{F}\{f\}\cdot\mathcal{F}\{g\}\big\}</math> Note that the relationships above are only valid for the form of the Fourier transform shown in the [[#Proof|Proof]] section below. The transform may be normalised in other ways, in which case constant scaling factors (typically <math>\ 2\pi</math> or <math>\ \sqrt{2\pi}</math>) will appear in the relationships above. This theorem also holds for the [[Laplace transform]], the [[two-sided Laplace transform]] and, when suitably modified, for the [[Mellin transform]] and [[Hartley transform]] (see [[Mellin inversion theorem]]). It can be extended to the Fourier transform of [[abstract harmonic analysis]] defined over [[locally compact abelian group]]s. This formulation is especially useful for implementing a numerical convolution on a [[computer]]: The standard convolution algorithm has [[Quadratic function|quadratic]] [[computational complexity]]. With the help of the convolution theorem and the [[fast Fourier transform]], the complexity of the convolution can be reduced to O(''n'' log ''n''). This can be exploited to construct fast [[multiplication algorithm]]s. === Proof === ''The proof here is shown for a particular normalisation of the Fourier transform. As mentioned above, if the transform is normalised differently, then constant scaling factors will appear in the derivation.'' Let ''f'', ''g'' belong to ''L''¹('''R'''^''n''). Let <math>F</math> be the Fourier transform of <math>f</math> and <math>G</math> be the Fourier transform of <math>g</math>: :<math>F(\nu) = \mathcal{F}\{f\} = \int_{\mathbb{R}^n} f(x) e^{-2 \pi i x\cdot\nu} \, \mathrm{d}x </math> :<math>G(\nu) = \mathcal{F}\{g\} = \int_{\mathbb{R}^n}g(x) e^{-2 \pi i x\cdot\nu} \, \mathrm{d}x, </math> where the ''dot'' between ''x'' and ''ν'' indicates the inner product of '''R'''^''n''. Let <math>h</math> be the [[convolution]] of <math>f</math> and <math>g</math> :<math>h(z) = \int\limits_{\mathbb{R}^n} f(x) g(z-x)\, \mathrm{d} x. </math> Now notice that :<math> \int\!\!\int |f(z)g(z-x)|\,dx\,dz=\int |f(z)| \int |g(z-x)|\,dx\,dz = \int |f(z)|\,\|g\|_1\,dz=\|f\|_1 \|g\|_1.</math> Hence by [[Fubini's theorem]] we have that <math>h\in L^1(\mathbb{R}^n)</math> so its Fourier transform <math>H</math> is defined by the integral formula :<math> \begin{align} H(\nu) = \mathcal{F}\{h\} &= \int_{\mathbb{R}^n} h(z) e^{-2 \pi i z\cdot\nu}\, dz \\ &= \int_{\mathbb{R}^n} \int_{\mathbb{R}^n} f(x) g(z-x)\, dx\, e^{-2 \pi i z\cdot \nu}\, dz. \end{align} </math> Observe that <math> |f(x)g(z-x)e^{-2\pi i z\cdot\nu}|=|f(x)g(z-x)|</math> and hence by the argument above we may apply Fubini's theorem again (i.e. interchange the order of integration): :<math>H(\nu) = \int_{\mathbb{R}^n} f(x)\left(\int_{\mathbb{R}^n} g(z-x)e^{-2 \pi i z\cdot \nu}\,dz\right)\,dx.</math> Substitute <math>y=z-x</math>; then <math>dy = dz</math>, so: :<math>H(\nu) = \int_{\mathbb{R}^n} f(x) \left( \int_{\mathbb{R}} g(y) e^{-2 \pi i (y+x)\cdot\nu}\,dy \right) \,dx</math> :::<math>=\int_{\mathbb{R}^n} f(x)e^{-2\pi i x\cdot \nu} \left( \int_{\mathbb{R}^n} g(y) e^{-2 \pi i y\cdot\nu}\,dy \right) \,dx</math> :::<math>=\int_{\mathbb{R}^n} f(x)e^{-2\pi i x\cdot \nu}\,dx \int_{\mathbb{R}^n} g(y) e^{-2 \pi i y\cdot\nu}\,dy.</math> These two integrals are the definitions of <math>F(\nu)</math> and <math>G(\nu)</math>, so: :<math>H(\nu) = F(\nu) \cdot G(\nu),</math> [[Q.E.D.|QED]]. == Functions of a discrete variable... sequences == By similar arguments, it can be shown that the [[Convolution#Discrete_convolution|discrete convolution]] of sequences &nbsp;<math>x\,</math> and <math>y\,</math> is given by: :<math>x * y\ =\ \scriptstyle{DTFT}^{-1} \displaystyle \big[\ \scriptstyle{DTFT}\displaystyle \{x\}\cdot \ \scriptstyle{DTFT}\displaystyle \{y\}\ \big],</math><br><br> where '''DTFT''' represents the [[discrete-time Fourier transform]]. An important special case is the '''[[circular convolution]]''' of &nbsp;<math>x\,</math> and <math>y\,</math> defined by &nbsp;<math>x_N * y,\,</math>&nbsp; where <math>x_N\,</math>&nbsp; is a [[periodic summation]]''':''' :<math>x_N[n]\ \stackrel{\text{def}}{=}\ \sum_{m=-\infty}^{\infty} x[n-mN].</math> It can then be shown that''':''' :<math> \begin{align} x_N * y\ &=\ \scriptstyle{DTFT}^{-1} \displaystyle \big[\ \scriptstyle{DTFT}\displaystyle \{x_N\}\cdot \ \scriptstyle{DTFT}\displaystyle \{y\}\ \big]\\ &=\ \scriptstyle{DFT}^{-1} \displaystyle \big[\ \scriptstyle{DFT}\displaystyle \{x_N\}\cdot \ \scriptstyle{DFT}\displaystyle \{y_N\}\ \big], \end{align} </math><br> where '''DFT''' represents the [[discrete Fourier transform]]. The proof follows from [[DTFT#Periodic_data]], which indicates that <math>\scriptstyle{DTFT}\displaystyle \{x_N\}</math> can be written as''':''' :<math>\scriptstyle{DTFT}\displaystyle \{x_N\}(f) = \frac{1}{N} \sum_{k=-\infty}^{\infty} \left(\scriptstyle{DFT}\displaystyle\{x_N\}[k]\right)\cdot \delta\left(f-k/N\right)</math> The product with <math>\scriptstyle{DTFT}\displaystyle \{y\}(f)</math> is thereby reduced to a discrete-frequency function''':''' :<math>\ \scriptstyle{DTFT}\displaystyle \{x_N\}\cdot \ \scriptstyle{DTFT}\displaystyle \{y\} = \frac{1}{N} \sum_{k=-\infty}^{\infty} \scriptstyle{DFT}\displaystyle\{x_N\}[k]\cdot \underbrace{\scriptstyle{DTFT}\displaystyle \{y\}(k/N)}_{\scriptstyle{DFT}\displaystyle\{y_N\}[k]}\cdot \delta\left(f-k/N\right)</math> &nbsp; &nbsp; (also using [[DTFT#Sampling_the_DTFT|Sampling the DTFT]]). The inverse DTFT is''':''' :<math> \begin{align} (x_N * y)[n]\ &=\ \int_{0}^{1} \frac{1}{N} \sum_{k=-\infty}^{\infty} \scriptstyle{DFT}\displaystyle\{x_N\}[k]\cdot \scriptstyle{DFT}\displaystyle\{y_N\}[k]\cdot \delta\left(f-k/N\right)\cdot e^{i 2 \pi f n} df\\ &=\ \frac{1}{N} \sum_{k=-\infty}^{\infty} \scriptstyle{DFT}\displaystyle\{x_N\}[k]\cdot \scriptstyle{DFT}\displaystyle\{y_N\}[k]\cdot \int_{0}^{1} \delta\left(f-k/N\right)\cdot e^{i 2 \pi f n} df\\ &=\ \frac{1}{N} \sum_{k=0}^{N-1} \scriptstyle{DFT}\displaystyle\{x_N\}[k]\cdot \scriptstyle{DFT}\displaystyle\{y_N\}[k]\cdot e^{i 2 \pi \frac{n}{N} k}\\ &=\ \scriptstyle{DFT}^{-1} \displaystyle \big[\ \scriptstyle{DFT}\displaystyle \{x_N\}\cdot \ \scriptstyle{DFT}\displaystyle \{y_N\}\ \big], \end{align} </math> [[Q.E.D.|QED]]. ==References== {{Reflist}} * {{citation|first=Yitzhak|last=Katznelson|title=An introduction to Harmonic Analysis|year=1976|publisher=Dover|isbn=0-486-63331-4}} * {{MathWorld|ConvolutionTheorem|Convolution Theorem}} * {{citation |last=Crutchfield |first=Steve |url=http://www.jhu.edu/signals/convolve/index.html |title=The Joy of Convolution |work=Johns Hopkins University |date=October 9, 2010 |accessdate=November 19, 2010}} ==Additional resources== For visual representation of the use of the convolution theorem in [[signal processing]], see: *[[Johns Hopkins University]]'s [[Java (software platform)|Java]]-aided simulation: http://www.jhu.edu/signals/convolve/index.html *[http://www.gnu.org/software/c-graph GNU C-Graph]: Free Software interactive [http://www.gnu.org/software/c-graph convolution demo]. {{DEFAULTSORT:Convolution Theorem}} [[Category:Theorems in Fourier analysis]] [[Category:Articles containing proofs]] [[ca:Teorema de convolució]] [[de:Faltung_(Mathematik)#Faltungstheorem_2]] [[es:Teorema de convolución]] [[fr:Produit de convolution]] [[it:Teorema di convoluzione]] [[pt:Teorema da convolução]] [[zh:卷积定理]]'