What is convolution intuitively? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T21:25:53Z http://mathoverflow.net/feeds/question/5892 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/5892/what-is-convolution-intuitively What is convolution intuitively? Kim Greene 2009-11-18T01:23:35Z 2012-10-27T00:23:21Z <p>If random variable $X$ has a probability distribution of $f(x)$ and random variable $Y$ has a probability distribution $g(x)$ then $(f*g)(x)$, the convolution of $f$ and $g$, is the probability distribution of $X+Y$. This is the only intuition I have for what convolution means.</p> <p>Are there any other intuitive models for the process of convolution?</p> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/5894#5894 Answer by John D. Cook for What is convolution intuitively? John D. Cook 2009-11-18T01:41:53Z 2009-11-18T01:41:53Z <p>Maybe it would help your intuition to think about the discrete case first where the convolution is a sum rather than an integral. (f*g)(x) is the sum of f(i) g(j) over all (i, j) that sum to x.</p> <p>Or maybe you could think of convolution as a kind of multiplication. Convolution makes certain function spaces into algebras.</p> <p>Or you could think in terms of Fourier transforms: the Fourier transform of f*g is the product of the Fourier transforms of f and g. </p> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/5899#5899 Answer by Theo Johnson-Freyd for What is convolution intuitively? Theo Johnson-Freyd 2009-11-18T02:10:48Z 2009-11-18T02:10:48Z <p>The way you have described <em>is</em> the best way to think about convolution. More generally, if you have a group and a class of square-integrable functions (really I should say "half-densities") on it, then the convolution product precisely extends the group product.</p> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/5908#5908 Answer by S. Carnahan for What is convolution intuitively? S. Carnahan 2009-11-18T02:43:52Z 2009-11-18T02:43:52Z <p>I think one's standards of intuitiveness depend strongly on one's background. Even if a picture seems unintuitive at first, it can be helpful later.</p> <ol> <li>If you're an algebraist, I'd suggest the multiplication operation in group rings or monoid rings (easiest example: polynomial rings).</li> <li>If you like differential or integral operators, I'd suggest convolving with derivatives of delta and Heaviside functions to realize derivatives and integrals.</li> <li>If you like multiplying large numbers (or power series) together, convolution in the places (possibly with a carry) is the process by which this is done.</li> </ol> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/5916#5916 Answer by Terry Tao for What is convolution intuitively? Terry Tao 2009-11-18T04:01:32Z 2009-11-18T04:01:32Z <p>I remember as a graduate student that Ingrid Daubechies frequently referred to convolution by a bump function as "blurring" - its effect on images is similar to what a short-sighted person experiences when taking off his or her glasses (and, indeed, if one works through the geometric optics, convolution is not a bad first approximation for this effect). I found this to be very helpful, not just for understanding convolution per se, but as a lesson that one should try to use physical intuition to model mathematical concepts whenever one can.</p> <p>More generally, if one thinks of functions as fuzzy versions of points, then convolution is the fuzzy version of addition (or sometimes multiplication, depending on the context). The probabilistic interpretation is one example of this (where the fuzz is a a probability distribution), but one can also have signed, complex-valued, or vector-valued fuzz, of course.</p> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/5917#5917 Answer by Yemon Choi for What is convolution intuitively? Yemon Choi 2009-11-18T04:04:32Z 2009-11-18T04:04:32Z <p>This is really following on from John's answer, but is a bit long for a comment, so I thought I'd write it out here for extra clarity.</p> <p>Say you have a semigroup S, and you take the free (complex) vector space this generates, call it $C^S$. By construction/definition this has a distinguished basis, indexed by elements of the semigroup; and since we have a semigroup structure, that means we can multiply basis elements to get other basis elements. But that now gives us a way to multiply two vectors $a$ and $b$ together: write $a$ and $b$ as linear combinations of basis elements, and then define their product as the obvious (bi)linear extension of the multiplication on basis elements. If you do all this starting with $S={\bf Z}$, the group of integers, then what we've done is defined multiplication of trigonometric polynomials, or convolution of finitely supported sequences.</p> <p>The thing I like about this point of view is that it immediately generalises to $l^1(S)$, and makes $l^1(S)$ into a Banach algebra. If $S$ is a topological group with a Haar measure on it -- such as the real line with Lebesgue measure -- then the same idea gives us the usual Banach algebra structure on $L^1(S)$, which in the case $S={\bf R}$ is precisely the convolution of integrable functions in the usual sense.</p> <p>(At this point someone -- often me -- usually wants to mention forgetful functors from algebras to vector spaces and from semigroups to sets, but that's probably getting a bit OTT for the question at hand.)</p> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/5919#5919 Answer by Harald Hanche-Olsen for What is convolution intuitively? Harald Hanche-Olsen 2009-11-18T04:13:41Z 2009-11-18T04:13:41Z <p>What is the operator $C_f\colon g\mapsto f*g$? Consider the translation operator $T_y$ defined by $T_y(g)(x)=g(x-y)$, and look at $f*g(x)=\int_{\mathbb{R}}f(y)g(x-y)dy$. Rewriting this as an operator by taking out $g$, you end up with the operator equation $$C_f=\int_{\mathbb{R}}f(y)T_ydy.$$ This is only formally correct of course, but it roughly says that convolution with $f$ is a linear combination of translation operators, the integral being a sort of generalized sum.</p> <p>Tying this in with Terry Tao's answer, which came in while I was writing the above, if $f$ is a bump function, say nonnegative, with integral equal to 1 and concentrated near the origin, then $f*g$ is a (generalized) linear combination of translates of $g$, each one translated just a short distance, hence the blurryness of the result.</p> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/5940#5940 Answer by vonjd for What is convolution intuitively? vonjd 2009-11-18T08:56:00Z 2009-11-18T08:56:00Z <p>Have a look here - its rather helpful!</p> <p><a href="http://answers.yahoo.com/question/index?qid=20070125163821AA5hyRX" rel="nofollow">http://answers.yahoo.com/question/index?qid=20070125163821AA5hyRX</a></p> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/18923#18923 Answer by rgrig for What is convolution intuitively? rgrig 2010-03-21T11:40:52Z 2010-03-21T11:40:52Z <p>The two things that first come to mind when I think 'convolution' are:</p> <ol> <li><p>It's the thing that corresponds to multiplication on the other side of the Fourier transform. (This was already mentioned by John D. Cook) It works both ways, of course, $\mathcal F (f*g)=\mathcal F f\cdot \mathcal F g$ and $\mathcal F (f\cdot g)=\mathcal F f* \mathcal F g$. This fact is useful when used in combination with other simple facts about the Fourier transform (such as the fact that a rectangular function corresponds to sinc and, in the limit, a Dirac impulse corresponds to a constant function).</p></li> <li><p>Imagine a black box that receives one number $x_n$ every second and must output a number $y_n$ every second. (<a href="http://en.wikipedia.org/wiki/Digital_signal_processing" rel="nofollow">DSP</a> people call it a 'filter' and it's used, for example, to process audio signals in a mobile phone in real-time.) The simplest thing the box could do is to output some function of the current input. The natural next step is to remember the last <em>k</em> inputs and output some function of those <em>k</em> values. One of the simplest functions is a linear combination $$y_n=\sum_i c_i x_{n-i}$$ where $c_i$ is non-zero only for <code>$0\le i&lt;k$</code>. That's a convolution! To generalize, you make the filter remember all previous values and even be clairvoyant. That is, you extend the support of $[c_n]$. Then, if you want, you replace digital circuits with analog ones. That is, you go from summing to integration.</p></li> </ol> <p>As an example of combining these two points, if the filter always outputs the average of the last <em>k</em> inputs then that's a convolution with the rectangular function in the time domain so it must be a multiplication with a sinc in the frequency domain. Therefore, averaging the last <em>k</em> values attenuates high frequencies. (Hardly surprising, but at least you see immediately that the frequency response is not monotonic and there are only a few frequencies that are <em>completely</em> filtered out.)</p> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/18925#18925 Answer by Anweshi for What is convolution intuitively? Anweshi 2010-03-21T12:45:28Z 2010-03-21T13:53:56Z <p>It looks I am a bit late to the party; but hopefully not too late. I can contribute one instance where the application of convolution is very enlightening. Look at this in the light of Harald Hanche-Olsen's answer.</p> <p>Let us consider the operation of a signal processing system, or an electrical network, or a control system. </p> <p>Let $i(t)$ be the response of the system to the unit impulse function, ie the Dirac delta function, $\delta(t)$. Now we give an arbitrary signal $f(t)$ as input to the system. Then, the response of the system to $f(t)$ is</p> <p>$(f * i) (t)$,</p> <p>i.e. the convolution of $i$ and $f$.</p> <p>Next, in the spirit of rgrig's answer, I add that convolution becomes multiplication in the frequency domain. In that domain, it is like you multiply individually at each frequency component and add up again(ie integrate).</p> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/18954#18954 Answer by AH for What is convolution intuitively? AH 2010-03-21T21:04:04Z 2011-06-13T19:15:55Z <p>I want to expand on a special case of Terry's answer which I think is particularly intuitive.</p> <p>Suppose there is a function $f$ that you want to understand, but perhaps it is not smooth. Convolution gives you a way to construct new, possibly nicer functions which approximate $f$.</p> <p>If you let $g$ be a bump function centered at the origin, then the convolution $f*g$ is a new function whose value at $x$ is given by averaging the values of $f$ around $x$. What do we mean exactly by "averaging"? Well, you use $g$ as your measure; translate it over so that it is centered at $x$, and then the integral $$f * g(x) = \int_{\mathbb{R}^n} f(y)g(y - x) dy$$ in the convolution corresponds to the $g$-weighted average of the values of $f$ around $x$ (i.e. in the small ball where $g$ doesn't vanish).</p> <p>The convolution $f*g$ in this case has the advantage that it is much smoother than $f$. Intuitively, this should be not surprising since the value of $f*g(x)$ was gotten by averaging nearby $f$-values of $x$. Furthermore, you can approximate $f$ by smooth(er) things by considering a sequence of convolutions $f*(g_n)$ where $g_n$ is a sequence of bump functions which are more and more concentrated at the origin.</p> <p>If you think of the second function $g$ in the convolution $f*g$ as a measure, then you can think of convolutions as $g$-weighted averages of $f$.</p> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/29729#29729 Answer by Ivan Meir for What is convolution intuitively? Ivan Meir 2010-06-27T20:00:09Z 2010-06-27T20:00:09Z <p>If you convolve an image with a discrete matrix of values - so like a function that is zero outside a few pixles then you can create almost an unlimited number of filtering effects around each point. Fof example you can do some kind of averaging or weighted integration - which looks like blurring as Professor Tao mentions if you use a matrix whose values drop off smoothly, radially from the centre - a bump. You can also compute directional derivatives, look for edges, circles, blobs, steps - basically anything you like. </p> <p>The interpretation in terms of multiplication of Fourier coeficients is interesting and makes applications of the above in reality fast, especially if the filter is fixed, because you can use the Fast Fourier Transform on both images but you only need to update one of them. However I a not sure how intuitive it is!</p> <p>I'm not sure I have added much additional information but I hope this helps anyway,</p> <p>Ivan</p> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/46649#46649 Answer by Michael Hardy for What is convolution intuitively? Michael Hardy 2010-11-19T16:34:19Z 2010-11-19T16:34:19Z <p>Among things that it's good to know about convolution is that the identity element for convolution is the Dirac delta function $\delta$.</p> <p>Another is that if you convolve a function $f$ with $\delta'$, the derivative of the delta function, you get $f'$. Since convolution is associative, that implies that $f'*g = f*g'$.</p> <p>Another is that often the convolution of two functions is as well-behaved as the better-behaved one of the two. If you convolve something with a smooth function, you get a smooth function; if you convolve something with a polynomial, you get a polynomial. In other words, many classes of "well-behaved" functions are ideals in a ring whose multiplication is convolution.</p> <p>So if you convolve $f$ with a smooth approximation to Dirac's delta function, you get a smooth approximation to $f$. Thinking about why that works can probably shed a lot of intuitive light on the nature of convolution.</p> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/67690#67690 Answer by Anixx for What is convolution intuitively? Anixx 2011-06-13T18:13:37Z 2011-06-13T18:13:37Z <p>Algebraic meaning of convolution in analysis can be seen from the following formula:</p> <p>$$\int_{-\infty}^{+\infty} f(x)*g(x)\ dx=\left(\int_{-\infty}^{+\infty} f(x)\right)\left(\int_{-\infty}^{+\infty} g(x)\right)$$</p> <p>So, in short, convolution is the product of integrals.</p> <p>This is also true in discrete calculus where discrete convolution is used when multiplying sums, and in particular n-times repeated convolution is used in binomial theorem to express the power of a binomial.</p> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/67716#67716 Answer by Peter Luthy for What is convolution intuitively? Peter Luthy 2011-06-14T00:55:04Z 2011-06-14T00:55:04Z <p>There is a nice relationship between convolution of probability measures and random walks which is very clear on finite groups. </p> <p>For a particularly concrete example, suppose you are shuffling a deck of cards. You can model this as picking elements of $S_{52}$ according to some probability measure $P$ on $S_{52}$. This generates a Markov chain with transition matrix whose $(s,t)$-th entry is given by $P(ts^{-1})$ --- if I am permitted to abuse notation somewhat, the element $ts^{-1}$ is the shuffle that takes the deck from ordering $s$ to ordering $t$. If one wants to know the transition matrix for two shuffles, this corresponds to the square of the original matrix. One can then check that this new matrix corresponds to constructing the transition matrix generated by $P*P$, that is the matrix whose $(s,t)$-th entry is given by $(P*P)(ts^{-1})$, and in fact $k$ shuffles corresponds to the the $k$-fold convolution of $P$ with itself.</p> <p>Convolving two different probability measures then corresponds to shuffling your deck according to one technique and then a different technique.</p> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/67724#67724 Answer by Paul Pearson for What is convolution intuitively? Paul Pearson 2011-06-14T04:43:39Z 2011-06-14T04:43:39Z <p>Arthur Mattuck gives an interesting lecture on the convolution, its construction, and its applications:</p> <p><a href="http://ocw.mit.edu/courses/mathematics/18-03-differential-equations-spring-2010/video-lectures/lecture-21-convolution-formula/" rel="nofollow">http://ocw.mit.edu/courses/mathematics/18-03-differential-equations-spring-2010/video-lectures/lecture-21-convolution-formula/</a></p> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/86040#86040 Answer by Phil Isett for What is convolution intuitively? Phil Isett 2012-01-18T22:07:49Z 2012-01-18T22:07:49Z <p>I like the answer you gave when you asked the question. More generally, the convolution of two measures $\mu$ and $\nu$ is the pushforward of $\mu \times \nu$ by multiplication. In probability, that means you independently draw from $\mu$ and $\nu$ and add the resulting random vector. It's something that you can visualize to a certain extent if you do think of measures as fuzzy versions of points (like Terry Tao said).</p> <p>One point of view of measures is that they are linear combinations of points (or limits of things you can get from linear combinations of points). If you take this point of view, then convolution is simply the extension of the addition law by linearity to the case of measures.</p> <p>Since you can translate functions as well as measures, you can convolve, say, a probability measure with a function by randomly translating the function, giving the averaged out function $\int f(x-y) d\mu(y)$ which generally looks like a smoothed out version of your function $f$ -- $\mu$ tells you which translations you use and how to average. Again, you can view this as the extension of the operation of translating functions by linearity/continuity to the case of measures.</p> <p>The Lebesgue measure allows you to identify functions with measures, $g \mapsto g(x) dx$, so you can also convolve functions with other functions, but you might think of this operation is a bit less basic.</p> <p>Actually, the process of convolution extends by continuity to more than just measures but also to distributions. For example, you can approximate a tangent vector at $0$ (giving the distribution $u(x) = \sum_i c^i \partial_i \delta_0$) by differences of point masses, so convolution extends to distributions as well, but you can even get differential operators this way (in this example, $u \ast f$ is the derivative of $f$ in the $u$ direction). The technical difference here is that the approximation is only valid when integrated against $C^k$ functions (rather than $C^0$ functions in the case of measures). But the principle is the same -- it's the extension of the addition law by linearity and limits.</p> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/104740#104740 Answer by Steven Gubkin for What is convolution intuitively? Steven Gubkin 2012-08-15T03:17:40Z 2012-08-15T03:17:40Z <p>The fundamental theorem of calculus says that $\frac{d}{dx} \displaystyle \int_a^x f(t)dt = f(x)$. In other words, $f(x) \approx \displaystyle \int_{x-h}^{x+h} \frac{1}{2h} f(t)dt$. Letting $g_h(u) = \frac{1}{2h}$ on the interval $(-h,h)$ and 0 elsewhere, we see by pure algebraic manipulation that $f(x) \approx \displaystyle \int_{-\infty}^\infty g_h(x-t)f(t)dt$. So the fundamental theorem of calculus can very naturally be rephrased in terms of convolution with a bump function. Differentiation under the integral sign immediately gives the differentiation formula for convolutions, and thus that convolutions of two functions are at least as smooth as both factors. Thus finding good smooth approximations to the rectangular bump functions $g_h$ automatically gives us smooth approximations to any integrable function we like, just by convolving against these "smooth molifiers". Pretty cool stuff. As mentioned in other answers they really start to shine when you start thinking about fourier analysis, but that is a another story. If you google "low pass filter" you will find some pretty snazzy applications of the fact that the fourier transform turns convolution into multiplication. </p> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/110762#110762 Answer by iBM for What is convolution intuitively? iBM 2012-10-26T15:19:36Z 2012-10-26T15:19:36Z <p>As far as I understand, in simple words, considering the simple moving average algorithm, when you convolve F with G, then G defines how you are going to do the weightings to get the average. G can be seen as a component for defining the weighting policy.</p> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/110792#110792 Answer by paul garrett for What is convolution intuitively? paul garrett 2012-10-26T23:22:34Z 2012-10-26T23:38:03Z <p>To complement/supplement other answers, it may be worthwhile to note that the question itself blurs two substantially different mechanisms. Namely, there is, first, for any group representation of a topological group $G$ on a topological vector space $V$, an action of compactly-supported continuous functions on $G$ on $V$, by (e.g., Gelfand-Pettis/weak) integrals $f\cdot v=\int_G f(g)\cdot gv\,dg$. It is of some moment to note that this does not depend on $v$ being in any sort of natural function-space. The second point is that $f\cdot (g\cdot v)=(f*g)\cdot v$, where $*$ denotes the convolution. That is, the notion of convolution is externally determined by being what it has to be for (for example) compactly-supported continuous functions to act (associatively) on any representation space.</p> <p>Depending on one's outlook, this may reduce some element of seeming whimsy in "defining" convolution, since, in a larger context, _there_is_no_choice_.</p> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/110793#110793 Answer by Liviu Nicolaescu for What is convolution intuitively? Liviu Nicolaescu 2012-10-27T00:23:21Z 2012-10-27T00:23:21Z <p>Here is my take on this. $\newcommand{\bZ}{\mathbb{Z}}$ $\newcommand{\bR}{\mathbb{R}}$ Discretize the real axis and thing of it as the collection of point $\Lambda_\hbar:=\hbar \bZ$, where $\hbar>0$ is a small number. Then a function $f:\Lambda_\hbar\to \bR$ is determined by its <em>generating function</em>, i.e., the formal power series $\newcommand{\ii}{\boldsymbol{i}}$</p> <p>$$G^\hbar_f(t)=\sum_{n\in\bZ}f(n\hbar)t^n.$$</p> <p>Then</p> <p>$$G^\hbar_{f_0\ast f_1}(t)= G^\hbar_{f_0}(t)\cdot G^\hbar_{f_1}(t).\tag{1}$$</p> <p>Observe that if we set $t=e^{-\ii\xi \hbar}$, then</p> <p>$$G^\hbar_f(t)=\sum_{x\in\Lambda_\hbar} f(x) e^{-\ii \xi x}.$$</p> <p>Moreover</p> <p>$$\hbar G^\hbar_f(e^{-\ii\xi \hbar})=\sum _{n\in \bZ} \hbar f(n\hbar) e^{-\ii\xi(n\hbar)}, \tag{2}$$</p> <p>and the expression in the right hand sum is a "Riemann sum" approximating</p> <p>$$\int_{\bR} f(x)^{-\ii\xi x} dx.$$</p> <p>Above we recognize the Fourier transform of $f$. If we let $\hbar\to 0$ in (\ref{2}) and we use (\ref{1}) we obtain the wellknown fact that the Fourier transform maps the convolution to the usual pointwise product of functions. (The fact that this rather careless passing to the limit can be rigorous is what the Poisson formula is all about.)</p> <p>The above argument shows that we can regard $\hbar G_f^\hbar(1)$ as an approximation for $\int_{\bR} f(x) dx$.</p> <p>Denote by $\delta(x)$ the Delta function 9concentrated at $0$. The Delta function concentrated at $x_0$ is then $\delta(x-x_0)$. What could be the generating function of $\delta(x)$, $G\delta^\hbar$? First, we know that $\delta(x)=0$, $\forall x\neq 0$ so that</p> <p>$$G_\delta^\hbar(t) =ct^0=c.$$</p> <p>The constant $c$ can be determined from the equality </p> <p>$$1= \int_{\bR} \delta(x) dx=\hbar G_\delta^\hbar(1)=\hbar c$$</p> <p>Hence $\hbar G_\delta^\hbar(1)=1$. Similarly</p> <p>$$G^\hbar_{\delta(\cdot-n\hbar)} =\frac{1}{\hbar} t^n.$$</p> <p>Putting together all of the above we obtain an equivalemt description for the generating functon af a function $f:\Lambda_\hbar\to\bR$. More precisely</p> <p>$$G_f(t)=\hbar\sum_{\lambda\in\Lambda_\hbar}f(\lambda) G_{\delta(\cdot-\lambda)}(t).$$</p> <p>The last equality suggests an interpretation for the generating function as an algebraic encoding of the fact that $f:\Lambda_\hbar\to\bR$ is a superposition of $\delta$ functions concentrated along the points of the lattice $\Lambda_\hbar$.</p>