Convolution theorem

Last updated

In mathematics, the convolution theorem states that under suitable conditions the Fourier transform of a convolution of two signals is the pointwise product of their 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 Fourier-related transforms. Let $f$ and $g$ be two functions with convolution $f*g$ . (Note that the asterisk denotes convolution in this context, not standard multiplication. The tensor product symbol $\otimes$ is sometimes used instead.) Mathematics includes the study of such topics as quantity, structure (algebra), space (geometry), and change. It has no generally accepted definition. The Fourier transform (FT) decomposes a function of time into its constituent frequencies. This is similar to the way a musical chord can be expressed in terms of the volumes and frequencies of its constituent notes. The term Fourier transform refers to both the frequency domain representation and the mathematical operation that associates the frequency domain representation to a function of time. The Fourier transform of a function of time is itself a complex-valued function of frequency, whose magnitude (modulus) represents the amount of that frequency present in the original function, and whose argument is the phase offset of the basic sinusoid in that frequency. The Fourier transform is not limited to functions of time, but the domain of the original function is commonly referred to as the time domain. There is also an inverse Fourier transform that mathematically synthesizes the original function from its frequency domain representation. In mathematics convolution is a mathematical operation on two functions to produce a third function that expresses how the shape of one is modified by the other. The term convolution refers to both the result function and to the process of computing it. It is defined as the integral of the product of the two functions after one is reversed and shifted.

Contents

If ${\mathcal {F}}$ denotes the Fourier transform operator, then ${\mathcal {F}}\{f\}$ and ${\mathcal {F}}\{g\}$ are the Fourier transforms of $f$ and $g$ , respectively. Then

In mathematics, an operator is generally a mapping that acts on elements of a space to produce elements of another space. The most common operators are linear maps, which act on vector spaces. However, when using "linear operator" instead of "linear map", mathematicians often mean actions on vector spaces of functions, which also preserve other properties, such as continuity. For example, differentiation and indefinite integration are linear operators; operators that are built from them are called differential operators, integral operators or integro-differential operators.

${\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 \}}$ and:

$f\cdot g={\mathcal {F}}^{-1}{\big \{}{\mathcal {F}}\{f\}*{\mathcal {F}}\{g\}{\big \}}$ The relationships above are only valid for the form of the Fourier transform shown in the Proof section below. The transform may be normalized 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). It can be extended to the Fourier transform of abstract harmonic analysis defined over locally compact abelian groups.

In mathematics, the Laplace transform is an integral transform named after its inventor Pierre-Simon Laplace. It transforms a function of a real variable t to a function of a complex variable s. The transform has many applications in science and engineering.

In mathematics, the two-sided Laplace transform or bilateral Laplace transform is an integral transform equivalent to probability's moment generating function. Two-sided Laplace transforms are closely related to the Fourier transform, the Mellin transform, and the ordinary or one-sided Laplace transform. If ƒ(t) is a real or complex valued function of the real variable t defined for all real numbers, then the two-sided Laplace transform is defined by the integral

In mathematics, the Mellin transform is an integral transform that may be regarded as the multiplicative version of the two-sided Laplace transform. This integral transform is closely connected to the theory of Dirichlet series, and is often used in number theory, mathematical statistics, and the theory of asymptotic expansions; it is closely related to the Laplace transform and the Fourier transform, and the theory of the gamma function and allied special functions.

This formulation is especially useful for implementing a numerical convolution on a computer: The standard convolution algorithm has quadratic computational complexity. With the help of the convolution theorem and the fast Fourier transform, the complexity of the convolution can be reduced from $O\left(n^{2}\right)$ to $O\left(n\log n\right)$ , using big O notation. This can be exploited to construct fast multiplication algorithms, as in Multiplication algorithm § Fourier transform methods.

A computer is a machine that can be instructed to carry out sequences of arithmetic or logical operations automatically via computer programming. Modern computers have the ability to follow generalized sets of operations, called programs. These programs enable computers to perform an extremely wide range of tasks. A "complete" computer including the hardware, the operating system, and peripheral equipment required and used for "full" operation can be referred to as a computer system. This term may as well be used for a group of computers that are connected and work together, in particular a computer network or computer cluster. In algebra, a quadratic function, a quadratic polynomial, a polynomial of degree 2, or simply a quadratic, is a polynomial function with one or more variables in which the highest-degree term is of the second degree. For example, a quadratic function in three variables x, y, and z contains exclusively terms x2, y2, z2, xy, xz, yz, x, y, z, and a constant: In computer science, the analysis of algorithms is the determination of the computational complexity of algorithms, that is the amount of time, storage and/or other resources necessary to execute them. Usually, this involves determining a function that relates the length of an algorithm's input to the number of steps it takes or the number of storage locations it uses. An algorithm is said to be efficient when this function's values are small, or grow slowly compared to a growth in the size of the input. Different inputs of the same length may cause the algorithm to have different behavior, so best, worst and average case descriptions might all be of practical interest. When not otherwise specified, the function describing the performance of an algorithm is usually an upper bound, determined from the worst case inputs to the algorithm.

Proof

The proof here is shown for a particular normalization of the Fourier transform. As mentioned above, if the transform is normalized differently, then constant scaling factors will appear in the derivation.

In statistics and applications of statistics, normalization can have a range of meanings. In the simplest cases, normalization of ratings means adjusting values measured on different scales to a notionally common scale, often prior to averaging. In more complicated cases, normalization may refer to more sophisticated adjustments where the intention is to bring the entire probability distributions of adjusted values into alignment. In the case of normalization of scores in educational assessment, there may be an intention to align distributions to a normal distribution. A different approach to normalization of probability distributions is quantile normalization, where the quantiles of the different measures are brought into alignment.

A scale factor is a number which scales, or multiplies, some quantity. In the equation y = Cx, C is the scale factor for x. C is also the coefficient of x, and may be called the constant of proportionality of y to x. For example, doubling distances corresponds to a scale factor of two for distance, while cutting a cake in half results in pieces with a scale factor for volume of one half. The basic equation for it is image over preimage.

Let $f,g$ belong to the Lp-space $L^{1}(\mathbb {R} ^{n})$ . Let $F$ be the Fourier transform of $f$ and $G$ be the Fourier transform of $g$ :

{\begin{aligned}F(\nu )&={\mathcal {F}}\{f\}(\nu )=\int _{\mathbb {R} ^{n}}f(x)e^{-2\pi ix\cdot \nu }\,dx,\\G(\nu )&={\mathcal {F}}\{g\}(\nu )=\int _{\mathbb {R} ^{n}}g(x)e^{-2\pi ix\cdot \nu }\,dx,\end{aligned}} where the dot between $x$ and $\nu$ indicates the inner product of $\mathbb {R} ^{n}$ . Let $h$ be the convolution of $f$ and $g$ $h(z)=\int _{\mathbb {R} ^{n}}f(x)g(z-x)\,dx.$ Also

$\iint |f(x)g(z-x)|\,dz\,dx=\int \left(|f(x)|\int |g(z-x)|\,dz\right)\,dx=\int |f(x)|\,\|g\|_{1}\,dx=\|f\|_{1}\|g\|_{1}.$ Hence by Fubini's theorem we have that $h\in L^{1}(\mathbb {R} ^{n})$ so its Fourier transform $H$ is defined by the integral formula

{\begin{aligned}H(\nu )={\mathcal {F}}\{h\}&=\int _{\mathbb {R} ^{n}}h(z)e^{-2\pi iz\cdot \nu }\,dz\\&=\int _{\mathbb {R} ^{n}}\int _{\mathbb {R} ^{n}}f(x)g(z-x)\,dx\,e^{-2\pi iz\cdot \nu }\,dz.\end{aligned}} Note that $|f(x)g(z-x)e^{-2\pi iz\cdot \nu }|=|f(x)g(z-x)|$ and hence by the argument above we may apply Fubini's theorem again (i.e. interchange the order of integration):

$H(\nu )=\int _{\mathbb {R} ^{n}}f(x)\left(\int _{\mathbb {R} ^{n}}g(z-x)e^{-2\pi iz\cdot \nu }\,dz\right)\,dx.$ Substituting $y=z-x$ yields $dy=dz$ . Therefore

$H(\nu )=\int _{\mathbb {R} ^{n}}f(x)\left(\int _{\mathbb {R} ^{n}}g(y)e^{-2\pi i(y+x)\cdot \nu }\,dy\right)\,dx$ $=\int _{\mathbb {R} ^{n}}f(x)e^{-2\pi ix\cdot \nu }\left(\int _{\mathbb {R} ^{n}}g(y)e^{-2\pi iy\cdot \nu }\,dy\right)\,dx$ $=\int _{\mathbb {R} ^{n}}f(x)e^{-2\pi ix\cdot \nu }\,dx\int _{\mathbb {R} ^{n}}g(y)e^{-2\pi iy\cdot \nu }\,dy.$ These two integrals are the definitions of $F(\nu )$ and $G(\nu )$ , so:

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

Convolution theorem for inverse Fourier transform

A similar argument, as the above proof, can be applied to the convolution theorem for the inverse Fourier transform;

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

$f\cdot g={\mathcal {F}}^{-1}{\big \{}{\mathcal {F}}\{f\}*{\mathcal {F}}\{g\}{\big \}}$ Functions of discrete variable sequences

By similar arguments, it can be shown that the discrete convolution of sequences $x$ and $y$ is given by:

$x*y={\rm {DTFT}}^{-1}\displaystyle {\big [}{\rm {DTFT}}\displaystyle \{x\}\cdot \ {\rm {DTFT}}\displaystyle \{y\}{\big ]},$ where DTFT represents the discrete-time Fourier transform.

An important special case is the circular convolution of $x$ and $y$ defined by $x_{N}*y,$ where $x_{N}$ is a periodic summation:

$x_{N}[n]\ {\stackrel {\text{def}}{=}}\sum _{m=-\infty }^{\infty }x[n-mN].$ It can then be shown that:

{\begin{aligned}x_{N}*y&={\rm {DTFT}}^{-1}\displaystyle {\big [}{\rm {DTFT}}\displaystyle \{x_{N}\}\cdot {\rm {DTFT}}\displaystyle \{y\}{\big ]}\\&={\rm {DFT}}^{-1}\displaystyle {\big [}{\rm {DFT}}\displaystyle \{x_{N}\}\cdot {\rm {DFT}}\displaystyle \{y_{N}\}{\big ]},\end{aligned}} where DFT represents the discrete Fourier transform.

The proof follows from DTFT#Periodic data, which indicates that ${DTFT}\displaystyle \{x_{N}\}$ can be written as:

${\rm {DTFT}}\displaystyle \{x_{N}\}(f)={\frac {1}{N}}\sum _{k=-\infty }^{\infty }\left({\rm {DFT}}\displaystyle \{x_{N}\}[k]\right)\cdot \delta \left(f-k/N\right)$ The product with ${\rm {DTFT}}\displaystyle \{y\}(f)$ is thereby reduced to a discrete-frequency function:

${\rm {DTFT}}\displaystyle \{x_{N}\}\cdot {\rm {DTFT}}\displaystyle \{y\}={\frac {1}{N}}\sum _{k=-\infty }^{\infty }{\rm {DFT}}\displaystyle \{x_{N}\}[k]\cdot \underbrace {{\rm {DTFT}}\displaystyle \{y\}(k/N)} _{{\rm {DFT}}\displaystyle \{y_{N}\}[k]}\cdot \delta \left(f-k/N\right)$ (also using Sampling the DTFT).

The inverse DTFT is:

{\begin{aligned}(x_{N}*y)[n]&=\int _{0}^{1}{\frac {1}{N}}\sum _{k=-\infty }^{\infty }{\rm {DFT}}\displaystyle \{x_{N}\}[k]\cdot {\rm {DFT}}\displaystyle \{y_{N}\}[k]\cdot \delta \left(f-k/N\right)\cdot e^{i2\pi fn}df\\&={\frac {1}{N}}\sum _{k=-\infty }^{\infty }{\rm {DFT}}\displaystyle \{x_{N}\}[k]\cdot {\rm {DFT}}\displaystyle \{y_{N}\}[k]\cdot \int _{0}^{1}\delta \left(f-k/N\right)\cdot e^{i2\pi fn}df\\&={\frac {1}{N}}\sum _{k=0}^{N-1}{\rm {DFT}}\displaystyle \{x_{N}\}[k]\cdot {\rm {DFT}}\displaystyle \{y_{N}\}[k]\cdot e^{i2\pi {\frac {n}{N}}k}\\&={\rm {DFT}}^{-1}\displaystyle {\big [}{\rm {DFT}}\displaystyle \{x_{N}\}\cdot {\rm {DFT}}\displaystyle \{y_{N}\}{\big ]},\end{aligned}} QED.

Convolution theorem for Fourier series coefficients

Two convolution theorems exist for the Fourier series coefficients of a periodic function:

• The first convolution theorem states that if $f$ and $g$ are in $L^{1}([-\pi ,\pi ])$ , the Fourier series coefficients of the 2π-periodic convolution of $f$ and $g$ are given by:
$[{\widehat {f*_{2\pi }g}}](n)=2\pi \cdot {\widehat {f}}(n)\cdot {\widehat {g}}(n),$ [nb 1]
where:
{\begin{aligned}\left[f*_{2\pi }g\right](x)\ &{\stackrel {\mathrm {def} }{=}}\int _{-\pi }^{\pi }f(u)\cdot g[{\text{pv}}(x-u)]\,du,&&{\big (}{\text{and }}\underbrace {{\text{pv}}(x)\ {\stackrel {\mathrm {def} }{=}}\arg \left(e^{ix}\right)} _{\text{principal value}}{\big )}\\&=\int _{-\pi }^{\pi }f(u)\cdot g(x-u)\,du,&&{\text{when }}g(x){\text{ is 2}}\pi {\text{-periodic.}}\\&=\int _{2\pi }f(u)\cdot g(x-u)\,du,&&{\text{when both functions are 2}}\pi {\text{-periodic, and the integral is over any 2}}\pi {\text{ interval.}}\end{aligned}} • The second convolution theorem states that the Fourier series coefficients of the product of $f$ and $g$ are given by the discrete convolution of the ${\hat {f}}$ and ${\hat {g}}$ sequences:
$\left[{\widehat {f\cdot g}}\right](n)=\left[{\widehat {f}}*{\widehat {g}}\right](n).$ 