PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (210)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (38)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
convolution (Definition)

Introduction

The convolution of two functions $ f,g : \Bbb{R} \rightarrow \Bbb{R}$ is the function

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

In a sense, $ (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 independent 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 abelian topological group with Haar measure $ \mu$ and $ f$ and $ g$ are measurable functions on $ G$, we define the convolution

$\displaystyle (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 = \Bbb{R}^n$ is the most important one, but $ G=\Bbb{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=\Bbb{Z}_n$ yields the so-called cyclic convolution which is often discussed in connection with the discrete Fourier transform.

The (Dirichlet) convolution of multiplicative functions considered in number theory does not quite fit the above definition, since there the functions are defined on a commutative monoid (the natural numbers under multiplication) rather than on an abelian group.

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 $ \Bbb{R}^n$, the convolution $ P \ast Q$ is the probability distribution on $ \Bbb{R}^n$ given by

$\displaystyle (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 $ \Bbb{R}^n$ is defined by

$\displaystyle (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

$\displaystyle f \ast \delta = f,$
where $ \delta$ is the Dirac delta distribution. The Fourier transform $ F$ translates between convolution and pointwise multiplication:
$\displaystyle F(f \ast g) = F(f) \cdot F(g).$
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.

Some convolutions of probability distributions

  • The convolution of two normal distributions with zero mean and variances $ \sigma_1^2$ and $ \sigma_2^2$ is a normal distribution with zero mean and variance $ \sigma^2 = \sigma_1^2 + \sigma_2^2$.
  • The convolution of two $ \chi^2$ distributions with $ f_1$ and $ f_2$ degrees of freedom is a $ \chi^2$ distribution with $ f_1 + f_2$ degrees of freedom.
  • The convolution of two Poisson distributions with parameters $ \lambda_1$ and $ \lambda_2$ is a Poisson distribution with parameter $ \lambda = \lambda_1 + \lambda_2$.
  • The convolution of an exponential and a normal distribution is approximated by another exponential distribution. If the original exponential distribution has density

    $\displaystyle f(x)=\frac{e^{-x/\tau}}{\tau} \;\;\; (x \ge 0)$    or $\displaystyle f(x)=0 \;\;\; (x < 0) , $

    and the normal distribution has zero mean and variance $ \sigma^2$, then for $ u \gg \sigma$ the probability density of the sum is

    $\displaystyle f(u) \approx \frac{e^{-u/\tau + \sigma^2/(2\tau^2)}}{\sigma \tau \sqrt{2\pi}} $

    In a semi-logarithmic diagram where $ \log(f_X(x))$ is plotted versus $ x$ and $ \log (f(u))$ versus $ u$, the latter lies by the amount $ \sigma^2/(2\tau^2)$ higher than the former but both are represented by parallel straight lines, the slope of which is determined by the parameter $ \tau$.

  • The convolution of a uniform and a normal distribution results in a quasi-uniform distribution smeared out at its edges. If the original distribution is uniform in the region $ a \le x < b$ and vanishes elsewhere and the normal distribution has zero mean and variance $ \sigma^2$, the probability density of the sum is

    $\displaystyle f(u) = \frac{\psi_0((u-a)/\sigma)-\psi_0((u-b)/\sigma)}{b-a}, $

    where

    $\displaystyle \psi_0(x) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^x e^{-t^2/2} dt $

    is the distribution function of the standard normal distribution. For $ \sigma \rightarrow 0$, the function $ f(u)$ vanishes for $ u<a$ and $ u>b$ and is equal to $ 1/(b-a)$ in between. For finite $ \sigma$ the sharp steps at $ a$ and $ b$ are rounded off over a width of the order $ 2\sigma$.

References



Anyone with an account can edit this entry. Please help improve it!

"convolution" is owned by mps. [ full author list (5) | owner history (2) ]
(view preamble)

View style:

See Also: logarithmic convolution

Other names:  convolve, fold, convolved, folded

Pronunciation (guide):
 convolution: /kon-v*-loo''sh*n/

Attachments:
associativity of convolution (Derivation) by mps
Log in to rate this entry.
(view current ratings)

Cross-references: order, width, finite, distribution function, vanishes, quasi-uniform, slope, lines, straight, parallel, exponential distribution, exponential, parameters, Poisson distributions, degrees of freedom, variances, mean, normal distributions, algorithms, pointwise, translates, Fourier transform, delta distribution, addition, distributive, associative, commutative, operation, Fubini's theorem, equation, Borel set, densities, abelian group, multiplication, natural numbers, commutative monoid, number theory, multiplicative functions, discrete Fourier transform, cyclic, sequences, integral, right hand side, measurable functions, Haar measure, topological group, abelian, locally compact, distributions, properties, power series, polynomials, products, coefficients, discrete, random variables, independent, terms, sum, functions
There are 22 references to this entry.

This is version 21 of convolution, born on 2002-03-13, modified 2007-06-26.
Object id is 2790, canonical name is Convolution.
Accessed 45872 times total.

Classification:
AMS MSC: 44A35 (Integral transforms, operational calculus :: Convolution)
 94A12 (Information and communication, circuits :: Communication, information :: Signal theory )
Pending Errata and Addenda
1. Definition of convolution, Sum of normals by Measure for Measure on 2008-04-18 18:11:15
[ View all 15 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)