Earlier quoted context omitted.
Ah, that explains it perfectly!
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.
depends on the audience I think
Convolution Is Fancy Multiplication
21–30 of 130 posts
Re: Convolution Is Fancy Multiplication
#22Okay. 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)
Here's a nice sanity check: if (tau) is larger than (t), (or equivalently, (t-tau)_____________________________
*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.
Re: Convolution Is Fancy Multiplication
#23And 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…
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).
Re: Convolution Is Fancy Multiplication
#24Re: Convolution Is Fancy Multiplication
#25Earlier quoted context omitted.
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.
depends on the audience I think
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.
Re: Convolution Is Fancy Multiplication
#26Convolution 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 example is great, hope you don't mind if I spell it out how your impulse weight f(d) and impulse response functions g(d) are functions over d (each associated with 10^d):
f(0) = 1 g(0) = 3 f*g(0) = 3
f(1) = 0 g(1) = 2 f*g(1) = 2
f(2) = 1 f*g(2) = 3
f(3) = 0 f*g(3) = 2
f(4) = 0 f*g(4) = 0
f(5) = 1 f*g(5) = 3
f*g(6) = 2
Re: Convolution Is Fancy Multiplication
#27Convolution 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…
> 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.
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.
Re: Convolution Is Fancy Multiplication
#28Convolution 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…
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?
> 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
Convolution is not a number. Convolution is an operator that outputs a function.
Re: Convolution Is Fancy Multiplication
#29Earlier quoted context omitted.
> 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.
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.
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.
Re: Convolution Is Fancy Multiplication
#30Convolution 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…
> 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).
Here is a bit more rambling in the direction of linear algebra and probability: you can define a vector space on the set of all random variables, wherein each random variable is a vector. Once you do so, you can further impose an inner product space with the traditional covariance function as the inner product. If the two random variables are orthogonal with respect to this inner product and this space, by definition their covariance is equal to 0. It follows by the definition of correlation from covariance that their correlation will also be 0, i.e. orthogonality implies two variables are uncorrelated in this space :)
Strictly speaking the correlation function is not the inner product in this instance, but practically the result is the same.