Live data from Hacker News

Convolution Is Fancy Multiplication

betterexplained.com

101–110 of 130 posts

Re: Convolution Is Fancy Multiplication

#101

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…

> Convolution is a correlation with a reversed signal.

Interesting - when I learnt it, convolution came first.

I like the visual 'sliding' explanation best. Perhaps partly because that's what I was shown, but also because, I think, how else would you explain any integral? I mean, you could, but would you?

Even to a blind person (so I couldn't draw a diagram) I'd explain integration as 'picture a graph ... it's that bit ... it's adding this and this and this ... just like when you multiply two sides of a rectangle ...'

Re: Convolution Is Fancy Multiplication

#102
post #62

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 your example, I guess you are reversing the 2nd signal so if the signals are the opposite. "Adding" or convolving them results in a zero? i.e. if the signal is a (+)slope /, convolving it with a reverse of that signal \ = 0 In this sense you are leaving the difference between 2 signals.

Yes that is (auto- if using the same signal) correlation.

Re: Convolution Is Fancy Multiplication

#103
post #40
post #31

Earlier quoted context omitted.

I don't think you can really call it a generalized dot product, because it doesn't map to a scalar. The inner product is the well accepted definition of a generalized dot product, and convolution does not follow the axioms that an inner product must follow.

> I don't think you can really call it a generalized dot product, because it doesn't map to a scalar. This. Convolution is a function which results from applying to convolution operator to two functions. A dot product is nothing of the sort.

> A dot product is nothing of the sort.

Its nearly the same thing, isn't it? If you denote by Tx the left-shift operator defined by (Tx f)(y) = f(y+x), then the correlation of f and g evaluated at x is precisely the dot product of f and Tx g. If you evaluate your function at a certain point, you obtain a scalar product.

Re: Convolution Is Fancy Multiplication

#104
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.

Re: Convolution Is Fancy Multiplication

#105
post #42
post #11

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…

> And multiplication is a fancy convolution (with carries). It really isn't. Just because you see different digits being multiplied that doesn't mean you're convolving functions.

What's 111111111*111111111?

Re: Convolution Is Fancy Multiplication

#106
post #65

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…

I'm split on this. On one hand I appreciate these kinds of posts because they bring math with intuition to broader masses.

On the other hand, it makes people believe that they have understood what's there to understand and move on. In a sense, they contribute to the Dunning-Kruger effect.

The article illustrates this quite well. The intuition is presented well, but is no substitute for actually learning math. The first two questions in the end:

> Why is one function reversed?

> Why is convolution commutative?

With having studied math "properly", it's immediately obvious that they are answers to each other. Defining it with the "reversal" on one function is what makes the operation commutative by introducing a somewhat hidden symmetry and that's a quite common trick in mathematics.

The other two questions are also quite clear with some actual math background. Not M.Sc. level math, just some proper calculus. You just need to sit down and do the math, which can take half a page of pen-on-paper. That's what math is, you need to work it.

Again, don't get me wrong, I appreciate the effort. But those types of posts don't make you more fluid in math than reading a popular science article about Alpha Centauri makes you an astronomer or an expose about Covid-19 makes you an epidemioloist. It's popular science and can't replace the actual study of the subject.

Re: Convolution Is Fancy Multiplication

#107
post #39
post #35

Earlier quoted context omitted.

The only cherry picking is that the numbers need to be small enough that the decimal digit does not overflow (4 times 2 is fine but 4 times 3 is not). A more 'convolved' example: 121 * 23 = 2783 If you use hex instead it also works for larger digits like 0x42 * 0x31 = 0xCA2 = [12, 10, 2] So, if you convert to a digit of a large enough base you can do any multiplication with just a convolution and no carry.

> The only cherry picking is that the numbers need to be small enough that the decimal digit does not overflow Aren't you restating my point? > So, if you convert to a digit of a large enough base you can do any multiplication with just a convolution and no carry. There is no convolution at all. There's only a cherry-picked example of how plain old multiplication feels similar to a sliding dot product, which for some…

The first few Google results for "sliding dot product" basically describe it as a convolution with the domain of one of the functions reversed. (Note as far as whether or not to reverse one of the functions, multiplication in base-b agrees with "convolution" and not with "sliding dot product".)

Elsewhere in the thread you seem to be suggesting that convolution is a way to convert between a frequency domain and a time domain, which suggests that you are confusing convolution with Fourier transforms. There's some nice relationships between these things, so they are often discussed together, but even then a single convolution happens either entirely in the time domain or entirely in the frequency domain, not as a way of going from one of those domains to the other. E.g. the pointwise product (in the frequency domain) of the Fourier transforms of two functions is the Fourier transform of the convolution (in the time domain) of those two functions.

There's also a chance you are focused on the difference between functions with a discrete domain and functions with a continuous domain. The term "convolution" is often applied to both.

Re: Convolution Is Fancy Multiplication

#108
post #15

Earlier quoted context omitted.

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).

> 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).

How's that?

Re: Convolution Is Fancy Multiplication

#109
post #65

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…

> and the entire body of high quality MOOCs are just available __for free__ over the Internet

nobody alerted me to these

Re: Convolution Is Fancy Multiplication

#110
post #39
post #35

Earlier quoted context omitted.

The only cherry picking is that the numbers need to be small enough that the decimal digit does not overflow (4 times 2 is fine but 4 times 3 is not). A more 'convolved' example: 121 * 23 = 2783 If you use hex instead it also works for larger digits like 0x42 * 0x31 = 0xCA2 = [12, 10, 2] So, if you convert to a digit of a large enough base you can do any multiplication with just a convolution and no carry.

> The only cherry picking is that the numbers need to be small enough that the decimal digit does not overflow Aren't you restating my point? > So, if you convert to a digit of a large enough base you can do any multiplication with just a convolution and no carry. There is no convolution at all. There's only a cherry-picked example of how plain old multiplication feels similar to a sliding dot product, which for some…

You’re right that the analogy between elementary-school-multiplication and convolution only works for multiplication without carrying. That still leaves a large amount of possible multiplication instances, for the term “cherry picking” to apply here.

You’re wrong to suggest that elementary-school-multiplication and (discrete) convolution are so dissimilar that the analogy is so unhelpful that it only adds to everyone’s confusion. Maybe to yours, but not to everyone’s.

If I understand your objection correctly (other than the already conceded fact that the analogy does not work in case of multiplication with carrying), you already have internalized that convolution is an operator on 2 functions, resulting in a function. And since you have already internalized that, the analogy with any operator on two natural numbers resulting in a natural number confuses you — although I assume you can see the similarity in the sliding operation.

For people who have not internalized what a convolution is, the visualisationg of the sliding operation, and the analogy with elementary-school-multiplication is the helpful bit.

To clarify why the operations are really similar: consider a natural number as a function that takes a natural number as argument, and returns the digit (between 0 and 9 inclusive) for that decimal position.

So f = 2 031 is considered to be: n → f(n) = if n = 3 then return 2 else if n = 1 then return 3 else if n = 0 then return 1 else return 0 (end if).

And g = 320 is considered to be: n → g(n) = if n = 2 then return 3 else if n = 1 then return 2 else return 0 (end if).

What is then the discrete convolution f ∗ g?

It’s f ∗ g = n → (f ∗ g)(n) = f(3) × g(n – 3) + f(1) × g(n – 1) + f(0) × g(n)

= n → if n = 5 then return 6 else if n = 4 then return 4 else if n = 3 or n = 2 then return 9 else n = 1 then return 2 else return 0 (end if).

This is how we consider 649 920 = 2 031 × 320.

Post reply on HN