There is a tool in mathematics that I have used a lot of times and I'm still not confortable with. In fact I can't figure out (by this I mean that I cannot understand it geometrically) why does convolution regularize things. It is know for example that if $u\in L_{loc}^1(\mathbb{R}^N)$ and $f\in C_0^k(\mathbb{R}^N)$, then $f\ast u\in C^k(\mathbb{R}^N)$ and $$D^\alpha (f\ast u)=(D^\alpha f)\ast g$$

Well, I have a lot of questions about convolution that might help me understand it better and I would appreciated one who points me out references to read and some insight about it.

I - For what reason was convolution implemented in mathematics? Was it for regularizing functions? Who used it the first time?

II - Is there any intuitive way to find out why convolution make functions more smooth?

I can understand the analytical proof of II, but in the end it is just algebraic manipulations and I dont get the essence of the thing. Thank you for your help.

up vote 21 down vote accepted

Perhaps this might soothe some of your discomfort.

Smoothing Action

There are many ways that convolution is useful in mathematics. First of all, as you have noted, $$ \mathrm{D}^\alpha\left(f\ast g\right)=\left(\mathrm{D}^\alpha f\right)\ast g\tag{1} $$ This is simply repeated changes of the order of integration and differentiation: $$ \frac{\mathrm{d}}{\mathrm{d}x}\int f(x-t)\,g(t)\,\mathrm{d}t=\int f'(x-t)\,g(t)\,\mathrm{d}t\tag{2} $$ This step can be justified in different ways depending on the context. For instance, if the limit which defines the derivative of $f$, $$ f'(x)=\lim_{h\to0}\frac{f(x+h)-f(x)}{h}\tag{3} $$ converges uniformly, then $(2)$ is valid for all $g\in L^1$.

Convolution combines the smoothness of two functions. That is, if both $f$ and $g$, and their first derivatives are in $L^1$, then the second derivative of their convolution is in $L^1$. This is because $f\ast g = g\ast f$, and so we can use $(2)$ twice to get $$ \frac{\mathrm{d}^2}{\mathrm{d}x^2}(f\ast g)=f'\ast g'\tag{4} $$

Fourier Analysis

Convolution plays an important role in Fourier Analysis. The key formulas demonstrate the duality between convolution and multiplication: $$ \mathscr{F}(f\ast g)=\mathscr{F}(f)\mathscr{F}(g)\quad\text{and}\quad\mathscr{F}(fg)=\mathscr{F}(f)\ast\mathscr{F}(g)\tag{5} $$ There also exists a duality between decay at $\infty$ and smoothness. Essentially, one derivative of smoothness of $f$ corresponds to one factor of $1/x$ in the decay of $\mathscr{F}(f)$, and vice versa.

The product of decaying functions decays even faster; e.g. $x^{-n}x^{-m}=x^{-(n+m)}$. The duality demonstrated in $(5)$ then says that the convolution of smooth functions is even smoother.

The Riemann-Lebesgue Lemma says that for $f\in L^1$, $$ \lim_{|x|\to\infty}\mathscr{F}(f)(x)=0\tag{6} $$ However, this is simply decay with no quantification. About all that can be said about $f,g\in L^1$ is that $f\ast g\in L^1$. However, if $f,g\in L^2$, then $f\ast g$ is continuous.

Summing Dice

Perhaps one of the earliest uses of convolution was in probability. If $f_n(k)$ is the number of ways to roll a $k$ on $n$ six-sided dice, then $$ f_n(k)=\sum_jf_{n-1}(k-j)f_1(j)\tag{7} $$ That is, for each way to achieve $k$ on $n$ dice, we must have $k-j$ on $n-1$ dice and $j$ on the remaining die. Equation $(7)$ represents discrete convolution.

The distribution function for the roll of a single six-sided die is evenly distributed among $6$ possibilities. This has discontinuities at $1$ and $6$ ($n=1$). The distribution function for the sum of two six-sided dice is the convolution of two of the one die distributions. This is continuous, but not smooth ($n=2$). The distribution function for the sum of three six-sided dice is the convolution of the one die and two dice distributions. This is smooth ($n=3$). For each die we add, we convolve one more of the one die distributions and the function gets smoother.

$\hspace{8mm}$enter image description here

As $n\to\infty$, the distribution approaches a scaled version of the normal distribution: $\frac1{\sqrt{2\pi}}e^{-x^2/2}$.

  • Where does it come from that $f\star g$ is continuous when $f,g \in L^2$ – incas Mar 20 '15 at 14:16
  • 1
    Plancherel's Theorem says that $\hat{f},\hat{g}\in L^2$. The Cauchy-Schwarz Inequality says that $\hat{f}\hat{g}\in L^1$. Finally, the Fourier Transform of an $L^1$ function is uniformly continuous: $\widehat{\hat{f}\hat{g}}(-x)=f\ast g(x)$. – robjohn Mar 20 '15 at 14:41
  • Ok I am sorry if it is obvious but I still don't get it, for me all you have when you fourrier transform an L^1 function is an $L^{\infty}$ function that decays at infty. – incas Mar 20 '15 at 18:03
  • This link in my previous comment says that the Fourier transform of an integrable function ($L^1$) is uniformly continuous. – robjohn Mar 20 '15 at 18:10
  • Ok, I have seen the proof of that in the Rudin, Thanks for the info. It's the kind of things that are important to keep in mind. – incas Mar 20 '15 at 18:39

Concerning II:

When $f$ is a smooth function then all its translates $T_xf$, defined by $T_xf(t):=f(t-x)$, are equally smooth. Convolution of $f$ with an arbitrary $u$ can be viewed as a linear combination of such translates: $$f*u=\int_{-\infty}^\infty u(x)\>T_x f\ dx\ ,$$ therefore we expect that it inherits this smoothness. Looking now what this process has done to $u$ we get the feeling that $u$ has been smoothed out in this way.

I can't help with the first question. As for the second, the way I think of it intuitively is that the convolution of two functions mixes their values and integrates. Integrating means averaging out, so whatever properties each function brought in to the convolution are relaxed. For instance, if one function had a sharp corner in its graph but was otherwise quite tame, then the contribution of the sharp point to the convolution will be moderated by the smoothness of the function at other points. This is why local ill-behavior tends to disappear in the convolution. I hope this helps.

Came across this question and thought I'd give my two (late) cents.

Point I:

I can't do much more than redirect you to interesting links: IEEE post, IEEE paper, SO question, and obviously the wiki.

Point II:

The goal of smoothing is to reduce the noise in a signal by sharing information between neighboring measurements. The simplest way of smoothing a signal is to uniformly average the values in a certain window. I.e.: suppose you measure $x = [s_1, s_2, s_3, s_4, s_5]$ where each $s_i = t_i + n_i$ has a true value altered by some noise, the noise affecting the average $\bar{x}$ is $\frac{1}{M}\sum_i n_i$ which has a much smaller variance.

I'll now show how convolution is related mathematically to the concept of average smoothing in the 1-D continuous case:

  1. The integral average $m(t)$ of a function $f(t)$ is $m(t) = \frac{1}{2\delta} \int_{t-\delta}^{t+\delta} f(t') dt' = \int_{t-\delta}^{t+\delta} \frac{1}{2\delta} f(t') dt'$.

  2. Lets define a function $g(t')$ uniform between the values of $+\delta$ and $-\delta$, i.e. $g(t') = \frac{1}{2\delta}$ if $-\delta \le t' \le +\delta$. Since it is symmetric $g(t')=g(-t')$; furthermore, its value if the input is translated by an amount $t$ is: $g(t-t') = \frac{1}{2\delta}$ if $t-\delta \le t' \le t+\delta$

  3. By combining points 1 and 2 above we can see how the integral average $m(t)$ is exactly the convolution between the original function $f(t)$ and the filter function g(t): $m(t) = \int_{t-\delta}^{t+\delta} \frac{1}{2\delta} f(t') dt = \int_{t-\delta}^{t+\delta} g(t-t') f(t') dt' = \int_{-\infty}^{+\infty} g(t-t') f(t') dt' \overset{\Delta}{=} (f * g)(t)$.

In other words, you can think of the convolution operator as nothing more than a useful mathematical tool that allows you to implement an average of your data over a certain window.


Extra remarks:

  • The same concepts above hold true if instead of uniform average smoothing you wish to apply another smoothing, i.e. gaussian weighted average smoothing. To do so, you simply have to change the definition of your filter function $g(t)$ so that instead of uniform with support $(-\delta,+\delta)$ and value $\frac{1}{2\delta}$ it is a gaussian: $g(t)=\frac{1}{\sigma\sqrt{2\pi}}e^{\frac{-t^2}{2\sigma^2}}$.

  • The same holds true for the multi-dimensional case, i.e. Gaussian smoothing in images.

When you convolve signal of length N with itself, you get a sequence of length 2N but the value at Nth sample of this sequence is the energy of the signal. So in communication system, if you receive one of two possible functions of time (called two symbols) and want to recognize which one is. You should have two known functions (symbols) or templates at the receiver. Then convolve the unknown received function with these two known templates and compare the resultant values at Nth sample. Then assign the received function to the category of the template providing the maximum convolution value at Nth sample.

Convolution of a signal with itself provides the auto-correlation function of the signal which is the energy spectrum in the frequency domain. So,first convolution provides the energy spectrum, second convolution provides the square of the energy spectrum, third convolution provides square of square of energy spectrum, and so on. Then such procedure enhances the main-loop and diminishes the minor-loops in the frequency domain, which means better smoothing since the original signal to be convolved is a lowpass one.

Both I and II can be addressed by thinking of an engineering device that, to each signal (given by a real-valued function $f(t)$ of time) responds like a linear operator $A$ acting on the space of such functions. The device is stationary; i.e., its response to a given signal value remains unchanged with time. That means, $A$ preserves time shifts: $(Af)(t-s) = A [ f(t-s)]$.

If $\delta(u)$ is the Dirac delta function, then $f(t) = \int_{-\infty}^{\infty} f(s) \delta(t-s) ds$, and consequently (because the latter integral can be approximated by Riemann sums where instead of $\delta$ one uses its rectangular approximations), one has:

$(Af)(t) = \int_{-\infty}^{\infty} f(s) (A \delta)(t-s) ds$. Thus, to know how the device will respond to any $f(t)$, all we need to know is its response to an impulse: $(A \delta)$. This is one very important reason for implementing convolution (your question I).

To answer II (how the convolution smoothes things), replace in the latter integral the function $\delta$ by a smooth approximation (a "mollifier'' https://en.wikipedia.org/wiki/Mollifier). The mollifier is the smooth result of "smearing" the highly discontinuous $\delta$ along the time axis. Thus, the convolution in which $\delta$ is replaced by the mollifier also has the effect of "smoothing by smearing" the input signal $f(t)$.

See section 17.4.1 of this book: https://books.google.com/books?id=q5KRCwAAQBAJ&printsec=frontcover&dq=zorich+mathematical+analysis+II&hl=en&sa=X&ved=0ahUKEwj-oZy_6-fNAhUU5WMKHcQ2DLIQ6AEIKzAC#v=onepage&q=convolution&f=false

  • Did you mean for the first integral to have $f(s)$ rather than $f(t)$ under the integration? Because as written it isn't a convolution. Also it seems rather sketchy to argue that convolution was introduced to express how to evaluate a function at a point; there are easier ways. Finally you do not so much explain why a "mollifer" is a smoothing operator as you talk around the point. A look at previous Answers, esp. the Accepted Answer, should serve as a standard to surpass for a Question now some three years old. – hardmath Jul 10 '16 at 2:55
  • The mistakes in the integrals are now corrected, thanks! My argument for convolution is not so much to evaluate a function at a point, but to use our knowledge of how a device reponds to an impulse for determining how it will reponse to a more complicated signal. As for the mollifier, if I understand your point correctly, yes, I do explain only the intent behind using the mollifier. Years of teaching have convinced me that going through the motions is not nearly as instructive as explaining the goals. – avs Jul 10 '16 at 7:26

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.