I always wondered about the idea behind convolution. I get what the definition of the convolution does (and I saw all the animations), but what I don't understand is how it relates to so many topics in physics. It seems to me that it is not really an intuitive concept. I guess my question is - what were the ideas, thoughts of the guy that discovered convolution?
About two years ago I read a blog post about convolution that explains it pretty intuitively, but I forgot the name of the website.
On
Intuition for Convolution
A convolution is an amount of overlap of one function f as it is shifted over another function g at a given time offset.
Let’s say we are transforming a certain function f(t) by passing it through a filter g(t) to get the output h(t):
f(t) -> [ g(t) ] -> h(t)
Say f(t) has the following values for t = [1, 2, 3, 4, 5] -> f(t) = [1, 2, 3, 4, 5], and
say g(t) has the following values for t = [1, 2, 3] -> g(t) = [3, 2, 1]
Now the question is what is the value of h(t) at a specified time t.
To find the value of h(t) at any time t, let's start with following -
Idea:
Imagine flipping the f(t) with respect to time values, because that is
what it looks like when it enters the filter [g(t)]
Now let's start here,
->| start of time (t)
[1, 2, 3] -> time
f(t) = [5, 4, 3, 2, 1]
g(t) = [3, 2, 1]
To calculate the values of h(t), let’s line up the values of f(t) and pass them through the values of g(t)
At t = 1
g(t) 3 2 1
f(t) 5 4 3 2 1
Total value 3 <-(3x1) = 3
At t = 2
g(t) 3 2 1
f(t) 5 4 3 2 1
Total value 6 2 <-(3x2)+(2x1) = 8
At t = 3
g(t) 3 2 1
f(t) 5 4 3 2 1
Total value 9 4 1 <-(3x3)+(2x2)+(1x1) = 14
At t = 4
g(t) 3 2 1
f(t) 5 4 3 2 1
Total value 12 6 2 <-(3x4)+(2x3)+(1x2) = 20
At t = 5
g(t) 3 2 1
f(t) 5 4 3 2 1
Total value 15 8 3 <-(3x5)+(2x4)+(1x3) = 26
At t = 6
g(t) 3 2 1
f(t) 5 4 3 2 1
Total value 10 4 <-(2x5)+(1x4) = 14
At t = 7
g(t) 3 2 1
f(t) 5 4 3 2 1
Total value 5 <-(1x5) = 5
Just by sliding to any t = n, we can find the value of h(t) by calculating the value of overlapped “area” at t = n.
Now the value h(t) = conv(g(t), h(t)) at any time t is as follows
g(t) * f(t) = h(t)
[3 2 1] * [1 2 3 4 5] = [3 8 14 20 26 14 5]
1 2 3 4 5 1 2 3 4 5 6 7
Note:
So far we have been doing a simple summation of terms as our functions are discrete, if we are dealing with continuous functions the integral as a limit of a summation would come into play.
If you have Matlab, please see https://www.mathworks.com/matlabcentral/fileexchange/4616-animated-convolution
Credit: The above example is based on the Intuitive Guide to Convolution @ Better Explained
On
I imagine convolution as a tail-to-head (flip) time dependent (sliding) "dot product" (please note the quotes) of two vectors as in the illustration below. This is just an analogy without geometrical counterpart, and it is easy to extend to the continuous convolution.
The key operation is flipping or reversing the entries of one of the two vectors (mathematically, this can be accomplished by multiplying one of the vectors by an exchange matrix, and corresponds to functions in computer languages such as 'flip' or 'reverse'). Naturally there are just functions to convolve, but it is interesting that there is no more specific name for this entry permutation (see here).
The motivation is to keep the sum of of the pairwise matches in each of these "dot products" constant, or identically, the sum of the inputs to the functions within the defining integral $(f*g)(t)=\displaystyle\int_{-\infty}^t f(\tau)g(t-\tau)\rm d\tau$
constant at $t=\tau + (t-\tau).$
This matching of indexed vector elements is very nicely exemplified when performing a polynomial multiplication as a convolution:
Each sliding step corresponds to multiplying coefficients of the terms with degrees adding up to a constant (the equivalent of a constant $t$), and adding them $\text{coeff}[x^n]=\sum_k a_k b_{n-k},$ where again $n=k+(n-k).$ This is the equivalent of integrating over tau from $-\infty$ to $t$ in the continuous counterpart.
Visually, the convolution integrates along directed lines along the domain of two variables $\tau,v,$ such that $\tau+v=t:$
The great example for this interpretation is the finding the distribution of the sum of two iid uniform random variables:
The sum of two independent variables $X$ and $Y$ can be proven to correspond to the convolution of $f_X(z)$ and $f_Y(z)$ at $z$, i.e.
$$f_Z(z)=(f * g)(z)= \int_{-\infty}^{+\infty}f_X(z-y)\,f_Y(y)\,\mathrm dy.$$
Here are a few great examples:
Well, here I want to give you just an intuition not a whole proof and abstract notions (convolution products are defined in abstract algebra), so it is a good way to start with Fourier transform. Let's begin with this theorem
$\hat{f}.\hat{g}=\mathcal{F}[\frac{1}{2\pi}f*g]$
where $\hat{f}$ and $\hat{g}$ are the Fourier transform of the functions $f$ and $g$ respectively and $\mathcal{F}$ is the Fourier transform symbol.
$\hat{f}=\frac{1}{2\pi}\int_{-\infty}^{\infty}f(x)e^{i\omega x}dx$
$\hat{g}=\frac{1}{2\pi}\int_{-\infty}^{\infty}g(x)e^{i\omega x}dx$
We just want to know "Where did convolution formula come from?" So we just need to accept the identity above and extend it to see what happens?
$\hat{f}.\hat{g}=\frac{1}{2\pi}\int_{-\infty}^{\infty}f(x)e^{i\omega x}dx .\frac{1}{2\pi}\int_{-\infty}^{\infty}g(x)e^{i\omega x}dx$
$=\frac{1}{4\pi^2}\int_{-\infty}^{\infty}f(x)e^{i\omega x}dx\int_{-\infty}^{\infty}g(x)e^{i\omega x}dx$
Now if we extend the right hand side of the first equation mentioned, we obtain:
$\frac{1}{2\pi}(\frac{1}{2\pi}\int_{-\infty}^{\infty}(f*g)e^{i\omega x}dx) = \frac{1}{4\pi^2}\int_{-\infty}^{\infty}(f*g)e^{i\omega x}dx$
In the equality the term $\frac{1}{4\pi^2}$ is omitted from both side and we obtain:
$\int_{-\infty}^{\infty}f(x)e^{i\omega x}dx\int_{-\infty}^{\infty}g(x)e^{i\omega x}dx=\int_{-\infty}^{\infty}(f*g)e^{i\omega x}dx$
Now we can ask "How can we have the product of two different integrals in only one integral?" (Note that by accepting the convolution and the theorems of Fourier transform we got here!).
Let's make it easier by writing $\int_{\Omega}\phi d\mu(x) \int_{\Omega}\psi d\mu(x)$ and how can we make them into one integral. We know from real analysis that we can write the integral as:
$\int \phi d\mu = \sum_{1}^{n}a_j\mu(E_j)$ and $\int \psi d\mu = \sum_{1}^{n}b_j\mu(E_j)$
where $E_j$ are elementary sets of the domain. For easier manipulation (this is just an intuition not a proof!) we suppose that for all $E_j$ we have $\phi(E_j)=a_j$ and $\psi(E_j)=b_j$ and with assumption that $\mu(E_j)=\mu(E_i)=1$ for all $i$ and $j$ ($\mu$ here is the measure of the sets $E_j$) then we can write
$\int \phi d\mu\int \psi d\mu = \sum_{1}^{n}a_j\mu(E_j)\sum_{1}^{n}b_j\mu(E_j)=$
$(a_1+a_2+\dots+a_n)(b_1+b_2+\dots+b_n)=$ $a_1(b_1+b_2+\dots+b_n)+a_2(b_1+b_2+\dots+b_n)+\dots+a_n(b_1+b_2+\dots+b_n)$
For the first term $a_1(b_1+b_2+\dots+b_n)$, we see that $a_1$ is multiplied in all values of the function $g$ and this process is repeated for other terms. This is like translating the function $f$ (compute its values in $E_j$s) and then multiply it by function of $g$ then sum them (integrate the function $f(x-t)g(x)$ over the translation domain).
Now we can understand the meaning of convolution: it is a way to take the product of two integrals into only one integral, and for doing that, you need to translate one function (like $f$) then multiply it by the other ($g$) and then sum the multiplications (integrate them).
Any useful comment to complete the answer is appreciated.