Convolution theorem - Citizendia

In mathematics, the convolution theorem states that under suitable conditions the Fourier transform of a convolution is the pointwise product of Fourier transforms. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and This article specifically discusses Fourier transformation of functions on the Real line; for other kinds of Fourier transformation see Fourier analysis and In Mathematics and in particular Functional analysis, convolution is a mathematical operation on two functions f and The pointwise product of two functions is another function obtained by multiplying the image of the two functions at each value in the domain In other words, convolution in one domain (e. g. , time domain) equals point-wise multiplication in the other domain (e. Time domain is a term used to describe the analysis of mathematical functions or physical signals with respect to Time. g. , frequency domain). Frequency domain is a term used to describe the analysis of Mathematical functions or signals with respect to frequency Versions of the convolution theorem are true for various Fourier-related transforms. This is a list of Linear transformations of functions related to Fourier analysis. Let $\ f$ and $\ g$ be two functions with convolution $\ f*g$ . The Mathematical concept of a function expresses dependence between two quantities one of which is given (the independent variable, argument of the function In Mathematics and in particular Functional analysis, convolution is a mathematical operation on two functions f and (Note that the asterisk denotes convolution in this context, and not multiplication. An asterisk ( *) (Latin asteriscum "little star" from Greek ἀστερίσκος) is a Typographical symbol or Glyph The symbol $\otimes$ is sometimes used instead. ) Let $\ \mathcal{F}$ denote the Fourier transform operator, so $\ \mathcal{F}\{f\}$ and $\ \mathcal{F}\{g\}$ are the Fourier transforms of $\ f$ and $\ g$ , respectively. In Mathematics, an operator is a function which operates on (or modifies another function Then

$\mathcal{F}\{f*g\} = \mathcal{F}\{f\} \cdot \mathcal{F}\{g\}$

where $\cdot$ denotes point-wise multiplication. It also works the other way around:

$\mathcal{F}\{f \cdot g\}= \mathcal{F}\{f\}*\mathcal{F}\{g\}$

By applying the inverse Fourier transform $\mathcal{F}^{-1}$ , we can write:

$f*g= \mathcal{F}^{-1}\big\{\mathcal{F}\{f\}\cdot\mathcal{F}\{g\}\big\}$

Note that the relationships above are only valid for the form of the Fourier transform shown in the Proof section below. The transform may be normalised in other ways, in which case constant scaling factors (typically $\ 2\pi$ or $\ \sqrt{2\pi}$ ) 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). In Mathematics, the Laplace transform is one of the best known and most widely used Integral transforms It is commonly used to produce an easily soluble algebraic In Mathematics, the two-sided Laplace transform or bilateral Laplace transform is an Integral transform closely related to the Fourier transform In Mathematics, the Mellin transform is an Integral transform that may be regarded as the multiplicative version of the Two-sided Laplace transform In Mathematics, the Hartley transform is an Integral transform closely related to the Fourier transform, but which transforms real-valued functions to real-valued In Mathematics, the Mellin inversion formula (named after Hjalmar Mellin) tells us conditions underwhich the inverse Mellin transform, or equivalently the It can be extended to the Fourier transform of abstract harmonic analysis defined over locally compact abelian groups. Harmonic analysis is the branch of Mathematics that studies the representation of functions or signals as the superposition of basic Waves It investigates and generalizes In Mathematics, in particular in Harmonic analysis and the theory of Topological groups Pontryagin duality explains the general properties of the Fourier

This formulation is especially useful for implementing a numerical convolution on a computer: The standard convolution algorithm has quadratic computational complexity. A computer is a Machine that manipulates data according to a list of instructions. A quadratic function, in Mathematics, is a Polynomial function of the form f(x=ax^2+bx+c \\! where a \ne 0 \\! Computational complexity theory, as a branch of the Theory of computation in Computer science, investigates the problems related to the amounts of resources 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 algorithms. A multiplication algorithm is an Algorithm (or method to multiply two numbers

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$ be the Fourier transform of $f$ and $G$ be the Fourier transform of $g$ :

$F(\nu) = \mathcal{F}\{f\} = \int_{\mathbb{R}} f(x) e^{-2 \pi i x\cdot\nu} \,dx$

$G(\nu) = \mathcal{F}\{g\} = \int_{\mathbb{R}}g(x) e^{-2 \pi i x\cdot\nu} \,dx$ .

Let $h$ be the convolution of $f$ and $g$

$h(z) = \int\limits_{\mathbb{R}} f(x) g(z-x)\, \mathrm{d} x.$

Now notice that

$\int\!\!\int |f(z)g(x-z)|\,dx\,dz=\int |f(z)| \int |g(z-x)|\,dx\,dz = \int |f(z)|\,\|g\|_1\,dz=\|f\|_1 \|g\|_1.$

Hence by Fubini's theorem we have that $h\in L^1(\mathbb{R}^n)$ so its Fourier transform is defined. In Mathematical analysis, Fubini's theorem, named after Guido Fubini, states that if \int_{A\times B} |f(xy|\d(xy Let $H$ be the Fourier transform of $h$ :

$\begin{align} H(\nu) = \mathcal{F}\{h\} &= \int_{\mathbb{R}} h(z) e^{-2 \pi i z\cdot\nu}\, dz \\ &= \int_{\mathbb{R}} \int_{\mathbb{R}^n} f(x) g(z-x)\, dx\, e^{-2 \pi i z\cdot \nu}\, dz. \end{align}$

Observe that $|f(x)g(z-x)e^{-2\pi i z\cdot\nu}|=|f(x)g(z-x)|$ and hence by the argument above we may apply Fubini's theorem again:

$H(\nu) = \int_{\mathbb{R}} f(x)\left(\int_{\mathbb{R}^n} g(z-x)e^{-2 \pi i z\cdot \nu}\,dz\right)\,dx.$

Substitute $y = z - x$ ; then $d y = d z$ , so:

$H(\nu) = \int_{\mathbb{R}} f(x) \left( \int_{\mathbb{R}} g(y) e^{-2 \pi i (y+x)\cdot\nu}\,dy \right) \,dx$

$=\int_{\mathbb{R}} f(x)e^{-2\pi i x\cdot \nu} \left( \int_{\mathbb{R}} g(y) e^{-2 \pi i y\cdot\nu}\,dy \right) \,dx$

$=\int_{\mathbb{R}} f(x)e^{-2\pi i x\cdot \nu}\,dx \int_{\mathbb{R}} g(y) e^{-2 \pi i y\cdot\nu}\,dy.$

These two integrals are the definitions of $F (ν)$ and $G (ν)$ , so:

$H(\nu) = F(\nu) \cdot G(\nu),$

which was to be demonstrated.

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |