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

31–40 of 130 posts

Re: Convolution Is Fancy Multiplication

#31

Post by Tomminn »

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.

Re: Convolution Is Fancy Multiplication

#32

Post by Tomminn »

rualca wrote: post #28
jaggirs wrote: post #19

Earlier quoted context omitted.

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

Re: Convolution Is Fancy Multiplication

#33

Post by nabla9 »

spekcular wrote: post #16

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…

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.

Re: Convolution Is Fancy Multiplication

#34

Post by Tomminn »

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

Re: Convolution Is Fancy Multiplication

#35

Post by jaggirs »

rualca wrote: post #28
jaggirs wrote: post #19

Earlier quoted context omitted.

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

Re: Convolution Is Fancy Multiplication

#37

Post by scythe »

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

Re: Convolution Is Fancy Multiplication

#38

Post by onecommentman »

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.

Re: Convolution Is Fancy Multiplication

#39

Post by rualca »

jaggirs wrote: post #35
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 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 reason some people confuse with convolution. This is not helpful, and only adds to the confusion already expressed.

Re: Convolution Is Fancy Multiplication

#40

Post by rualca »

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.

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

Post reply on HN