Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Convolution Is Fancy Multiplication

betterexplained.com

Post reply on HN
Print view View original

41–50 of 130 posts

Re: Convolution Is Fancy Multiplication

#41

Post by adamnemecek »

Tomminn wrote: post #34
adamnemecek wrote: post #2

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

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…

Ok, exterior product.

Re: Convolution Is Fancy Multiplication

#42

Post by rualca »

phaker wrote: 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.

Re: Convolution Is Fancy Multiplication

#43

Post by rualca »

sriku wrote: post #8

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…

> Convolution is digit-based multiplication,

It really isn't, and I don't understand the level of confusion that leads to this assertion.

Is it because the elementary school algorithm for multiplication decomposes a number in it's decimal places before multiplying?

> so why not start with that?

Because it would be wrong, misguided, and it would fail to demonstrate the logic behind convolution.

Let's take a step back and think about it. Convolution is mainly and primarily used as a convenient way to covert signals between time and frequency domain, within the scope of Fourier transforms. Who in their right mind associates elementary school multiplications with conversions to/from the frequency domain?

Re: Convolution Is Fancy Multiplication

#44

Post by rualca »

Tomminn wrote: post #32
rualca wrote: post #28

Earlier quoted context omitted.

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

The parents point is that when you do the primary school multiplication algorithm, you are actually performing a discrete convolution.

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.

Re: Convolution Is Fancy Multiplication

#45

Post by bonoboTP »

onecommentman wrote: post #38

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.

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

Re: Convolution Is Fancy Multiplication

#46

Post by bitdizzy »

scythe wrote: post #37

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…

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.

Re: Convolution Is Fancy Multiplication

#47

Post by tprice7 »

Tomminn wrote: post #31
kazinator wrote: post #12

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

Furthermore, it doesn't involve complex conjugation, and (closely related) it doesn't have any property akin to positive-definiteness.

Re: Convolution Is Fancy Multiplication

#48

Post by bigmanwalter »

m-hilgendorf wrote: post #13

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 serv…

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!

Re: Convolution Is Fancy Multiplication

#49

Post by bonoboTP »

hprotagonist wrote: post #4

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

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).
Post reply on HN