Convolution

Convolution has applications that include probability, statistics, acoustics, spectroscopy, signal processing and image processing, geophysics, engineering, physics, computer vision and differential equations.

[1] The convolution can be defined for functions on Euclidean space and other groups (as algebraic structures).

(i.e., zero for negative arguments), the integration limits can be truncated, resulting in: For the multi-dimensional formulation of convolution, see domain of definition (below).

A common engineering notational convention is:[2] which has to be interpreted carefully to avoid confusion.

In terms of the Fourier transforms of the input and output of an LTI operation, no new frequency components are created.

Formally: One of the earliest uses of the convolution integral appeared in D'Alembert's derivation of Taylor's theorem in Recherches sur différents points importants du système du monde, published in 1754.

[6] Also, an expression of the type: is used by Sylvestre François Lacroix on page 505 of his book entitled Treatise on differences and series, which is the last of 3 volumes of the encyclopedic series: Traité du calcul différentiel et du calcul intégral, Chez Courcier, Paris, 1797–1800.

[7] Soon thereafter, convolution operations appear in the works of Pierre Simon Laplace, Jean-Baptiste Joseph Fourier, Siméon Denis Poisson, and others.

[9][10] The operation: is a particular case of composition products considered by the Italian mathematician Vito Volterra in 1913.

For example, convolution of digit sequences is the kernel operation in multiplication of multi-digit numbers, which can therefore be efficiently implemented with transform techniques (Knuth 1997, §4.3.3.C; von zur Gathen & Gerhard 2003, §8.2).

Convolutions of the type defined above are then efficiently implemented using that technique in conjunction with zero-extension and/or discarding portions of the output.

Conditions for the existence of the convolution may be tricky, since a blow-up in g at infinity can be easily offset by sufficiently rapid decay in f. The question of existence thus may involve different conditions on f and g: If f and g are compactly supported continuous functions, then their convolution exists, and is also compactly supported and continuous (Hörmander 1983, Chapter 1).

More generally, if either function (say f) is compactly supported and the other is locally integrable, then the convolution f∗g is well-defined and continuous.

More generally, Young's inequality implies that the convolution is a continuous bilinear map between suitable Lp spaces.

The same result holds if f and g are only assumed to be nonnegative measurable functions, by Tonelli's theorem.

More generally, in the case of functions of several variables, an analogous formula holds with the partial derivative: A particular consequence of this is that the convolution can be viewed as a "smoothing" operation: the convolution of f and g is differentiable as many times as f and g are in total.

On the other hand, two positive integrable and infinitely differentiable functions may have a nowhere continuous convolution.

In the discrete case, the difference operator D f(n) = f(n + 1) − f(n) satisfies an analogous relationship: The convolution theorem states that[26] where

denotes Hadamard product (this result is an evolving of count sketch properties[32]).

Informally speaking, the following holds Thus some translation invariant operations can be represented as convolution.

The representing function gS is the impulse response of the transformation S. A more precise version of the theorem quoted above requires specifying the class of functions on which the convolution is defined, and also requires assuming in addition that S must be a continuous linear operator with respect to the appropriate topology.

If G is a suitable group endowed with a measure λ, and if f and g are real or complex valued integrable functions on G, then we can define their convolution by It is not commutative in general.

In typical cases of interest G is a locally compact Hausdorff topological group and λ is a (left-) Haar measure.

A direct calculation shows that its adjoint T* is convolution with By the commutativity property cited above, T is normal: T* T = TT* .

According to spectral theory, there exists an orthonormal basis {hk} that simultaneously diagonalizes S. This characterizes convolutions on the circle.

Specifically, we have which are precisely the characters of T. Each convolution is a compact multiplication operator in this basis.

A similar result holds for compact groups (not necessarily abelian): the matrix coefficients of finite-dimensional unitary representations form an orthonormal basis in L2 by the Peter–Weyl theorem, and an analog of the convolution theorem continues to hold, along with many other aspects of harmonic analysis that depend on the Fourier transform.

[34] If μ and ν are probability measures on the topological group (R,+), then the convolution μ∗ν is the probability distribution of the sum X + Y of two independent random variables X and Y whose respective distributions are μ and ν.

Let φ, ψ ∈ End(X), that is, φ, ψ: X → X are functions that respect all algebraic structure of X, then the convolution φ∗ψ is defined as the composition The convolution appears notably in the definition of Hopf algebras (Kassel 1995, §III.3).

A bialgebra is a Hopf algebra if and only if it has an antipode: an endomorphism S such that Convolution and related operations are found in many applications in science, engineering and mathematics.