14 ms·

Convolution Is Fancy Multiplication

397 points by ubac 6y ago

adamnemecek 6y ago
I think that calling it outer product makes more sense https://arxiv.org/pdf/1905.01289v1.pdf https://arxiv.org/pdf/1905.01289v1.pdf.
- Tomminn 6y ago
  The type signature of the outer product is not correct. We are mapping two functions to a function in the same domain. Convolution is neither a valid example of an inner product or an outer product. No basic geometric operation on vectors has the correct type signature and axioms for convolution to be interpreted as a generalized "x". What we'd be looking for is a billinear mapping of vectors to vectors, and complex number style multiplication in R^2, or cross product multiplication in R^3 or R^7 are the only real candidates in that category unless we start interpreting functions as matrices.
  - adamnemecek 6y ago
    Ok, exterior product.
    - Tomminn 6y ago
      The exterior product also exists in a different vector space to its factors.
brockwhittaker 6y ago
As someone who's forgotten almost all college calculus, this was incredibly well written and understandable!
hprotagonist 6y ago
"look it's just autocorrelation but upside down and backwards" is ... closer to true than it really ought to be.
- adamnemecek 6y ago
  They are adjoints. http://www.reproducibility.org/RSF/book/gee/ajt/paper_html/index.html http://www.reproducibility.org/RSF/book/gee/ajt/paper_html/i... I have written something on adjoints, they are literally everywhere https://github.com/adamnemecek/adjoint https://github.com/adamnemecek/adjoint
- bonoboTP 6y ago
  And you flip it to get nice properties like commutativity and associativity which correlation doesn't have (it almost has them, just that small flip is missing).
pmiller2 6y ago
That's because convolution literally is a type of product on the space of integrable functions: https://en.wikipedia.org/wiki/Convolution#Algebraic_properties https://en.wikipedia.org/wiki/Convolution#Algebraic_properti...
- Laakeri 6y ago
  Ah, that explains it perfectly!
  - pmiller2 6y ago
    I'm not sure if this is a sarcastic reply or not, but, it kinda does. Fubini's theorem is a hell of a drug.
    - nielsbot 6y ago
      depends on the audience I think
      - pmiller2 6y ago
        Exactly why I wasn't sure. :P
      - rectang 6y ago
        Math entries in Wikipedia generally favor completeness and correctness over clarity, which makes them of limited use for many users. In order to explain something simply, you usually have to lie a little bit — but I speculate that those little lies bother the contributors to mathematical Wikipedia articles a great deal. So they correct those little lies, making the articles more accurate but less useful for many of us.
        pmiller2 6y ago
        In this instance, though, you don't really have to lie, but a lot of the hard work is fobbed off to Fubini's theorem.
sriku 6y ago
Convolution is digit-based multiplication, so why not start with that? 100101 * 23 = 2302323. If you defer the carry over to the end, the digit-based steps we do is convolution. That said, giving lots of examples like those in the article is useful. Next up looking at multiplying two polynomials in a single variable. Edit: changed digit-wise to digit-based to make it clear that I'm not asking to multiply corresponding digits.
- jaggirs 6y ago
  Woha This is cool. It literally is the same, if you use base-infinity digits (not binary, or decimal, but infinity-ary?). How do you multiply two polynomials with a single variable?
  - rualca 6y ago
    > This is cool I don't agree the example has anything to do with convolution. The example is explained with plain old primary school multiplication. 100101 * 23 = (100000+100+1)*23 = 2300000+2300+23 There isn't any fantastic property, only cherry-picked number which works as decimal left-shifts. Convolution is not a number. Convolution is an operator that outputs a function.
    - Tomminn 6y ago
      The parents point is that when you do the primary school multiplication algorithm, you are actually performing a discrete convolution.
      - rualca 6y ago
        You really aren't. That assertion is like commenting that elementary arithmetics is discrete signal analysis because 1+1=2, which happens to match the amplitude of a resonance of a normalized vibration mode. It isn't. It's a cherry picked example. A broken clock which coincides with the current time.
        6y ago
skybrian 6y ago
The first example is explained a bit too quickly, so it’s not that intuitive. It seems this hospital has one patient the first day, two on the second, three on the third, and so on. I guess that’s a “schedule” but it seems more like a history of what happened? It’s not a “list of patients” either, which had me thinking they were patient ids. A better phrase would be a “list of patient counts”.
phaker 6y ago
And multiplication is a fancy convolution (with carries). Fast convolution algorithms use FFT and run in O(n log n) time, which is why fast multiplication algorithms are based on FFT and why everyone was looking for O(n log n) one, which was found like a year ago. (Though from what i can tell in "Faster Convolutions" section the article claims you can easily build O(n log n) multiplication using FFT which doesn't work as it ignores carries)
- nickcw 6y ago
  You can build a O(n log n) multiplication with FFT based convolutions. The trick is to only put as many bits into each number as are guaranteed not to overflow. So if the convolution is n long and you put B bits in to each "digit" then the output needs to be able to hold log(n)+2*B bits. So if your convolution is done with double precision with 56 bits of precision and n = 1 million, log(n) = 20 so you put (56 -20)/2 = 18 bits into each "digit". You do your convolution, and ripple the carries at the end. This is the way Prime95 does its maths, though it uses a IBDWT which through a bit of extra maths magic halves the length of the FFT needed. While it is rippling the carries at the end it checks to see if each number is pretty nearly an integer - if it isn't them something has gone wrong and it blows up with "FATAL ERROR: Rounding was 0.5, expected less than 0.4".
  - xiphias2 6y ago
    Good luck trying to explain this 43 paper the parent comment was refering to in a HN comment: https://hal.archives-ouvertes.fr/hal-02070778/document https://hal.archives-ouvertes.fr/hal-02070778/document Basically, you can't. It's the overflows that make it so hard. It's complex, even though we all had the intuition that it should be done (and it should be simple to do)
  - SamReidHughes 6y ago
    This requires padding out an O(n)-digit number to memory size O(n log n), with addition operations of numbers with log(n) bits deemed to take O(1) time. If this is allowed by your model of computation, then you could use this magical O(1) addition to to implement multiplication in O(n).
kazinator 6y ago
Convolution is a correlation with a reversed signal. Correlation is a generalized dot product: multiplying corresponding pairs of values from two signals, and then adding the factors together. The result is zero if the signals are orthogonal (like the dot product of two vectors in 2D or 3D that are at 90 degrees). The intuition behind the reversed signal comes from processing in the time domain. There are application in which we convolve a new signal with a segment based on a captured historic signal. That function is reversed so that the newest sample from the new signal correlates with the least recently captured sample in the historic signal. For instance, we can use an impulse signal (like a clap) to capture the echoes from an acoustic space. That signal can then be convolved with audio data in order to give it a reverberation similar to what would be produced by that acoustic space. The captured impulse response has to be reversed, because echoes come in reverse. In the impulse capture, the longest echo is found on the far right. When we apply the impulse to simulate the echo, it has to be on he far left, because it has to correlate with an old sample of he input. E.g. if we are at t = 0, and want to hear the 500 ms echo, that echo corresponds to a past sound sample that is now at t = -500. When are capturing the impulse response, then we issue the gunshot or clap at t = 0, and the 500 ms echo comes at t = 500. The earliest reflections have to apply to more recent signal, but they are based on the least recently captured data.
- deepsun 6y ago
  > echoes come in reverse I don't think it's true, cannot even imagine how it's possible, especially for long signals, like the whole song. Any links to read about.
  - convolvatron 6y ago
    imagine you are able to see the wave as it hits a wall and reflects. the reverse signal is 180 degrees out of phase with respect to the forward.
    - rualca 6y ago
      You should be more careful and precise in your attempts to describe these things. Inverting the phase of a signal is entirely different than inverting the signal. Time-reversed signals are not the same as phase-reversed signals.
m-hilgendorf 6y ago
I was introduced to convolution in a undergraduate signals/systems course in continuous time where it's basically magic that you memorize to pass your course. I think a better introduction would be through discrete convolution by reexamining polynomial multiplication (which is convolution through a different lens - the coefficients of the product of two polynomials is the convolution of their coefficients). That serves as a less magical introduction to the operator. You can then point out that the polynomials whose coefficients one convolves can be considered power series, which has a nice interlude into the Z transform and its usefulness as an analytical tool when working with convolutions (and then on to the Fourier transform, etc).
- bigmanwalter 6y ago
  My fist taste of convolution was in a discrete signals class while studying for a B.Eng. in Electrical Engineering. You’re right it was an excellent approach!
- defanor 6y ago
  I was rather surprised that it wasn't discrete convolution in the article, after the hospital analogy. Perhaps even with finite summation first, and generalized afterwards; otherwise there's a bit of a leap.
Twisol 6y ago
In "Part 2: The Calculus Definition", f and g switch roles a couple times. Before the colorized formula, "f" is described as "the plan to use", and "g" as "the list of inputs"; and after the colorized formula, the plan is referred to as a "kernel"; but in the formula itself, "g" is the inputs and "f" is the kernel. I realize convolution is commutative ("Part 3"), but it tripped me up a little as I tried to track the narrative.
spekcular 6y ago
I also enjoy Terence Tao's explanation [0]: > 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. > 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. [0] https://mathoverflow.net/questions/5892/what-is-convolution-intuitively https://mathoverflow.net/questions/5892/what-is-convolution-...
- nabla9 6y ago
  Tao's explanation seems to be the deepest one so far. Understanding convolution different contexts: geometry, vector algebra, statistics, signal progressing, control theory, functional analysis .. etc. just deepens the understanding. Instead of finding one definition and then seeing everything trough it, one should try to find how different viewpoints are the same and learn to switch.
- salty_biscuits 6y ago
  I might be wrong (so happy to be corrected by a native speaker) but I liked when I heard that the German word for convolution is "faltung" which translates to "folding". This is a much nicer word to metaphorically understand the operation. Maybe it still confuses the hell out of German undergrads though?
  - dasudasu 6y ago
    The etymology is the same in English. To convolve : to roll together : writhe. Convolution : a form or shape that is folded in curved or tortuous windings.
titanomachy 6y ago
This is great! Convolution over arrays is much easier for me to grasp intuitively, and the extension to functions over the reals is straightforward with that intuition. Everyone should introduce convolution that way.
Tomminn 6y ago
Okay. This is decent. I do like the idea of "fancy multiplications" because I do think you should understand convolution as well as you understand multiplication. But I still feel like this kinda obscures and confuses the origin of the reversal.* If you don't understand the convolution formula instinctively, read this comment enough times till you do. The point is this. -We have a function originBangSound(t) that maps the effect at (t) of an impulse or "bang" coming from the origin (t=0). -We have a function bangWeights(t), which measures the distribution of impulses or "bangs" over time. -The question is: how do we get the total allBangSounds(t)? Simple: We make every point in time the origin, and add all the results together. Let's call (tau) the current origin. The size of the bang at this origin is bangWeights(tau). The size of the sound at (t) which is coming from this origin is originBangSound(t- tau), since we care about the position of (t) relative to the current origin (tau). Adding them up leads to an integral in the continuous case. allBangSounds(t) = \integral bangWeights(tau)*originBangSound(t-tau) d(tau) The point is this. Don't think of it as a flip. Think of (tau) as defining the origin point for a particular "bang". Here's a nice sanity check: if (tau) is larger than (t), (or equivalently, (t-tau)<0) then do you expect to hear its bang? Ofcourse not. The bang hasn't happened yet. So unless its bang travels backward in time (which definitely does happen in spatial convolutions!) you ain't hearing it. _____________________________ *Come to think of it, this is a very useful pun. When you think to yourself "what's the origin of the reversal again?", just remember, the moving the origin is the origin of the reversal.
rotskoff 6y ago
Convolution is in fact multiplication in Fourier space (this is the convolution theorem [1]) which says that Fourier transforms convert convolutions to products. 1. https://en.wikipedia.org/wiki/Convolution_theorem https://en.wikipedia.org/wiki/Convolution_theorem
scythe 6y ago
Suppose f and g are normalized distributions and consider the function f(x)·g(y). If we "collapse" (integrate) in the y-dimension we recover f(x). If we collapse in the x-dimension we recover g(y). But if we collapse along the lines x+y = v, we obtain the convolution f⋆g(v). This picture is a little more advanced, but it makes clear two key properties of convolution: symmetry (commutativity) and the fact that the total integral of the convolution is the total integral of f(x)·g(y).
- bitdizzy 6y ago
  This generalizes to convolution in an arbitrary group (and even groupoid, and even category), not necessarily one that is commutative like the reals or integers are. For group convolution over a group G, the functions take values in the complex numbers and have domain the elements of G. The value of the convolution of two such functions f and g at a point c (a group element) is computed by taking the sums f(a)*g(b) where ab = c. This has applications in quantum mechanics where non-commutativity plays a prominent role.
- dsagal 6y ago
  This is really cool. The original post is great in putting it in terms of a concrete example. It would be cool (challenging but possible) to have a 3D visualization of collapsing f(x)·g(y) like you describe in the context of that same example. It's certainly a useful mental model.
- vlasev 6y ago
  Woah this is really cool and an awesome point of view. Collapsing along the x-axis is just a projection along the vector [1, 0, 0] onto the the y-z plane defined by it and the origin. Then if you project along the vector [1, 1, 0] onto the plane defined by [1, -1, 0] and [0, 0, 1], you get the convolution.
onecommentman 6y ago
Convolution is such a core concept. In my era, it was a college sophomore/junior sort of thing. Is it a standard high school topic for AP math types in high school nowadays? If not, why not? There are a few topics like that, for which I’d gladly give up high school teaching (or learning) L’Hôpital’s rule for.
- bonoboTP 6y ago
  I think it first comes up in signal processing courses at university (or nowadays in deep learning courses, which makes people think of convolution as some mysterious deep learning specific magic sauce buzzword).
stopachka 6y ago
Amazing work! Enjoyed this a bunch.
westurner 6y ago
FWIW, (bounded) Conway's Game of Life can be efficiently implemented as a convolution of the board state: https://gist.github.com/mikelane/89c580b7764f04cf73b32bf4e94fd3a3#file-game_of_life-py-L113 https://gist.github.com/mikelane/89c580b7764f04cf73b32bf4e94...
uoaei 6y ago
Convolution is fancy linear regression
ur-whale 6y ago
Convolution is just a weighted average, something you learn when you're in primary school. Not sure why all the hoopla.
- solidasparagus 6y ago
  You learned about convolution when you were in primary school?
zant 6y ago
There's also a good one made by Grant Sanderson from 3blue1brown. This video was the first time I was introduced to the concept and had no trouble following it: https://www.youtube.com/watch?v=8rrHTtUzyZA https://www.youtube.com/watch?v=8rrHTtUzyZA
anonytrary 6y ago
f(x)g(x-t)dt Integrating over t can be visualized as sliding g over f over the range of t. Result is a function of x as t has been integrated out. It all made sense to me when I thought of it as sliding one function over another fixed function.
dwrodri 6y ago
I'm a firm believer that resources which raise the bar for math and computing education are huge catalysts for innovation. The fact that resources like BetterExplained, Paul's Math Notes, 3Blue1Brown's YouTube Channel, Ben Eater's YouTube channel, and the entire body of high quality MOOCs are just available for free over the Internet is probably one of my favorite accomplishments of the human race in the 21st century. While researchers, inventors, startup founders, and all other types of entrepreneurs are pushing the envelope on what's possible, there are literally thousands of creators and educators who are doing their best to bring some of that knowledge to the common man. My own experience with academia has lead me to believe that there problems that are truly difficult and complex, but there are also problems which are described as difficult because so many people were exposed to the topic through a resource (typically another person) who had little experience (or interest) in effectively teaching the subject.
- parksy 6y ago
  Definitely agree - I struggled beyond basic integration in High School, and my "why" and "what is it" type questions about calculus were met with annoyed "read the book" replies and young me lost interest in higher maths at a time when my mind was more plastic. As an adult having these personalities enthusiastically breaking down the fundamentals and using analogies to help cement the concepts intuitively has been a taste of what I imagine having a brilliant and engaging math professor would be like.
  - jhoechtl 6y ago
    For me it clicked once it understood that integration is the area "beyond" the "curve".
- Barrin92 6y ago
  It's a good goal from just a humanistic standpoint and because learning should be recreational but from an innovation standpoint it's honestly likely overrated. Innovation is the result of very particular institutions and resources being coordinated and people networking and clustering tightly, which is why, despite incredibly dispersion of knowledge over the internet, innovation and VC money actually still is so geographically concentrated. I think these online learning resources are good but the expectations should be correct, they're not tools to kickstart innovation, which is much more tacit and reliant on close interaction between people rather than knowledge.
signaru 6y ago
working with image processing makes convolution easily intuitive. you can get a "feel" of what the math is doing by looking what's happening with the images. while blurring is a common example (convolve a Gaussian function with the image), edge detection and other image operations are just a matter of changing the convolved signal (or kernel). in a simplified model, blurry photos due to poor lenses also share the same principle (the lens cannot form a perfect point, that imperfect point is effectively what is convolved). the same can be said for audio and other 1d data, but images are more visual.
syntaxing 6y ago
My diffeq professor explained it as the fifth form of arithmetic (first four being addition, subtraction, multiplication, and division). This fifth form is unique because you sweep two functions relative to time and each other. To be honest, I still don't fully grasp the concept and I just use it as a mathematical tool. I need a 3blue1brown video to explain this to me so I can have an "aha!" moment like I had in his linear algebra videos.
- vlasev 6y ago
  I'm sure you've seen this elsewhere in the comments, but multiply two polynomials to see a discrete convolution in action! Here your functions would be discrete.
imvetri 6y ago
And multiplication is a fancy addition
- deleted 6y ago
  [deleted]
- imvetri 6y ago
  Addition is a repetition of vector
  - imvetri 6y ago
    Vector is displacement of a point
midjji 6y ago
Just because its funny, here is the obligatory reminder that deep convolutional networks are actually implemented as correlation, not convolution. True, its just the lack of mirroring that differs, which is a linear operation and hence, the network can be considered too have learned the mirrored kernels, but it matters for initialization(bilinear init for conv^T sampling is still incorrectly mirrored in pytorch), and every time someone has put the images of the kernels in a paper its better than even odds they show the correlation, not convolution kernls.
brettermeier 6y ago
That "Colorized Math" idea is pretty great! Thanks for let me stumbling over the link in this article.
leoedin 6y ago
There's a brilliant (and free) book called The Scientist and Engineer's Guide to Digital Signal Processing which covers this and other DSP topics. It's very readable and clear - I found it super useful in understanding DSP and the maths surrounding it. Most of the time the actual stuff happening is quite simple, but if you're not living and breathing mathematical notation the conventional explanations can be quite impenetrable. This book puts everything out in code, so you can follow the steps and truly understand what's happening. http://www.dspguide.com/ http://www.dspguide.com/
- spacechild1 6y ago
  I can second your recommendation! This book helped me to finally grok convolution and many other things.
JekLod10 6y ago
I could not understand convolution in the beginning partly because the book sucked and my professor was derisive with bad middle eastern accent. I wish resources like these existed back in the 90's so we would not waste time learning stuff.
hatsunearu 6y ago
So this is just discrete convolution but continuous time convolution AFAIK has no intuitive explanation. The general idea is there is a sense of taking mathematical operations as having not just numbers and variables and outputing another number or variable... but that operations can take any number of anything and output any number of anything. The Fourier Transform takes in a function and outputs another function, which you can put meaning on it or you can just "nod and continue" (which is often easier instead of trying to put some words on abstract concepts). Some "ideas" you can use to analyze the situation are concepts learned in things like linear algebra like abstract vector spaces, basis, eigen-whatever... and so on. In the case of the continuous time convolution, it just turns out there is a magical thing associated with something called a Dirac Delta function with certain properties that are important for various things in controls engineering. Kinda feels like a piece of turd that refuses to evacuate but I just stopped caring about "intuitive" explanations.
sunstone 6y ago
All mathematics is abstractions of addition.

397 points by ubac 6y ago

I think that calling it outer product makes more sense https://arxiv.org/pdf/1905.01289v1.pdf https://arxiv.org/pdf/1905.01289v1.pdf.

Tomminn 6y ago
The type signature of the outer product is not correct. We are mapping two functions to a function in the same domain. Convolution is neither a valid example of an inner product or an outer product. No basic geometric operation on vectors has the correct type signature and axioms for convolution to be interpreted as a generalized "x". What we'd be looking for is a billinear mapping of vectors to vectors, and complex number style multiplication in R^2, or cross product multiplication in R^3 or R^7 are the only real candidates in that category unless we start interpreting functions as matrices.
- adamnemecek 6y ago
  Ok, exterior product.
  - Tomminn 6y ago
    The exterior product also exists in a different vector space to its factors.

brockwhittaker 6y ago

As someone who's forgotten almost all college calculus, this was incredibly well written and understandable!

hprotagonist 6y ago

"look it's just autocorrelation but upside down and backwards" is ... closer to true than it really ought to be.

adamnemecek 6y ago
They are adjoints. http://www.reproducibility.org/RSF/book/gee/ajt/paper_html/index.html http://www.reproducibility.org/RSF/book/gee/ajt/paper_html/i... I have written something on adjoints, they are literally everywhere https://github.com/adamnemecek/adjoint https://github.com/adamnemecek/adjoint
bonoboTP 6y ago
And you flip it to get nice properties like commutativity and associativity which correlation doesn't have (it almost has them, just that small flip is missing).

pmiller2 6y ago

That's because convolution literally is a type of product on the space of integrable functions: https://en.wikipedia.org/wiki/Convolution#Algebraic_properties https://en.wikipedia.org/wiki/Convolution#Algebraic_properti...

Laakeri 6y ago
Ah, that explains it perfectly!
- pmiller2 6y ago
  I'm not sure if this is a sarcastic reply or not, but, it kinda does. Fubini's theorem is a hell of a drug.
  - nielsbot 6y ago
    depends on the audience I think
    - pmiller2 6y ago
      Exactly why I wasn't sure. :P
    - rectang 6y ago
      Math entries in Wikipedia generally favor completeness and correctness over clarity, which makes them of limited use for many users. In order to explain something simply, you usually have to lie a little bit — but I speculate that those little lies bother the contributors to mathematical Wikipedia articles a great deal. So they correct those little lies, making the articles more accurate but less useful for many of us.
      - pmiller2 6y ago
        In this instance, though, you don't really have to lie, but a lot of the hard work is fobbed off to Fubini's theorem.

sriku 6y ago

Convolution is digit-based multiplication, so why not start with that? 100101 * 23 = 2302323. If you defer the carry over to the end, the digit-based steps we do is convolution. That said, giving lots of examples like those in the article is useful. Next up looking at multiplying two polynomials in a single variable. Edit: changed digit-wise to digit-based to make it clear that I'm not asking to multiply corresponding digits.

jaggirs 6y ago
Woha This is cool. It literally is the same, if you use base-infinity digits (not binary, or decimal, but infinity-ary?). How do you multiply two polynomials with a single variable?
- rualca 6y ago
  > This is cool I don't agree the example has anything to do with convolution. The example is explained with plain old primary school multiplication. 100101 * 23 = (100000+100+1)*23 = 2300000+2300+23 There isn't any fantastic property, only cherry-picked number which works as decimal left-shifts. Convolution is not a number. Convolution is an operator that outputs a function.
  - Tomminn 6y ago
    The parents point is that when you do the primary school multiplication algorithm, you are actually performing a discrete convolution.
    - rualca 6y ago
      You really aren't. That assertion is like commenting that elementary arithmetics is discrete signal analysis because 1+1=2, which happens to match the amplitude of a resonance of a normalized vibration mode. It isn't. It's a cherry picked example. A broken clock which coincides with the current time.
      - 6y ago

skybrian 6y ago

The first example is explained a bit too quickly, so it’s not that intuitive. It seems this hospital has one patient the first day, two on the second, three on the third, and so on. I guess that’s a “schedule” but it seems more like a history of what happened? It’s not a “list of patients” either, which had me thinking they were patient ids. A better phrase would be a “list of patient counts”.

phaker 6y ago

And multiplication is a fancy convolution (with carries). Fast convolution algorithms use FFT and run in O(n log n) time, which is why fast multiplication algorithms are based on FFT and why everyone was looking for O(n log n) one, which was found like a year ago. (Though from what i can tell in "Faster Convolutions" section the article claims you can easily build O(n log n) multiplication using FFT which doesn't work as it ignores carries)

nickcw 6y ago
You can build a O(n log n) multiplication with FFT based convolutions. The trick is to only put as many bits into each number as are guaranteed not to overflow. So if the convolution is n long and you put B bits in to each "digit" then the output needs to be able to hold log(n)+2*B bits. So if your convolution is done with double precision with 56 bits of precision and n = 1 million, log(n) = 20 so you put (56 -20)/2 = 18 bits into each "digit". You do your convolution, and ripple the carries at the end. This is the way Prime95 does its maths, though it uses a IBDWT which through a bit of extra maths magic halves the length of the FFT needed. While it is rippling the carries at the end it checks to see if each number is pretty nearly an integer - if it isn't them something has gone wrong and it blows up with "FATAL ERROR: Rounding was 0.5, expected less than 0.4".
- xiphias2 6y ago
  Good luck trying to explain this 43 paper the parent comment was refering to in a HN comment: https://hal.archives-ouvertes.fr/hal-02070778/document https://hal.archives-ouvertes.fr/hal-02070778/document Basically, you can't. It's the overflows that make it so hard. It's complex, even though we all had the intuition that it should be done (and it should be simple to do)
- SamReidHughes 6y ago
  This requires padding out an O(n)-digit number to memory size O(n log n), with addition operations of numbers with log(n) bits deemed to take O(1) time. If this is allowed by your model of computation, then you could use this magical O(1) addition to to implement multiplication in O(n).

kazinator 6y ago

Convolution is a correlation with a reversed signal. Correlation is a generalized dot product: multiplying corresponding pairs of values from two signals, and then adding the factors together. The result is zero if the signals are orthogonal (like the dot product of two vectors in 2D or 3D that are at 90 degrees). The intuition behind the reversed signal comes from processing in the time domain. There are application in which we convolve a new signal with a segment based on a captured historic signal. That function is reversed so that the newest sample from the new signal correlates with the least recently captured sample in the historic signal. For instance, we can use an impulse signal (like a clap) to capture the echoes from an acoustic space. That signal can then be convolved with audio data in order to give it a reverberation similar to what would be produced by that acoustic space. The captured impulse response has to be reversed, because echoes come in reverse. In the impulse capture, the longest echo is found on the far right. When we apply the impulse to simulate the echo, it has to be on he far left, because it has to correlate with an old sample of he input. E.g. if we are at t = 0, and want to hear the 500 ms echo, that echo corresponds to a past sound sample that is now at t = -500. When are capturing the impulse response, then we issue the gunshot or clap at t = 0, and the 500 ms echo comes at t = 500. The earliest reflections have to apply to more recent signal, but they are based on the least recently captured data.

deepsun 6y ago
> echoes come in reverse I don't think it's true, cannot even imagine how it's possible, especially for long signals, like the whole song. Any links to read about.
- convolvatron 6y ago
  imagine you are able to see the wave as it hits a wall and reflects. the reverse signal is 180 degrees out of phase with respect to the forward.
  - rualca 6y ago
    You should be more careful and precise in your attempts to describe these things. Inverting the phase of a signal is entirely different than inverting the signal. Time-reversed signals are not the same as phase-reversed signals.

m-hilgendorf 6y ago

I was introduced to convolution in a undergraduate signals/systems course in continuous time where it's basically magic that you memorize to pass your course. I think a better introduction would be through discrete convolution by reexamining polynomial multiplication (which is convolution through a different lens - the coefficients of the product of two polynomials is the convolution of their coefficients). That serves as a less magical introduction to the operator. You can then point out that the polynomials whose coefficients one convolves can be considered power series, which has a nice interlude into the Z transform and its usefulness as an analytical tool when working with convolutions (and then on to the Fourier transform, etc).

bigmanwalter 6y ago
My fist taste of convolution was in a discrete signals class while studying for a B.Eng. in Electrical Engineering. You’re right it was an excellent approach!
defanor 6y ago
I was rather surprised that it wasn't discrete convolution in the article, after the hospital analogy. Perhaps even with finite summation first, and generalized afterwards; otherwise there's a bit of a leap.

Twisol 6y ago

In "Part 2: The Calculus Definition", f and g switch roles a couple times. Before the colorized formula, "f" is described as "the plan to use", and "g" as "the list of inputs"; and after the colorized formula, the plan is referred to as a "kernel"; but in the formula itself, "g" is the inputs and "f" is the kernel. I realize convolution is commutative ("Part 3"), but it tripped me up a little as I tried to track the narrative.

spekcular 6y ago

I also enjoy Terence Tao's explanation [0]: > 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. > 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. [0] https://mathoverflow.net/questions/5892/what-is-convolution-intuitively https://mathoverflow.net/questions/5892/what-is-convolution-...

nabla9 6y ago
Tao's explanation seems to be the deepest one so far. Understanding convolution different contexts: geometry, vector algebra, statistics, signal progressing, control theory, functional analysis .. etc. just deepens the understanding. Instead of finding one definition and then seeing everything trough it, one should try to find how different viewpoints are the same and learn to switch.
salty_biscuits 6y ago
I might be wrong (so happy to be corrected by a native speaker) but I liked when I heard that the German word for convolution is "faltung" which translates to "folding". This is a much nicer word to metaphorically understand the operation. Maybe it still confuses the hell out of German undergrads though?
- dasudasu 6y ago
  The etymology is the same in English. To convolve : to roll together : writhe. Convolution : a form or shape that is folded in curved or tortuous windings.

titanomachy 6y ago

This is great! Convolution over arrays is much easier for me to grasp intuitively, and the extension to functions over the reals is straightforward with that intuition. Everyone should introduce convolution that way.

Tomminn 6y ago

Okay. This is decent. I do like the idea of "fancy multiplications" because I do think you should understand convolution as well as you understand multiplication. But I still feel like this kinda obscures and confuses the origin of the reversal.* If you don't understand the convolution formula instinctively, read this comment enough times till you do. The point is this. -We have a function originBangSound(t) that maps the effect at (t) of an impulse or "bang" coming from the origin (t=0). -We have a function bangWeights(t), which measures the distribution of impulses or "bangs" over time. -The question is: how do we get the total allBangSounds(t)? Simple: We make every point in time the origin, and add all the results together. Let's call (tau) the current origin. The size of the bang at this origin is bangWeights(tau). The size of the sound at (t) which is coming from this origin is originBangSound(t- tau), since we care about the position of (t) relative to the current origin (tau). Adding them up leads to an integral in the continuous case. allBangSounds(t) = \integral bangWeights(tau)*originBangSound(t-tau) d(tau) The point is this. Don't think of it as a flip. Think of (tau) as defining the origin point for a particular "bang". Here's a nice sanity check: if (tau) is larger than (t), (or equivalently, (t-tau)<0) then do you expect to hear its bang? Ofcourse not. The bang hasn't happened yet. So unless its bang travels backward in time (which definitely does happen in spatial convolutions!) you ain't hearing it. _____________________________ *Come to think of it, this is a very useful pun. When you think to yourself "what's the origin of the reversal again?", just remember, the moving the origin is the origin of the reversal.

rotskoff 6y ago

Convolution is in fact multiplication in Fourier space (this is the convolution theorem [1]) which says that Fourier transforms convert convolutions to products. 1. https://en.wikipedia.org/wiki/Convolution_theorem https://en.wikipedia.org/wiki/Convolution_theorem

scythe 6y ago

Suppose f and g are normalized distributions and consider the function f(x)·g(y). If we "collapse" (integrate) in the y-dimension we recover f(x). If we collapse in the x-dimension we recover g(y). But if we collapse along the lines x+y = v, we obtain the convolution f⋆g(v). This picture is a little more advanced, but it makes clear two key properties of convolution: symmetry (commutativity) and the fact that the total integral of the convolution is the total integral of f(x)·g(y).

bitdizzy 6y ago
This generalizes to convolution in an arbitrary group (and even groupoid, and even category), not necessarily one that is commutative like the reals or integers are. For group convolution over a group G, the functions take values in the complex numbers and have domain the elements of G. The value of the convolution of two such functions f and g at a point c (a group element) is computed by taking the sums f(a)*g(b) where ab = c. This has applications in quantum mechanics where non-commutativity plays a prominent role.
dsagal 6y ago
This is really cool. The original post is great in putting it in terms of a concrete example. It would be cool (challenging but possible) to have a 3D visualization of collapsing f(x)·g(y) like you describe in the context of that same example. It's certainly a useful mental model.
vlasev 6y ago
Woah this is really cool and an awesome point of view. Collapsing along the x-axis is just a projection along the vector [1, 0, 0] onto the the y-z plane defined by it and the origin. Then if you project along the vector [1, 1, 0] onto the plane defined by [1, -1, 0] and [0, 0, 1], you get the convolution.

onecommentman 6y ago

Convolution is such a core concept. In my era, it was a college sophomore/junior sort of thing. Is it a standard high school topic for AP math types in high school nowadays? If not, why not? There are a few topics like that, for which I’d gladly give up high school teaching (or learning) L’Hôpital’s rule for.

bonoboTP 6y ago
I think it first comes up in signal processing courses at university (or nowadays in deep learning courses, which makes people think of convolution as some mysterious deep learning specific magic sauce buzzword).

stopachka 6y ago

Amazing work! Enjoyed this a bunch.

westurner 6y ago

FWIW, (bounded) Conway's Game of Life can be efficiently implemented as a convolution of the board state: https://gist.github.com/mikelane/89c580b7764f04cf73b32bf4e94fd3a3#file-game_of_life-py-L113 https://gist.github.com/mikelane/89c580b7764f04cf73b32bf4e94...

uoaei 6y ago

Convolution is fancy linear regression

ur-whale 6y ago

Convolution is just a weighted average, something you learn when you're in primary school. Not sure why all the hoopla.

solidasparagus 6y ago
You learned about convolution when you were in primary school?

zant 6y ago

There's also a good one made by Grant Sanderson from 3blue1brown. This video was the first time I was introduced to the concept and had no trouble following it: https://www.youtube.com/watch?v=8rrHTtUzyZA https://www.youtube.com/watch?v=8rrHTtUzyZA

anonytrary 6y ago

f(x)g(x-t)dt Integrating over t can be visualized as sliding g over f over the range of t. Result is a function of x as t has been integrated out. It all made sense to me when I thought of it as sliding one function over another fixed function.

dwrodri 6y ago

I'm a firm believer that resources which raise the bar for math and computing education are huge catalysts for innovation. The fact that resources like BetterExplained, Paul's Math Notes, 3Blue1Brown's YouTube Channel, Ben Eater's YouTube channel, and the entire body of high quality MOOCs are just available for free over the Internet is probably one of my favorite accomplishments of the human race in the 21st century. While researchers, inventors, startup founders, and all other types of entrepreneurs are pushing the envelope on what's possible, there are literally thousands of creators and educators who are doing their best to bring some of that knowledge to the common man. My own experience with academia has lead me to believe that there problems that are truly difficult and complex, but there are also problems which are described as difficult because so many people were exposed to the topic through a resource (typically another person) who had little experience (or interest) in effectively teaching the subject.

parksy 6y ago
Definitely agree - I struggled beyond basic integration in High School, and my "why" and "what is it" type questions about calculus were met with annoyed "read the book" replies and young me lost interest in higher maths at a time when my mind was more plastic. As an adult having these personalities enthusiastically breaking down the fundamentals and using analogies to help cement the concepts intuitively has been a taste of what I imagine having a brilliant and engaging math professor would be like.
- jhoechtl 6y ago
  For me it clicked once it understood that integration is the area "beyond" the "curve".
Barrin92 6y ago
It's a good goal from just a humanistic standpoint and because learning should be recreational but from an innovation standpoint it's honestly likely overrated. Innovation is the result of very particular institutions and resources being coordinated and people networking and clustering tightly, which is why, despite incredibly dispersion of knowledge over the internet, innovation and VC money actually still is so geographically concentrated. I think these online learning resources are good but the expectations should be correct, they're not tools to kickstart innovation, which is much more tacit and reliant on close interaction between people rather than knowledge.

signaru 6y ago

working with image processing makes convolution easily intuitive. you can get a "feel" of what the math is doing by looking what's happening with the images. while blurring is a common example (convolve a Gaussian function with the image), edge detection and other image operations are just a matter of changing the convolved signal (or kernel). in a simplified model, blurry photos due to poor lenses also share the same principle (the lens cannot form a perfect point, that imperfect point is effectively what is convolved). the same can be said for audio and other 1d data, but images are more visual.

syntaxing 6y ago

My diffeq professor explained it as the fifth form of arithmetic (first four being addition, subtraction, multiplication, and division). This fifth form is unique because you sweep two functions relative to time and each other. To be honest, I still don't fully grasp the concept and I just use it as a mathematical tool. I need a 3blue1brown video to explain this to me so I can have an "aha!" moment like I had in his linear algebra videos.

vlasev 6y ago
I'm sure you've seen this elsewhere in the comments, but multiply two polynomials to see a discrete convolution in action! Here your functions would be discrete.

imvetri 6y ago

And multiplication is a fancy addition

deleted 6y ago
[deleted]
imvetri 6y ago
Addition is a repetition of vector
- imvetri 6y ago
  Vector is displacement of a point

midjji 6y ago

Just because its funny, here is the obligatory reminder that deep convolutional networks are actually implemented as correlation, not convolution. True, its just the lack of mirroring that differs, which is a linear operation and hence, the network can be considered too have learned the mirrored kernels, but it matters for initialization(bilinear init for conv^T sampling is still incorrectly mirrored in pytorch), and every time someone has put the images of the kernels in a paper its better than even odds they show the correlation, not convolution kernls.

brettermeier 6y ago

That "Colorized Math" idea is pretty great! Thanks for let me stumbling over the link in this article.

leoedin 6y ago

There's a brilliant (and free) book called The Scientist and Engineer's Guide to Digital Signal Processing which covers this and other DSP topics. It's very readable and clear - I found it super useful in understanding DSP and the maths surrounding it. Most of the time the actual stuff happening is quite simple, but if you're not living and breathing mathematical notation the conventional explanations can be quite impenetrable. This book puts everything out in code, so you can follow the steps and truly understand what's happening. http://www.dspguide.com/ http://www.dspguide.com/

spacechild1 6y ago
I can second your recommendation! This book helped me to finally grok convolution and many other things.

JekLod10 6y ago

I could not understand convolution in the beginning partly because the book sucked and my professor was derisive with bad middle eastern accent. I wish resources like these existed back in the 90's so we would not waste time learning stuff.

hatsunearu 6y ago

So this is just discrete convolution but continuous time convolution AFAIK has no intuitive explanation. The general idea is there is a sense of taking mathematical operations as having not just numbers and variables and outputing another number or variable... but that operations can take any number of anything and output any number of anything. The Fourier Transform takes in a function and outputs another function, which you can put meaning on it or you can just "nod and continue" (which is often easier instead of trying to put some words on abstract concepts). Some "ideas" you can use to analyze the situation are concepts learned in things like linear algebra like abstract vector spaces, basis, eigen-whatever... and so on. In the case of the continuous time convolution, it just turns out there is a magical thing associated with something called a Dirac Delta function with certain properties that are important for various things in controls engineering. Kinda feels like a piece of turd that refuses to evacuate but I just stopped caring about "intuitive" explanations.

sunstone 6y ago

All mathematics is abstractions of addition.