# convolution

## Introduction

 $(f\ast g)(u)=\int_{-\infty}^{\infty}f(x)g(u-x)dx.$

$(f\ast g)(u)$ is the sum of all the terms $f(x)g(y)$ where $x+y=u$. Such sums occur when investigating sums of random variables  , and discrete versions appear in the coefficients of products of polynomials and power series. Convolution is an important tool in data processing, in particular in digital signal and image processing. We will first define the concept in various general settings, discuss its properties and then list several convolutions of probability distributions.

## Definitions

If $G$ is a locally compact (topological) Abelian group  (http://planetmath.org/LocallyCompactGroupoids) with Haar measure $\mu$ and $f$ and $g$ are measurable functions on $G$, we define the convolution

 $(f\ast g)(u):=\int_{G}f(x)g(u-x)d\mu(x)$

whenever the right hand side integral  exists (this is for instance the case if $f\in L^{p}(G,\mu)$, $g\in L^{q}(G,\mu)$ and $1/p+1/q=1$).

The case $G=\mathbb{R}^{n}$ is the most important one, but $G=\mathbb{Z}$ is also useful, since it recovers the convolution of sequences which occurs when computing the coefficients of a product of polynomials or power series. The case $G=\mathbb{Z}_{n}$ yields the so-called cyclic convolution which is often discussed in connection with the discrete Fourier transform. Based on this definition one also obtains the groupoid    C*–convolution algebra (http://planetmath.org/GroupoidCConvolutionAlgebra)

If $X$ and $Y$ are independent  random variables with probability densities $f_{X}$ and $f_{Y}$ respectively, and if $X+Y$ has a probability density, then this density is given by the convolution $f_{X}\ast f_{Y}$. This motivates the following definition: for probability distributions $P$ and $Q$ on $\mathbb{R}^{n}$, the convolution $P\ast Q$ is the probability distribution on $\mathbb{R}^{n}$ given by

 $(P\ast Q)(A):=(P\times Q)\big{(}\{(x,y)\mid x+y\in A\}\big{)}=\int_{\mathbb{R}% ^{n}}Q(A-x)\,dP(x)$

for every Borel set $A$. The last equation is the result of Fubini’s theorem.

The convolution of two distributions   $u$ and $v$ on $\mathbb{R}^{n}$ is defined by

 $(u\ast v)(\phi)=u(\psi)$

for any test function $\phi$ for $v$, assuming that $\psi(t):=v(\phi(\cdot+t))$ is a suitable test function for $u$.

## Properties

The convolution operation, when defined, is commutative, associative and distributive with respect to addition. For any $f$ we have

 $f\ast\delta=f,$

where $\delta$ is the Dirac delta distribution. The Fourier transform   $F$ converts the convolution of two functions into their pointwise multiplication:

 $F(f\ast g)=F(f)\cdot F(g),$

which provides a great simplification in the computation of convolution. Because of the availability of the Fast Fourier Transform and its inverse    , this latter relation is often used to quickly compute discrete convolutions, and in fact the fastest known algorithms for the multiplication of numbers and polynomials are based on this idea.

## References

• Adapted with permission from The Data Analysis Briefbook (http://rkb.home.cern.ch/rkb/titleA.htmlhttp://rkb.home.cern.ch/rkb/titleA.html)

 Title convolution Canonical name Convolution Date of creation 2013-03-22 12:32:45 Last modified on 2013-03-22 12:32:45 Owner PrimeFan (13766) Last modified by PrimeFan (13766) Numerical id 31 Author PrimeFan (13766) Entry type Definition Classification msc 44A35 Classification msc 94A12 Synonym convolve Synonym fold Synonym convolved Synonym folded Related topic LogarithmicConvolution Related topic LaplaceTransformOfConvolution Related topic GroupoidCConvolutionAlgebra