11–20 of 130 posts
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)
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.
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).
I realize convolution is commutative ("Part 3"), but it tripped me up a little as I tried to track the narrative.
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 wor…
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".
> 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-...
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…
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.
Everyone should introduce convolution that way.
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 correspondin…
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?
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 wor…
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…
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)