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

121–130 of 130 posts

Re: Convolution Is Fancy Multiplication

#121

Post by antonfire »

antonfire wrote: post #120
SamReidHughes wrote: post #118

Earlier quoted context omitted.

Those are equivalent statements.

Do you interpret both as > addition operations of numbers with an arbitrary number of bits deemed to take O(1) time ? I was picturing a more restrictive model of computation in which your claim is along the lines of > There's an O(n)-time algorithm, which, given two numbers with n digits and a magic black box that can add log(n)-digit numbers together in O(1) time, will output the product of those two numbers.

Fun fact, you can construct and store a lookup table for sums of all possible pairs of O(log(n))-digit numbers in O(n) space. (And O(n) time, probably?)

So if your model of computation lets you look things up in a table like that in O(1) time, you can kind of get the situation I'm describing above. Maybe your model of computation shouldn't let you do this, but some do. Often if an algorithm takes up O(foo) space, we don't worry about the fact that lookups into that space should take Theta(log(foo)) time (to even read the address) rather than O(1) time, because things are assumed to "fit into memory".

Another fun way to be fussy along these lines is that the usual algorithms for sorting a list of n distinct items only give bounds of O(n (log n)^2) time. Each item takes around log(n) bits to even store, so comparing two of those can't be done in time O(1) in the worst case (in a model that forbids the kind of "cheating" I'm describing above). The best uniform bound you can hope for is time O(log n) per comparison. (Though in some sense the extra log(n) factor might "drop back out", because it takes O(n log(n)) space to even write down an input to this algorithm.)

Re: Convolution Is Fancy Multiplication

#122

Post by rualca »

sriku wrote: post #61
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.

(sum_i ai x^i)(sum_j bj x^j) when you expand that, the coefficient of x^k is the sum of aibj such that i+j=k which is discrete convolution. Set x=10 and you're dealing with decimal representation of numbers.

> Set x=10 and (...)

...and you no longer have a function, only the image of a function at a specific point of its domain.

Convolutions are functions, not functions evaluated at a specific, and cherry-picked point.

Re: Convolution Is Fancy Multiplication

#123

Post by rualca »

AdhemarVandamme wrote: post #110
rualca wrote: post #39

Earlier quoted context omitted.

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

> You’re wrong to suggest that elementary-school-multiplication and (discrete) convolution are so dissimilar (...)

They are way more than dissimilar, they are radically different concepts altogether.

Convolution is a function, or an operator that outputs a function given two input functions that share the same domain.

Plain old algebra over real numbers is nothing of the sort.

You're trying to compare a function, with its domain and codomain, with an operation between scalars that results in a scalar. It's way more than apples to oranges. It's apples to orange tree plantations.

Re: Convolution Is Fancy Multiplication

#124

Post by antonfire »

rualca wrote: post #123
AdhemarVandamme wrote: post #110

Earlier quoted context omitted.

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…

> You’re wrong to suggest that elementary-school-multiplication and (discrete) convolution are so dissimilar (...) They are way more than dissimilar, they are radically different concepts altogether. Convolution is a function, or an operator that outputs a function given two input functions that share the same domain. Plain old algebra over real numbers is nothing of the sort. You're trying to compare a function, wit…

The standard multiplication algorithm is an algorithm for taking base-b representations of two numbers and outputting the base-b representation of the product of those numbers. A base-b representation of a number is a sequence of digits. A sequence is a function.

This is not a large conceptual chasm. It is boilerplate for actually talking about decimal (or binary or hex or whatever) representations of numbers. Here is one version of that boilerplate, spelled out:

Think of a base-10 representation of a natural number as a function with domain N (the set of natural numbers) and codomain {0, ..., 9}, where f(0) is the ones digit, f(1) is the tens digit, f(2) is the hundreds digit and so on. (This function will be finitely supported, i.e. all but finitely many inputs to this function will give output 0.)

If f and g are the representations of two numbers n and m, then one can say the following about the representation of their product n * m:

  (1) Extend the codomain of f and g, to N, i.e. think of them as functions N -> N instead of functions N -> {0, ..., 9}.
  (2) Compute the convolution of those two functions, giving you another (still finitely supported) function h: N -> N. Usually at this point h will have values that are larger than 10.
  (3) Do all the carrying (e.g. repeatedly take the first n for which h(n) > 10, and subtract 10 from h(n) and add 1 to h(n+1)). Now all the values of h are in {0, ..., 9}, so you can think of h as a function N -> {0, ..., 9}.
The resulting function h is the base-10 representation of the product of the two numbers that f and g represent.

Re: Convolution Is Fancy Multiplication

#125

Post by SamReidHughes »

antonfire wrote: post #120
SamReidHughes wrote: post #118

Earlier quoted context omitted.

Those are equivalent statements.

Do you interpret both as > addition operations of numbers with an arbitrary number of bits deemed to take O(1) time ? I was picturing a more restrictive model of computation in which your claim is along the lines of > There's an O(n)-time algorithm, which, given two numbers with n digits and a magic black box that can add log(n)-digit numbers together in O(1) time, will output the product of those two numbers.

I was meaning arbitrary numbers of digits, yes. In the sense that the sets {ceil(log2(n >= 1))} = {n >= 0}, and generally taking for granted that the model doesn't change based on the value n.

Re: Convolution Is Fancy Multiplication

#126

Post by antonfire »

jaggirs wrote: post #19
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…

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?

A polynomial with a single variable is more or less what you would mean by "use base-infinity digits" in the first place.

Roughly, in base 10, the number represented by the sequence of digits d_0, d_1, ..., d_n is d_0 + d_1 * 10 + d_2 * 10^2 + ... + d_n * 10^n.

In "base infinity", the "number" represented by the sequence of digits d_0, d_1, ..., d_n is the polynomial d_0 + d_1 * x + d_2 * x^2 + ... + d_n * x^n.

Multiplying these "numbers" (polynomials) is like decimal multiplication, except the digits can be arbitrarily high and you do no carrying at all.

Re: Convolution Is Fancy Multiplication

#127

Post by SamReidHughes »

antonfire wrote: post #121
antonfire wrote: post #120

Earlier quoted context omitted.

Do you interpret both as > addition operations of numbers with an arbitrary number of bits deemed to take O(1) time ? I was picturing a more restrictive model of computation in which your claim is along the lines of > There's an O(n)-time algorithm, which, given two numbers with n digits and a magic black box that can add log(n)-digit numbers together in O(1) time, will output the product of those two numbers.

Fun fact, you can construct and store a lookup table for sums of all possible pairs of O(log(n))-digit numbers in O(n) space. (And O(n) time, probably?) So if your model of computation lets you look things up in a table like that in O(1) time, you can kind of get the situation I'm describing above. Maybe your model of computation shouldn't let you do this, but some do. Often if an algorithm takes up O(foo) space, we…

Yep. This is why I map all my inputs to vector first and use radix sort on that :-)

Re: Convolution Is Fancy Multiplication

#128

Post by vlasev »

syntaxing wrote: post #76

My diffeq professor explained it as the fifth form of arithmetic (first four being addition, subtraction, multiplication, and division). This fifth form is unique because you sweep two functions relative to time and each other. To be honest, I still don't fully grasp the concept and I just use it as a mathematical tool. I need a 3blue1brown video to explain this to me so I can have an "aha!" moment like I had in his…

I'm sure you've seen this elsewhere in the comments, but multiply two polynomials to see a discrete convolution in action! Here your functions would be discrete.

Re: Convolution Is Fancy Multiplication

#129

Post by vlasev »

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…

Woah this is really cool and an awesome point of view. Collapsing along the x-axis is just a projection along the vector [1, 0, 0] onto the the y-z plane defined by it and the origin. Then if you project along the vector [1, 1, 0] onto the plane defined by [1, -1, 0] and [0, 0, 1], you get the convolution.
Post reply on HN