Convolution
The convolution (German: Faltung) is a mathematical operator which takes two functions f and g and produces a function as output that represents the amount of overlap of the two functions for each relative translation. It is defined as the integral of the product of the two functions while one is reversed and shifted.
- (f * g) (τ) = ∫ f (t) g (τ - t) dt
The integration range depends on the domain on which the functions are defined. In case of a finite integration range, f and g are often considered as cyclically extended so that the term g (τ - t) does not imply a range violation. Of course, extension with zeros is also possible.
If X and Y are two independent random variables with probability densities f and g, respectively, then the probability density of the sum X + Y is given by the convolution f * g.
For discrete functions, one can use a discrete version of the convolution. It is then given by
- (f * g) (m) = ∑n f (n) g (m - n)
When multiplying two polynomials, the coefficients of the product are given by the convolution of the original coefficient sequences, in this sense (using extension with zeros as mentioned above).
Generalizing the above cases, the convolution can be defined for any two square-integrable functions defined on a locally compact topological group. A different generalization is the convolution of distributions.
The various convolution operators all satisfy the following properties:
Symmetry:
- f * g = g * f
Associativity:
- f * (g * h) = (f * g) * h
Distributivity:
- f * (g + h) = (f * g) + (f * h)
Associativity with scalar multiplication:
- a (f * g) = (a f) * g = f * (a g)
for any real (or complex) number a.
Derivation rule:
- D(f * g) = Df * g = f * Dg
where Df denotes the derivative of f or, in the discrete case, the difference operator Df(n) = f(n+1) - f(n).
- F(f * g) = (F f) · (F g)
where F f denotes the Fourier transform of f