Convolution

01 Theory

Theory 1

THEOREM: Continuous PDF of a sum

Let $f_{X,Y}(x,y)$ be any joint continuous PDF.

Suppose $W=X+Y$. Then:

$$f_W(w)={\int }_{-\infty }^{+\infty }{f}_{X,Y}(u,w-u)du$$

When $X$ and $Y$ are independent, so $f_{X,Y}=f_X{f}_Y$, this becomes convolution:

$$f_W(w)=f_X\ast f_Y={\int }_{-\infty }^{+\infty }{f}_X(u)f_Y(w-u)du$$

Extra - Derivation of $X+Y$ PDF

The joint CDF of $X+Y$:

$$F_{X+Y}(w)=P[X+Y\le w]={\iint }_{x+y\le w}{f}_{X,Y}(x,y)dxdy$$

Find $f_{X+Y}$ by differentiating:

$$f_{X+Y}(w)=\frac{d}{dw}{F}_{X+Y}(w)\gg \gg \frac{d}{dw}{\iint }_{x+y\le w}{f}_{X,Y}(x,y)dxdy$$

To calculate this derivative, change variables by setting $u=x$ and $s=x+y$. The Jacobian is 1, so $dxdy$ becomes $duds$, and we have:

$$\gg \gg \frac{d}{dw}{\int }_{-\infty }^w{\int }_{-\infty }^{+\infty }{f}_{X,Y}(u,s-u)duds\gg \gg {\int }_{-\infty }^{+\infty }{f}_{X,Y}(u,w-u)du$$

Link to original

02 Illustration

Example - Sum of parabolic random variables

Sum of parabolic random variables

Suppose $X$ is an RV with PDF given by:

$$f_X(x)=\{\begin{array}{ll}\frac{3}{4}(1-x^2)& x\in [-1,1]\\ 0& \text{otherwise}\end{array}$$

Let $Y$ be an independent copy of $X$. So $f_Y=f_X$, but $Y$ is independent of $X$.

Find the PDF of $X+Y$.

Solution

The graph of $f_X(w-x)$ matches the graph of $f_X(x)$ except (i) flipped in a vertical mirror, (ii) shifted by $w$ to the left.

When $w\in [-2,0]$, the integrand is nonzero only for $x\in [-1,w+1]$:

$$\begin{array}{rl}{f}_{X+Y}(w)& ={\left(\frac{3}{4}\right)}^2{\int }_{-1}^{w+1}(1-(w-x{)}^2\left)\right(1-x^2)dx\\ & =\frac{9}{16}\left(\frac{w^5}{30}-\frac{2w^3}{3}-\frac{4w^2}{3}+\frac{16}{15}\right)\end{array}$$

When $w\in [0,+2]$, the integrand is nonzero only for $x\in [w-1,+1]$:

$$\begin{array}{rl}{f}_{X+Y}(w)& ={\left(\frac{3}{4}\right)}^2{\int }_{w-1}^{+1}(1-(w-x{)}^2\left)\right(1-x^2)dx\\ & =\frac{9}{16}\left(-\frac{w^5}{30}+\frac{2w^3}{3}-\frac{4w^2}{3}+\frac{16}{15}\right)\end{array}$$

Final result is:

$$f_{X+Y}(w)=\{\begin{array}{ll}\frac{9}{16}\left(\frac{w^5}{30}-\frac{2w^3}{3}-\frac{4w^2}{3}+\frac{16}{15}\right)& w\in [-2,0]\\ & \\ \frac{9}{16}\left(-\frac{w^5}{30}+\frac{2w^3}{3}-\frac{4w^2}{3}+\frac{16}{15}\right)& w\in [0,2]\\ & \\ 0& \text{otherwise}\end{array}$$

Link to original

03 Theory - extra

Theory 3

Videos by 3Blue1Brown:

• Why X+Y in probability is a beautiful mess
• But what is a convolution?

Convolution

The convolution of two continuous functions $f(x)$ and $g(x)$ is defined by:

$$(f\ast g)(x)={\int }_{-\infty }^{+\infty }f(x-t)g(t)dt$$

For more example calculations, look at 9.6.1 and 9.6.2 at this page.

Applications of convolution

• Convolutional neural networks (machine learning theory: translation invariant NN, low pre-processing)
• Image processing: edge detection, blurring
• Signal processing: smoothing and interpolation estimation
• Electronics: linear translation-invariant (LTI) system response: convolution with impulse function

Extra - Convolution

Geometric meaning of convolution
Convolution does not have a neat and precise geometric meaning, but it does have an imprecise intuitive sense.

The product of two quantities tends to be large when both quantities are large; when one of them is small or zero, the product will be small or zero. This behavior is different from the behavior of a sum, where one summand being large is sufficient for the sum to be large. A large summand overrides a small co-summand, whereas a large factor is scaled down by a small cofactor.

The upshot is that a convolution will be large when two functions have similar overall shape. (Caveat: one function must be flipped in a vertical mirror before the overlay is considered.) The argument value where the convolution is largest will correspond to the horizontal offset needed to get the closest overlay of the functions.

Algebraic properties of convolution

• $f\ast g=g\ast f$
• $f\ast (g\ast h)=(f\ast g)\ast h$
• $f\ast (g+h)=f\ast g+f\ast h$
• $a(f\ast g)=(af)\ast g=f\ast (ag)$
• $(f\ast g{)}^{\prime }=f^{\prime }\ast g=f\ast g^{\prime }$

The last of these is not the typical Leibniz rule for derivatives of products!

All of these properties can be checked by simple calculations with iterated integrals.

Convolution in more variables
Given $f,g:{\mathbb{R}}^n\to \mathbb{R}$, their convolution at $\mathbf{x}$ is defined by integrating the shifted products over the whole domain:

$$(f\ast g)(\mathbf{x})={\iiint }_{{\mathbb{R}}^n}f(\mathbf{x}-\mathbf{y})g(\mathbf{y})dy$$

Link to original