Convolution theorem
View on Wikipediafrom Wikipedia
In mathematics, the convolution theorem states that under suitable conditions the Fourier transform of a convolution of two functions (or signals) is the product of their Fourier transforms. More generally, convolution in one domain (e.g., time domain) equals point-wise multiplication in the other domain (e.g., frequency domain). Other versions of the convolution theorem are applicable to various Fourier-related transforms.
Functions of a continuous variable
[edit]Consider two functions and with Fourier transforms and :
where denotes the Fourier transform operator. The transform may be normalized in other ways, in which case constant scaling factors (typically or ) will appear in the convolution theorem below. The convolution of and is defined by:
In this context the asterisk denotes convolution, instead of standard multiplication. The tensor product symbol is sometimes used instead.
The convolution theorem states that:[1][2]: eq.8
|
| Eq.1a |
Applying the inverse Fourier transform produces the corollary:[2]: eqs.7, 10
Convolution theorem
|
| Eq.1b |
The theorem also generally applies to multi-dimensional functions.
Multi-dimensional derivation of Eq.1
|
|---|
|
Consider functions in Lp-space with Fourier transforms : where indicates the inner product of : and The convolution of and is defined by: Also: Hence by Fubini's theorem we have that so its Fourier transform is defined by the integral formula: Note that Hence by the argument above we may apply Fubini's theorem again (i.e. interchange the order of integration): |
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.
Periodic convolution (Fourier series coefficients)
[edit]Consider -periodic functions and which can be expressed as periodic summations:
- and
In practice the non-zero portion of components and are often limited to duration but nothing in the theorem requires that.
The Fourier series coefficients are:
![{\displaystyle {\begin{aligned}U[k]&\triangleq {\mathcal {F}}\{u_{_{P}}\}[k]={\frac {1}{P}}\int _{P}u_{_{P}}(x)e^{-i2\pi kx/P}\,dx,\quad k\in \mathbb {Z} ;\quad \quad \scriptstyle {\text{integration over any interval of length }}P\\V[k]&\triangleq {\mathcal {F}}\{v_{_{P}}\}[k]={\frac {1}{P}}\int _{P}v_{_{P}}(x)e^{-i2\pi kx/P}\,dx,\quad k\in \mathbb {Z} \end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/51b732f1fe5d5074f423f1b96c4eea07631284ed)
where denotes the Fourier series integral.
- The product: is also -periodic, and its Fourier series coefficients are given by the discrete convolution of the and sequences:
![{\displaystyle {\mathcal {F}}\{u_{_{P}}\cdot v_{_{P}}\}[k]=\{U*V\}[k].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab30eb678559f102051cedba4be0fc07f346a4c0)
- The convolution:
is also -periodic, and is called a periodic convolution.
Derivation of periodic convolution
|
|---|
|
|
![{\displaystyle {\begin{aligned}\int _{-\infty }^{\infty }u_{_{P}}(x-\tau )\cdot v(\tau )\,d\tau &=\sum _{k=-\infty }^{\infty }\left[\int _{x_{o}+kP}^{x_{o}+(k+1)P}u_{_{P}}(x-\tau )\cdot v(\tau )\ d\tau \right]\quad x_{0}{\text{ is an arbitrary parameter}}\\&=\sum _{k=-\infty }^{\infty }\left[\int _{x_{o}}^{x_{o}+P}\underbrace {u_{_{P}}(x-\tau -kP)} _{u_{_{P}}(x-\tau ),{\text{ by periodicity}}}\cdot v(\tau +kP)\ d\tau \right]\quad {\text{substituting }}\tau \rightarrow \tau +kP\\&=\int _{x_{o}}^{x_{o}+P}u_{_{P}}(x-\tau )\cdot \underbrace {\left[\sum _{k=-\infty }^{\infty }v(\tau +kP)\right]} _{\triangleq \ v_{_{P}}(\tau )}\ d\tau \end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f1575bd74f86366816ffc18d0fabd05dd5cd1269)
The corresponding convolution theorem is:
|
| Eq.2 |
![{\displaystyle {\mathcal {F}}\{u_{_{P}}*v\}[k]=\ P\cdot U[k]\ V[k].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d4ee3375f365aa800cc34e56a6bf89e0a90ed3b)
Derivation of Eq.2
|
|---|
|
|
![{\displaystyle {\begin{aligned}{\mathcal {F}}\{u_{_{P}}*v\}[k]&\triangleq {\frac {1}{P}}\int _{P}\left(\int _{P}u_{_{P}}(\tau )\cdot v_{_{P}}(x-\tau )\ d\tau \right)e^{-i2\pi kx/P}\,dx\\&=\int _{P}u_{_{P}}(\tau )\left({\frac {1}{P}}\int _{P}v_{_{P}}(x-\tau )\ e^{-i2\pi kx/P}dx\right)\,d\tau \\&=\int _{P}u_{_{P}}(\tau )\ e^{-i2\pi k\tau /P}\underbrace {\left({\frac {1}{P}}\int _{P}v_{_{P}}(x-\tau )\ e^{-i2\pi k(x-\tau )/P}dx\right)} _{V[k],\quad {\text{due to periodicity}}}\,d\tau \\&=\underbrace {\left(\int _{P}\ u_{_{P}}(\tau )\ e^{-i2\pi k\tau /P}d\tau \right)} _{P\cdot U[k]}\ V[k].\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/252a143162a38ecc1ee2c1780ed231edf64ed597)
Functions of a discrete variable (sequences)
[edit]By a derivation similar to Eq.1, there is an analogous theorem for sequences, such as samples of two continuous functions, where now denotes the discrete-time Fourier transform (DTFT) operator. Consider two sequences and with transforms and :
![{\displaystyle u[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6f1362207606428a09d907db25527859eab6ac3)
![{\displaystyle v[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7cbc20699310c20ae48d376fc4f6365c67966405)
![{\displaystyle {\begin{aligned}U(f)&\triangleq {\mathcal {F}}\{u\}(f)=\sum _{n=-\infty }^{\infty }u[n]\cdot e^{-i2\pi fn}\;,\quad f\in \mathbb {R} ,\\V(f)&\triangleq {\mathcal {F}}\{v\}(f)=\sum _{n=-\infty }^{\infty }v[n]\cdot e^{-i2\pi fn}\;,\quad f\in \mathbb {R} .\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/244dd8c93040378c9c8849ab6483c6582445d1b7)
The § Discrete convolution of and is defined by:
![{\displaystyle r[n]\triangleq (u*v)[n]=\sum _{m=-\infty }^{\infty }u[m]\cdot v[n-m]=\sum _{m=-\infty }^{\infty }u[n-m]\cdot v[m].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/22aac1f7102502f6b39153be6aacd9bce5fc7cdd)
The convolution theorem for discrete sequences is:[3][4]: p.60 (2.169)
|
| Eq.3 |
Periodic convolution
[edit]and as defined above, are periodic, with a period of 1. Consider -periodic sequences and :
- and
![{\displaystyle u_{_{N}}[n]\ \triangleq \sum _{m=-\infty }^{\infty }u[n-mN]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed44f4cf6f7e56baa871eef261cd01f53855dd07)
![{\displaystyle v_{_{N}}[n]\ \triangleq \sum _{m=-\infty }^{\infty }v[n-mN],\quad n\in \mathbb {Z} .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/62b3cb372f16be04589aa1f446455da9d8bcd8f0)
These functions occur as the result of sampling and at intervals of and performing an inverse discrete Fourier transform (DFT) on samples (see § Sampling the DTFT). The discrete convolution:
![{\displaystyle \{u_{_{N}}*v\}[n]\ \triangleq \sum _{m=-\infty }^{\infty }u_{_{N}}[m]\cdot v[n-m]\equiv \sum _{m=0}^{N-1}u_{_{N}}[m]\cdot v_{_{N}}[n-m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/907f89efecfca8b8c1519230c0efe93f721d0ad3)
is also -periodic, and is called a periodic convolution. Redefining the operator as the -length DFT, the corresponding theorem is:[5][4]: p. 548
|
| Eq.4a |
![{\displaystyle {\mathcal {F}}\{u_{_{N}}*v\}[k]=\ \underbrace {{\mathcal {F}}\{u_{_{N}}\}[k]} _{U(k/N)}\cdot \underbrace {{\mathcal {F}}\{v_{_{N}}\}[k]} _{V(k/N)},\quad k\in \mathbb {Z} .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cbf1eab2ab63c1b6db4fc8f33c8a4a30b1391f50)
And therefore:
|
| Eq.4b |
![{\displaystyle \{u_{_{N}}*v\}[n]=\ {\mathcal {F}}^{-1}\{{\mathcal {F}}\{u_{_{N}}\}\cdot {\mathcal {F}}\{v_{_{N}}\}\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd918e288950dc7554d3cb3e478d441022b16afc)
Under the right conditions, it is possible for this -length sequence to contain a distortion-free segment of a convolution. But when the non-zero portion of the or sequence is equal or longer than some distortion is inevitable. Such is the case when the sequence is obtained by directly sampling the DTFT of the infinitely long § Discrete Hilbert transform impulse response.[A]
For and sequences whose non-zero duration is less than or equal to a final simplification is:
Circular convolution
|
| Eq.4c |
![{\displaystyle \{u_{_{N}}*v\}[n]=\ {\mathcal {F}}^{-1}\{{\mathcal {F}}\{u\}\cdot {\mathcal {F}}\{v\}\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ac7a801e261a01f897517049a2095ee7d745cf6)
This form is often used to efficiently implement numerical convolution by computer. (see § Fast convolution algorithms and § Example)
As a partial reciprocal, it has been shown [6] that any linear transform that turns convolution into a product is the DFT (up to a permutation of coefficients).
Derivations of Eq.4
|
|---|
|
A time-domain derivation proceeds as follows: A frequency-domain derivation follows from § Periodic data, which indicates that the DTFTs can be written as: The product with is thereby reduced to a discrete-frequency function: where the equivalence of and follows from § Sampling the DTFT. Therefore, the equivalence of (5a) and (5b) requires:
|
![{\displaystyle {\begin{aligned}\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}*v\}[k]&\triangleq \sum _{n=0}^{N-1}\left(\sum _{m=0}^{N-1}u_{_{N}}[m]\cdot v_{_{N}}[n-m]\right)e^{-i2\pi kn/N}\\&=\sum _{m=0}^{N-1}u_{_{N}}[m]\left(\sum _{n=0}^{N-1}v_{_{N}}[n-m]\cdot e^{-i2\pi kn/N}\right)\\&=\sum _{m=0}^{N-1}u_{_{N}}[m]\cdot e^{-i2\pi km/N}\underbrace {\left(\sum _{n=0}^{N-1}v_{_{N}}[n-m]\cdot e^{-i2\pi k(n-m)/N}\right)} _{\scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\quad \scriptstyle {\text{due to periodicity}}}\\&=\underbrace {\left(\sum _{m=0}^{N-1}u_{_{N}}[m]\cdot e^{-i2\pi km/N}\right)} _{\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]}\left(\scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\right).\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61dd82c63ec339357bb750973d87a819d0490c8e)
![{\displaystyle {\mathcal {F}}\{u_{_{N}}*v\}(f)={\frac {1}{N}}\sum _{k=-\infty }^{\infty }\left(\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}*v\}[k]\right)\cdot \delta \left(f-k/N\right).\quad \scriptstyle {\mathsf {(Eq.5a)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9dc6053c6711e16180fcaf82615d9ba6d205646c)
![{\displaystyle {\mathcal {F}}\{u_{_{N}}\}(f)={\frac {1}{N}}\sum _{k=-\infty }^{\infty }\left(\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\right)\cdot \delta \left(f-k/N\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/42c03475328868e8c4027366eb1a6740a38895e6)
![{\displaystyle {\begin{aligned}{\mathcal {F}}\{u_{_{N}}*v\}(f)&=G_{_{N}}(f)V(f)\\&={\frac {1}{N}}\sum _{k=-\infty }^{\infty }\left(\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\right)\cdot V(f)\cdot \delta \left(f-k/N\right)\\&={\frac {1}{N}}\sum _{k=-\infty }^{\infty }\left(\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\right)\cdot V(k/N)\cdot \delta \left(f-k/N\right)\\&={\frac {1}{N}}\sum _{k=-\infty }^{\infty }\left(\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\right)\cdot \left(\scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\right)\cdot \delta \left(f-k/N\right),\quad \scriptstyle {\mathsf {(Eq.5b)}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fbfa658cb06c8f39bd4f6c14c0cf49ebb7f614af)
![{\displaystyle \left(\scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/867247cbc04ad960f719050702f1b613652470f0)
![{\displaystyle \scriptstyle {\rm {DFT}}\displaystyle {\{u_{_{N}}*v\}[k]}=\left(\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\right)\cdot \left(\scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f7b413f938f761ac2c932b93215c4e166e02071)
![{\displaystyle {\begin{aligned}(u_{_{N}}*v)[n]&=\int _{0}^{1}\left({\frac {1}{N}}\sum _{k=-\infty }^{\infty }\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\cdot \scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\cdot \delta \left(f-k/N\right)\right)\cdot e^{i2\pi fn}df\\&={\frac {1}{N}}\sum _{k=-\infty }^{\infty }\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\cdot \scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\cdot \underbrace {\left(\int _{0}^{1}\delta \left(f-k/N\right)\cdot e^{i2\pi fn}df\right)} _{{\text{0, for}}\ k\ \notin \ [0,\ N)}\\&={\frac {1}{N}}\sum _{k=0}^{N-1}{\bigg (}\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\cdot \scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]{\bigg )}\cdot e^{i2\pi {\frac {n}{N}}k}\\&=\ \scriptstyle {\rm {DFT}}^{-1}\displaystyle {\bigg (}\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}\cdot \scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}{\bigg )}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1c651d3df13f237865ee17f554975dbd3136b08)
Convolution theorem for inverse Fourier transform
[edit]There is also a convolution theorem for the inverse Fourier transform:
Here, "" represents the Hadamard product, and "" represents a convolution between the two matrices.
so that
Convolution theorem for tempered distributions
[edit]The convolution theorem extends to tempered distributions. Here, is an arbitrary tempered distribution:
But must be "rapidly decreasing" towards and in order to guarantee the existence of both, convolution and multiplication product. Equivalently, if is a smooth "slowly growing" ordinary function, it guarantees the existence of both, multiplication and convolution product.[7][8][9]
In particular, every compactly supported tempered distribution, such as the Dirac delta, is "rapidly decreasing". Equivalently, bandlimited functions, such as the function that is constantly are smooth "slowly growing" ordinary functions. If, for example, is the Dirac comb both equations yield the Poisson summation formula and if, furthermore, is the Dirac delta then is constantly one and these equations yield the Dirac comb identity.
See also
[edit]Notes
[edit]- ^ An example is the MATLAB function, hilbert(u,N).
References
[edit]- ^ McGillem, Clare D.; Cooper, George R. (1984). Continuous and Discrete Signal and System Analysis (2 ed.). Holt, Rinehart and Winston. p. 118 (3–102). ISBN 0-03-061703-0.
- ^ a b Weisstein, Eric W. "Convolution Theorem". From MathWorld--A Wolfram Web Resource. Retrieved 8 February 2021.
- ^ Proakis, John G.; Manolakis, Dimitri G. (1996), Digital Signal Processing: Principles, Algorithms and Applications (3 ed.), New Jersey: Prentice-Hall International, p. 297, Bibcode:1996dspp.book.....P, ISBN 9780133942897, sAcfAQAAIAAJ
- ^ a b Oppenheim, Alan V.; Schafer, Ronald W.; Buck, John R. (1999). Discrete-time signal processing (2nd ed.). Upper Saddle River, N.J.: Prentice Hall. ISBN 0-13-754920-2.
- ^ Rabiner, Lawrence R.; Gold, Bernard (1975). Theory and application of digital signal processing. Englewood Cliffs, NJ: Prentice-Hall, Inc. p. 59 (2.163). ISBN 978-0139141010.
- ^ Amiot, Emmanuel (2016). Music through Fourier Space. Computational Music Science. Zürich: Springer. p. 8. doi:10.1007/978-3-319-45581-5. ISBN 978-3-319-45581-5. S2CID 6224021.
- ^ Horváth, John (1966). Topological Vector Spaces and Distributions. Reading, MA: Addison-Wesley Publishing Company.
- ^ Barros-Neto, José (1973). An Introduction to the Theory of Distributions. New York, NY: Dekker.
- ^ Petersen, Bent E. (1983). Introduction to the Fourier Transform and Pseudo-Differential Operators. Boston, MA: Pitman Publishing.
Further reading
[edit]- Katznelson, Yitzhak (1976), An introduction to Harmonic Analysis, Dover, ISBN 0-486-63331-4
- Li, Bing; Babu, G. Jogesh (2019), "Convolution Theorem and Asymptotic Efficiency", A Graduate Course on Statistical Inference, New York: Springer, pp. 295–327, ISBN 978-1-4939-9759-6
- Crutchfield, Steve (October 9, 2010), "The Joy of Convolution", Johns Hopkins University, retrieved November 19, 2010
Additional resources
[edit]For a visual representation of the use of the convolution theorem in signal processing, see:
- Johns Hopkins University's Java-aided simulation: http://www.jhu.edu/signals/convolve/index.html
Convolution theorem
View on Grokipediafrom Grokipedia
Core statements
Continuous aperiodic case
In the continuous aperiodic case, the convolution of two functions (the space of absolutely integrable functions on the real line) is defined as
This operation measures the overlap between and a reflected, shifted version of , and it extends to (square-integrable functions) via density arguments and Plancherel's theorem.[4][5]
The convolution theorem states that the Fourier transform of the convolution equals the pointwise product of the individual Fourier transforms:
where the Fourier transform is defined as
This holds for functions in by direct computation using Fubini's theorem for interchanging integrals, and for by continuity of the Fourier transform as a unitary operator on that space.[4][1]
The inverse form of the theorem asserts the duality: the inverse Fourier transform of the product of the transforms yields the convolution,
Here, the inverse transform is
ensuring the operation is reversible under suitable integrability conditions, such as when and are in . This duality simplifies computations in signal processing and partial differential equations by converting integration in the time domain to multiplication in the frequency domain.[4][1]
A illustrative example is the convolution of two Gaussian functions, and , each of whose Fourier transform is itself, and similarly for . By the theorem, , so the inverse transform yields , another Gaussian with variance scaled by the sum of the originals. More generally, for and with , the result is , demonstrating how the product of exponential transforms produces a convolved Gaussian.[2][4]
The convolution theorem for the Fourier transform was first linked to the transform by Émile Borel in 1899 through work on divergent series and was fully established by Percy Daniell in 1920 via generalizations of Stieltjes-Volterra products.[6]
Discrete aperiodic case
In the discrete aperiodic case, the convolution of two sequences and , defined over the integers , is given by
for all , where the sequences belong to the space (absolutely summable) or (square-summable).[7] This operation models the output of a linear time-invariant system in discrete-time signal processing when one sequence acts as the input and the other as the impulse response.[8]
The discrete-time Fourier transform (DTFT) provides the frequency-domain representation for such aperiodic sequences, defined as
where is the normalized angular frequency.[9] Similarly for , yielding .
The convolution theorem states that the DTFT of the convolved sequence is the pointwise product of the individual DTFTs:
[7][8] This property simplifies computations by transforming time-domain convolution into frequency-domain multiplication, which is particularly efficient for long sequences in digital signal processing applications.
The inverse relation follows from the inverse DTFT, which reconstructs the time-domain sequence via
where the inverse transform is
[9] This bidirectional equivalence holds under the specified sequence spaces, enabling seamless switching between domains.
For convergence, the DTFT of sequences in is guaranteed to exist and be continuous for all , as the absolute summability ensures the infinite sum converges uniformly.[10] For sequences, the DTFT exists in the mean-square sense but may exhibit discontinuities, though the convolution theorem still applies when both inputs are in these spaces.[10]
A representative example illustrates the theorem: consider the convolution of two identical rectangular sequences, each of length , defined as for and 0 otherwise. The time-domain convolution yields a triangular sequence of length , peaking at and linearly tapering to the sides. In the frequency domain, the DTFT of each rectangular sequence is the Dirichlet kernel , so the DTFT of the convolution is , demonstrating how multiplication produces the frequency response of the triangular output.[11][7]
Periodic variants
Continuous periodic functions
For P-periodic continuous functions and , the periodic convolution is defined by
This operation produces another P-periodic function, capturing the "overlap" of and over one period while ensuring consistency with Fourier analysis on the circle. The normalization factor aligns the integral with the measure of the fundamental domain , preventing scaling issues that would arise in the frequency domain.[12]
The Fourier series of a P-periodic function is expressed as , where the complex coefficients are
The convolution theorem adapts to this setting by stating that the Fourier coefficients of the periodic convolution satisfy
for every integer . This pointwise multiplication in the frequency domain simplifies computations for periodic signals, such as filtering or system responses in engineering contexts. The theorem holds under mild conditions, such as square-integrability over the period, ensuring the integrals converge.[12][13]
This periodic formulation relates to the aperiodic Fourier transform through the Dirac comb, or Shah function, . A P-periodic function can be viewed as the convolution of an aperiodic function (supported on ) with , yielding the infinite periodic extension. The Fourier transform of is , another comb, so the transform of the periodic function becomes the aperiodic transform modulated by this comb. Applying the convolution theorem in the transform domain then recovers the coefficient multiplication after sampling at discrete frequencies .[14]
A concrete example illustrates the theorem: the periodic convolution of two P-periodic square waves, each alternating between and with period P (a standard even square wave), produces a P-periodic triangular wave ranging from to . The square wave has Fourier coefficients for odd and 0 otherwise, decaying as ; their product yields for odd , matching the known series for the triangular wave and highlighting the smoothing effect of convolution.[15][16]
The factor in the convolution definition is essential for the theorem's clean form, as it mirrors the normalization in the coefficient integral. Omitting it would introduce an extraneous in the product , complicating reconstructions and applications like signal processing. This choice ensures the periodic case parallels the aperiodic transform limit as .[12]
Discrete circular convolution
In the discrete circular convolution, two finite-length sequences $ f[n] $ and $ g[n] $, each of length $ N $, are convolved using periodic extension with wrap-around, defined as
This operation treats the sequences as periodic with period $ N $, incorporating aliasing effects from the modulo arithmetic that differ from linear convolution.[17]
The convolution theorem for the discrete Fourier transform (DFT) states that the DFT of the circular convolution equals the pointwise product of the individual DFTs:
where the DFT is given by
This equivalence holds because the DFT basis functions are eigenfunctions of the circulant matrix representing circular convolution.[17][18]
Conversely, the circular convolution can be recovered via the inverse DFT (IDFT):
with the IDFT defined as
This relation enables efficient computation using fast Fourier transform (FFT) algorithms, reducing complexity from $ O(N^2) $ for direct summation to $ O(N \log N) $.[17][18]
A representative example involves the circular convolution of two 4-point finite impulse response sequences: $ h[n] = {-2, -1, 3, 1} $ and $ x[n] = {-1, 0, 2, 1} $. Their DFTs are $ H[k] = {1, -5 + 2i, 1, -5 - 2i} $ and $ X[k] = {2, -3 + i, 0, -3 - i} $, respectively. The product $ Y[k] = H[k] X[k] = {2, 13 - 11i, 0, 13 + 11i} $, and the IDFT yields $ y[n] = {7, 6, -6, -5} $, matching direct circular summation. This demonstrates utility in FFT-based filtering for periodic or block-processed signals.[19]
To approximate linear convolution without aliasing using circular convolution, sequences are zero-padded to length at least $ N_1 + N_2 - 1 $, where $ N_1 $ and $ N_2 $ are original lengths, ensuring the wrap-around does not overlap valid terms.[17][20]
Proofs
Continuous case derivation
The derivation for the continuous aperiodic case assumes that , the space of Lebesgue integrable functions over the real line, which guarantees the absolute convergence of the relevant integrals.[21] Under this assumption, the convolution is well-defined and also belongs to , with .[21] Consider the Fourier transform of the convolution, defined as
\mathcal{F}\{[f * g](/page/F&G)\}(\omega) = \int_{\mathbb{R}} \left( \int_{\mathbb{R}} f(\tau) g(t - \tau) \, d\tau \right) e^{-2\pi i [\omega](/page/Omega) t} \, dt.
[21] The integrand satisfies , and its double integral over equals , so Fubini's theorem permits interchanging the order of integration:[21]
\mathcal{F}\{[f * g](/page/F&G)\}(\omega) = \int_{\mathbb{R}} f(\tau) \left( \int_{\mathbb{R}} g(t - \tau) e^{-2\pi i \omega t} \, dt \right) d\tau.
[21] For the inner integral, perform the change of variables (so and ), yielding
[21] Substituting back gives
\mathcal{F}\{[f * g](/page/F&G)\}(\omega) = \mathcal{F}\{g\}(\omega) \int_{\mathbb{R}} f(\tau) e^{-2\pi i \omega \tau} \, d\tau = \mathcal{F}\{f\}(\omega) \, \mathcal{F}\{g\}(\omega),
[21] establishing the theorem.
The result extends to functions in via the Plancherel theorem, which shows that the Fourier transform is a unitary operator (isometry) on .[22] Specifically, the Schwartz functions (smooth with rapid decay) are dense in , the theorem holds on this dense subspace by the case (as Schwartz functions are in ), and continuity of the Fourier transform on yields the extension.[22]
An alternative derivation uses the Fourier inversion formula, which recovers as the inverse transform of .[23] Substituting into the convolution integral and interchanging orders (justified by Tonelli's theorem for nonnegativity or Fubini for integrability) with a change of variables leads to the inverse transform of the product , confirming the theorem.[23]
For functions not in but in , the Fourier transforms are defined only in the sense (not pointwise), and convolutions may require approximation by mollifiers; the theorem holds with equality in the norm, addressing convergence via the Plancherel isometry.[22]
Discrete case derivation
The discrete convolution theorem for aperiodic signals states that the discrete-time Fourier transform (DTFT) of the convolution of two sequences equals the pointwise product of their individual DTFTs, under suitable convergence conditions.[7] Consider two discrete-time signals and with DTFTs and , where the convolution is defined as
The DTFT of the convolution is
Assuming absolute convergence of the sequences, i.e., and , the double summation allows reordering by Fubini's theorem for sums.[7] This yields
For the inner sum, substitute , so and
Thus,
For periodic variants, the discrete Fourier transform (DFT) applies to finite-length sequences of length , where convolution becomes circular. The circular convolution is
The DFT of this circular convolution equals the product of the individual DFTs, leveraging the orthogonality of the complex exponentials.[24] Specifically, the DFT basis functions satisfy
which follows from the sum of a finite geometric series: for , the sum is , and for , it is . To derive the theorem, compute the DFT of :
Reordering gives
using the shift property and periodicity, resulting in .[24]
The theorem extends to square-summable sequences () via density arguments and an analog of Parseval's theorem, which equates the energy in time and frequency domains: .[25] Finite-support sequences (in ) satisfy the theorem directly, and sequences approximate these densely, allowing the result by continuity of the DTFT on .[25]
Generalizations
Inverse Fourier transform
The inverse Fourier transform of the pointwise product of two Fourier transforms equals the convolution of the original functions, providing the dual form of the convolution theorem. Specifically, if $ F = \mathcal{F}{f} $ and $ G = \mathcal{F}{g} $, then
where the convolution is defined as $ (f * g)(t) = \int_{-\infty}^{\infty} f(\tau) g(t - \tau) , d\tau $, assuming $ f $ and $ g $ are sufficiently integrable functions such as those in the Schwartz class or $ L^1(\mathbb{R}) $.[1][4]
This inverse form follows directly from the forward convolution theorem and the Fourier inversion theorem, which ensures that applying the forward and inverse transforms recovers the original function under appropriate conditions. By taking the inverse Fourier transform of both sides of the forward theorem $ \mathcal{F}{f * g} = F \cdot G $, and invoking the linearity and invertibility of the transform, the equivalence is established, highlighting the symmetry between the time and frequency domains.[1][26]
In the discrete setting, the analogous result holds for finite sequences using the discrete Fourier transform (DFT) and its inverse (IDFT). For sequences $ x[n] $ and $ y[n] $ of length $ N $, the circular convolution is given by
where $ (x \circledast y)[n] = \sum_{m=0}^{N-1} x[m] y[(n - m) \mod N] $, assuming zero-padding if necessary to avoid wrap-around effects in linear convolution approximations.[27][28]
A practical illustration arises in signal smoothing, where multiplying the Fourier transform of a signal by a low-pass filter's transfer function (e.g., a rectangular window in frequency) attenuates high frequencies, and the inverse transform yields a convolved time-domain signal that smooths the original via the filter's impulse response, such as a sinc function.[4] This duality is particularly advantageous in filter design, as pointwise multiplication in the frequency domain is computationally simpler than direct time-domain convolution, enabling efficient implementation via fast Fourier transform algorithms.[27]
Tempered distributions
Tempered distributions are continuous linear functionals on the Schwartz space , the space of smooth functions that decay rapidly at infinity along with all their derivatives.[29] These distributions, denoted , extend the notion of functions to include generalized objects like the Dirac delta, enabling the Fourier transform to be defined via for .[30] The convolution theorem generalizes to tempered distributions as follows: if is a tempered distribution and is a smooth function with compact support, then the convolution is a smooth function defined by , where and , and the Fourier transform satisfies in the distributional sense.[29] This product of distributions is well-defined because is a Schwartz function, which multiplies smoothly with any tempered distribution.[30] Convolution between two tempered distributions is defined provided at least one has compact support, ensuring the result is again a tempered distribution; for instance, if (compactly supported distributions) and , then .[31] A key property is that the Dirac delta distribution , defined by , acts as the identity under convolution: for any tempered distribution .[32] As an illustrative example, since the Fourier transform of is the constant function 1 (with appropriate normalization), the theorem yields , confirming consistency with .[32] A proof sketch proceeds by leveraging the density of Schwartz functions in suitable topologies and the pairing definition: for a test function , , where is a Schwartz function; applying the Fourier transform to both sides and using the known theorem for Schwartz functions gives , establishing the equality in the distributional sense.[29]Multidimensional extensions
The convolution theorem extends naturally to functions defined on or , generalizing the one-dimensional case where . In the continuous setting, the multidimensional convolution of two integrable functions and is defined as
where .[33]
The multidimensional Fourier transform of a function is given by
with and denoting the dot product; the inverse transform follows analogously with the positive exponent.[33] Under suitable integrability conditions (e.g., ), the convolution theorem states that the Fourier transform of the convolution equals the pointwise product of the individual transforms:
This property holds componentwise in the frequency domain, facilitating efficient computation for higher-dimensional signals such as those in imaging or physics simulations.[34]
In the discrete case, particularly for multidimensional arrays like digital images, the theorem applies via the multidimensional discrete Fourier transform (DFT). For two arrays and in two dimensions (), the 2D circular convolution is computed efficiently in the frequency domain: the 2D DFT of the convolution equals the product of the 2D DFTs, , followed by an inverse 2D DFT to recover the spatial result.[35] To avoid wraparound artifacts from periodicity, zero-padding is typically applied to extend the arrays to at least .[35] This is widely used in image processing for filtering operations, where the fast Fourier transform (FFT) implementation reduces complexity from to .[35]
A representative application is 2D Gaussian convolution for image blurring, where the kernel is a radially symmetric Gaussian . The 2D Fourier transform of this kernel is also Gaussian, , which is radial (depending only on ) and acts as a low-pass filter by attenuating high frequencies.[36] Convolving an image with thus multiplies by in the frequency domain, yielding a blurred image upon inversion; larger widens the Gaussian in space and narrows it in frequency, removing finer details.[36]
For separable functions, where over Cartesian coordinates, the multidimensional Fourier transform factors as , and the convolution theorem applies componentwise across dimensions.[33] This separability simplifies computations in applications like multidimensional filtering, reducing higher-dimensional operations to iterated one-dimensional transforms.[33]
Other integral transforms
The convolution theorem extends to other integral transforms, such as the Laplace transform and the Z-transform, which share the property that the transform of a convolution equals the product of the individual transforms, albeit with adaptations for their domains./09%3A_Transform_Techniques_in_Physics/9.09%3A_The_Convolution_Theorem)[37] For the Laplace transform, the theorem applies to causal functions, where the convolution is defined as the one-sided integral for , and the transform satisfies ./09%3A_Transform_Techniques_in_Physics/9.09%3A_The_Convolution_Theorem)[38] This formulation is particularly useful in analyzing linear time-invariant systems, such as where the output response is the convolution of an input with the system's impulse response, transforming to the product of their Laplace transforms (the transfer function).[39] The Z-transform, the discrete analog of the Laplace transform, exhibits a similar property for sequences: the Z-transform of the one-sided convolution is .[40][41] Unlike the bilateral Fourier transform, both the Laplace and Z-transforms are typically unilateral (one-sided), integrating or summing from zero onward, which suits them for stability analysis in causal systems and initial value problems but lacks the full inverse duality of the Fourier case.[42] These theorems were developed in the context of control theory following the Fourier transform's establishment, with the unilateral Laplace transform gaining prominence through applications in electrical engineering and system dynamics during the early 20th century.[43][44]Applications
Signal processing
In signal processing, the convolution theorem plays a central role in the analysis and implementation of linear time-invariant (LTI) systems, where the output signal is obtained by convolving the input signal with the system's impulse response. This operation, expressed as $ y[n] = \sum_{k=-\infty}^{\infty} x[k] h[n - k] $ for discrete-time signals, corresponds in the frequency domain to multiplication of their discrete Fourier transforms: $ Y(\omega) = X(\omega) H(\omega) $. This duality enables filter design by specifying the desired frequency response $ H(\omega) $ and then deriving the impulse response $ h[n] $ via inverse transform, facilitating efficient implementation of filters like equalizers and noise reducers.[45] A key practical advantage arises from accelerating convolution computations using the fast Fourier transform (FFT), which reduces the complexity from $ O(N^2) $ for direct time-domain convolution of length-$ N $ signals to $ O(N \log N) $ by transforming to the frequency domain, multiplying the spectra, and applying the inverse FFT. This FFT-based approach, leveraging the convolution theorem, is essential for processing long signals in real-time applications, such as echo cancellation and spectral analysis.[46][47] For instance, a low-pass filter can be designed by multiplying the input's frequency spectrum by a rectangular window function that attenuates high frequencies, with the equivalent time-domain operation being convolution with a sinc function $ h[n] = \frac{\sin(\omega_c n)}{\pi n} $ (where $ \omega_c $ is the cutoff frequency), effectively smoothing the signal while preserving low-frequency components. This method is widely used in audio equalization to remove unwanted high-frequency noise.[48][49] To handle long signals and mitigate artifacts from the circular convolution inherent in finite DFTs, techniques like overlap-add and overlap-save are employed. In the overlap-add method, the input is segmented into overlapping blocks, each convolved via FFT, and the results are added after aligning overlaps, yielding linear convolution without edge effects. Similarly, overlap-save discards corrupted overlap portions post-convolution, ensuring efficient streaming processing for extended data streams.[46][50] In modern audio processing, the convolution theorem underpins real-time systems enhanced by GPU-accelerated FFT libraries, enabling low-latency convolution reverbs and spatial audio rendering since the early 2000s, with implementations like NVIDIA's cuSignal achieving up to 10x speedups over CPU methods for multichannel processing.[51][52]Probability and statistics
In probability theory, the convolution of two probability density functions corresponds to the density of the sum of two independent continuous random variables. If and are independent random variables with densities and , the density of is given by the convolution
[53] This operation arises naturally from the joint density under independence, , and marginalizing over the sum.[54]
The convolution theorem simplifies analysis via characteristic functions, which are the Fourier transforms of the densities. For independent and , the characteristic function of is the product
where .[55] This multiplicative property holds because the expectation factors under independence, providing a direct application of the theorem without computing the integral convolution explicitly.[56] The density can then be recovered by the inverse Fourier transform of .[54]
A representative example is the Irwin–Hall distribution, which describes the sum of independent uniform random variables on . The density is the -fold convolution of the uniform density for . The characteristic function is the product , equivalent to a product of sinc functions since .[57] /05%3A_Special_Distributions/5.25%3A_The_Irwin-Hall_Distribution) This product form highlights how the theorem captures the smoothing effect of repeated convolutions, leading to a piecewise polynomial density.[53]
In statistics, the convolution theorem enables deconvolution to correct for measurement errors. Consider observations , where are i.i.d. errors independent of the signal with known error density . The density , so the characteristic functions satisfy . Solving for the signal gives , with obtained via inverse Fourier transform.[58] This approach is widely used in density estimation under errors, though it requires regularization if vanishes.[59]
The theorem extends to multivariate settings via multivariate characteristic functions. For independent random vectors and in , the characteristic function of is , where and .[54] This supports extensions to multinomial distributions, where the sum of independent multinomials follows a multinomial via convolution of probability mass functions, with the multivariate characteristic function product confirming the result.[60]