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

111–120 of 130 posts

Re: Convolution Is Fancy Multiplication

#111

Post by alexpotato »

DoreenMichele wrote: post #88
dwrodri wrote: 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…

because so many people were exposed to the topic through a resource (typically another person) who had little experience (or interest) in effectively teaching the subject. I used to homeschool and one of my sons had terrible baggage about math by the time I pulled him out of public school when he was 11. And somewhere along the way, I learned that a lot of elementary school teachers are women who weren't doing well i…

It's interesting you mention the solider aspect because the US Marine Corps went through a similar evaluation.

For a long time, being a drill instructor (the guy yelling at you in boot camp) was considered a low status position and therefore a career dead end. This in turn led to the DI spots being filled primarily by people who were in trouble, didn't care or were "bad apples".

At some point, the questions were raised: "Wait, why are we putting some of our worst Marines to train new Marines? Wouldn't it it make more sense to have our BEST Marines train the next generation?". The follow up was then: so how do we actually make that happen?

The answer was to make being a DI one of the stepping stones to higher level ranks. This dramatically increased the quality of DIs and in turn, raised the quality of the training and finally the Marines.

There is a similar story in some countries with socialized medicine. E.g. to get a license to practice medicine privately, you first have to spend N years working in a public hospital. This ensures that you can get top quality people working even in a public healthcare based system.

Re: Convolution Is Fancy Multiplication

#112

Post by jonahx »

peppery wrote: post #78
jonahx wrote: post #75

Earlier quoted context omitted.

"if one thinks of functions as fuzzy versions of points" Can anyone elaborate on this?

Tao is likely inviting us (just as many physical/probabilistic laws do) to view any arbitrary function as relatively "thicker"/"fuzzier" than an infinitely-thin, infinitely-tall spike function at a certain value: the Dirac delta function ( https://en.wikipedia.org/wiki/Dirac_delta_function ). If you convolve ≡ integrate this Dirac delta function (located at some value x) against any function g(t), by construction the…

Great explanation, thank you.

Re: Convolution Is Fancy Multiplication

#113

Post by dsagal »

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 is really cool. The original post is great in putting it in terms of a concrete example. It would be cool (challenging but possible) to have a 3D visualization of collapsing f(x)·g(y) like you describe in the context of that same example.

It's certainly a useful mental model.

Re: Convolution Is Fancy Multiplication

#114

Post by rualca »

enriquto wrote: post #103
rualca wrote: post #40

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

> (...) then the correlation of f and g evaluated at x

It really isn't the same, and oddly enough you unknowingly show that off, by mentioning that convolution is the function that maps input functions to the output function, but the dot product is at best a single point evaluated with the output function.

Re: Convolution Is Fancy Multiplication

#115

Post by spacechild1 »

leoedin wrote: post #97

There's a brilliant (and free) book called The Scientist and Engineer's Guide to Digital Signal Processing which covers this and other DSP topics. It's very readable and clear - I found it super useful in understanding DSP and the maths surrounding it. Most of the time the actual stuff happening is quite simple, but if you're not living and breathing mathematical notation the conventional explanations can be quite im…

I can second your recommendation! This book helped me to finally grok convolution and many other things.

Re: Convolution Is Fancy Multiplication

#116

Post by SamReidHughes »

antonfire wrote: post #108
SamReidHughes wrote: post #23

Earlier quoted context omitted.

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?

For example, starting from decimal representation, you can calculate the product of five digit numbers, ("abcde" * "fghij") with the following, where capitalized variables X and S are the magic O(1)-addition integer types:

    let X = to_magic_integer("abcde")
    let y = "fghij".reverse()
    let S = to_magic_integer("0")
    for d = 0 to 4
        for i = 1 to y[d]
            S += X
        end
        X = X+X+X+X+X + X+X+X+X+X
    end

    return S
(You can implement to_magic_integer with basically the same algorithm in O(n).)

Re: Convolution Is Fancy Multiplication

#117

Post by antonfire »

SamReidHughes wrote: post #116
antonfire wrote: post #108

Earlier quoted context omitted.

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

For example, starting from decimal representation, you can calculate the product of five digit numbers, ("abcde" * "fghij") with the following, where capitalized variables X and S are the magic O(1)-addition integer types: let X = to_magic_integer("abcde") let y = "fghij".reverse() let S = to_magic_integer("0") for d = 0 to 4 for i = 1 to y[d] S += X end X = X+X+X+X+X + X+X+X+X+X end return S (You can implement to_ma…

The premise was

> addition operations of numbers with log(n) bits deemed to take O(1) time.

not

> addition operations of numbers with n bits deemed to take O(1) time.

Re: Convolution Is Fancy Multiplication

#118

Post by SamReidHughes »

antonfire wrote: post #117
SamReidHughes wrote: post #116

Earlier quoted context omitted.

For example, starting from decimal representation, you can calculate the product of five digit numbers, ("abcde" * "fghij") with the following, where capitalized variables X and S are the magic O(1)-addition integer types: let X = to_magic_integer("abcde") let y = "fghij".reverse() let S = to_magic_integer("0") for d = 0 to 4 for i = 1 to y[d] S += X end X = X+X+X+X+X + X+X+X+X+X end return S (You can implement to_ma…

The premise was > addition operations of numbers with log(n) bits deemed to take O(1) time. not > addition operations of numbers with n bits deemed to take O(1) time.

Those are equivalent statements.

Re: Convolution Is Fancy Multiplication

#119

Post by hatsunearu »

So this is just discrete convolution but continuous time convolution AFAIK has no intuitive explanation.

The general idea is there is a sense of taking mathematical operations as having not just numbers and variables and outputing another number or variable... but that operations can take any number of anything and output any number of anything. The Fourier Transform takes in a function and outputs another function, which you can put meaning on it or you can just "nod and continue" (which is often easier instead of trying to put some words on abstract concepts).

Some "ideas" you can use to analyze the situation are concepts learned in things like linear algebra like abstract vector spaces, basis, eigen-whatever... and so on.

In the case of the continuous time convolution, it just turns out there is a magical thing associated with something called a Dirac Delta function with certain properties that are important for various things in controls engineering.

Kinda feels like a piece of turd that refuses to evacuate but I just stopped caring about "intuitive" explanations.

Re: Convolution Is Fancy Multiplication

#120

Post by antonfire »

SamReidHughes wrote: post #118
antonfire wrote: post #117

Earlier quoted context omitted.

The premise was > addition operations of numbers with log(n) bits deemed to take O(1) time. not > addition operations of numbers with n bits deemed to take O(1) time.

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.

Post reply on HN