3Blue1Brown | But what is a convolution? @3blue1brown | Uploaded 1 year ago | Updated 2 hours ago
Discrete convolutions, from probability to image processing and FFTs.
Video on the continuous case: youtu.be/IaSGqQa5O-M
Help fund future projects: patreon.com/3blue1brown
Special thanks to these supporters: 3b1b.co/lessons/convolutions#thanks
An equally valuable form of support is to simply share the videos.
Other videos I referenced
Live lecture on image convolutions for the MIT Julia lab
youtu.be/8rrHTtUzyZA
Lecture on Discrete Fourier Transforms
youtu.be/g8RkArhtCc4
Reducible video on FFTs
youtu.be/h7apO7q16V0
Veritasium video on FFTs
youtu.be/nmgFG7PUHfo
A small correction for the integer multiplication algorithm mentioned at the end. A “straightforward” application of FFT results in a runtime of O(N * log(n) log(log(n)) ). That log(log(n)) term is tiny, but it is only recently in 2019, Harvey and van der Hoeven found an algorithm that removed that log(log(n)) term.
Another small correction at 17:00. I describe O(N^2) as meaning "the number of operations needed scales with N^2". However, this is technically what Theta(N^2) would mean. O(N^2) would mean that the number of operations needed is at most constant times N^2, in particular, it includes algorithms whose runtimes don't actually have any N^2 term, but which are bounded by it. The distinction doesn't matter in this case, since there is an explicit N^2 term.
Thanks to these viewers for their contributions to translations
Hebrew: Omer Tuchfeld
Italian: Emanuele Vezzoli
Vietnamese: lkhphuc
--------
These animations are largely made using a custom python library, manim. See the FAQ comments here:
3blue1brown.com/faq#manim
github.com/3b1b/manim
github.com/ManimCommunity/manim
You can find code for specific videos and projects here:
github.com/3b1b/videos
Music by Vincent Rubinetti.
vincentrubinetti.com
Download the music on Bandcamp:
vincerubinetti.bandcamp.com/album/the-music-of-3blue1brown
Stream the music on Spotify:
open.spotify.com/album/1dVyjwS8FBqXhRunaG5W5u
Timestamps
0:00 - Where do convolutions show up?
2:07 - Add two random variables
6:28 - A simple example
7:25 - Moving averages
8:32 - Image processing
13:42 - Measuring runtime
14:40 - Polynomial multiplication
18:10 - Speeding up with FFTs
21:22 - Concluding thoughts
------------------
3blue1brown is a channel about animating math, in all senses of the word animate. And you know the drill with YouTube, if you want to stay posted on new videos, subscribe: http://3b1b.co/subscribe
Various social media stuffs:
Website: 3blue1brown.com
Twitter: twitter.com/3blue1brown
Reddit: reddit.com/r/3blue1brown
Instagram: instagram.com/3blue1brown
Patreon: patreon.com/3blue1brown
Facebook: facebook.com/3blue1brown
Discrete convolutions, from probability to image processing and FFTs.
Video on the continuous case: youtu.be/IaSGqQa5O-M
Help fund future projects: patreon.com/3blue1brown
Special thanks to these supporters: 3b1b.co/lessons/convolutions#thanks
An equally valuable form of support is to simply share the videos.
Other videos I referenced
Live lecture on image convolutions for the MIT Julia lab
youtu.be/8rrHTtUzyZA
Lecture on Discrete Fourier Transforms
youtu.be/g8RkArhtCc4
Reducible video on FFTs
youtu.be/h7apO7q16V0
Veritasium video on FFTs
youtu.be/nmgFG7PUHfo
A small correction for the integer multiplication algorithm mentioned at the end. A “straightforward” application of FFT results in a runtime of O(N * log(n) log(log(n)) ). That log(log(n)) term is tiny, but it is only recently in 2019, Harvey and van der Hoeven found an algorithm that removed that log(log(n)) term.
Another small correction at 17:00. I describe O(N^2) as meaning "the number of operations needed scales with N^2". However, this is technically what Theta(N^2) would mean. O(N^2) would mean that the number of operations needed is at most constant times N^2, in particular, it includes algorithms whose runtimes don't actually have any N^2 term, but which are bounded by it. The distinction doesn't matter in this case, since there is an explicit N^2 term.
Thanks to these viewers for their contributions to translations
Hebrew: Omer Tuchfeld
Italian: Emanuele Vezzoli
Vietnamese: lkhphuc
--------
These animations are largely made using a custom python library, manim. See the FAQ comments here:
3blue1brown.com/faq#manim
github.com/3b1b/manim
github.com/ManimCommunity/manim
You can find code for specific videos and projects here:
github.com/3b1b/videos
Music by Vincent Rubinetti.
vincentrubinetti.com
Download the music on Bandcamp:
vincerubinetti.bandcamp.com/album/the-music-of-3blue1brown
Stream the music on Spotify:
open.spotify.com/album/1dVyjwS8FBqXhRunaG5W5u
Timestamps
0:00 - Where do convolutions show up?
2:07 - Add two random variables
6:28 - A simple example
7:25 - Moving averages
8:32 - Image processing
13:42 - Measuring runtime
14:40 - Polynomial multiplication
18:10 - Speeding up with FFTs
21:22 - Concluding thoughts
------------------
3blue1brown is a channel about animating math, in all senses of the word animate. And you know the drill with YouTube, if you want to stay posted on new videos, subscribe: http://3b1b.co/subscribe
Various social media stuffs:
Website: 3blue1brown.com
Twitter: twitter.com/3blue1brown
Reddit: reddit.com/r/3blue1brown
Instagram: instagram.com/3blue1brown
Patreon: patreon.com/3blue1brown
Facebook: facebook.com/3blue1brown
