But what is a convolution?

Discrete convolutions, from probability to image processing and FFTs.
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

Lecture on Discrete Fourier Transforms

Reducible video on FFTs

Veritasium video on FFTs

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:

You can find code for specific videos and projects here:

Music by Vincent Rubinetti.

Download the music on Bandcamp:

Stream the music on Spotify:

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

------------------

Various social media stuffs:

[reillymcdowell]

Ok… the fact that a 23 minute video about an advanced math topic is #42 in the youtube trending charts is incredible and represents the sheer explanatory power of 3B1B. Congratulations, Grant!

[lioreshkhar]

Anyone else would love to see a Stats series from 3b1b? I feel like that's a topic that's so often very confusingly and unintuitively explained.

[dude]

I did my PhD in image processing, detecting the surface interfaces of different structures in volumetric imagery such as MRI data to support tasks such as segmentation. Convolution is such a key process for so many of the different stages. This video is the most elegant and clear explanation of convolution I've ever come across.

[misterjigolo]

I'm amazed by the fact that Grant is basically providing so much more intuition and understanding in 25 minutes about a complex subject than what I got from 10 hours classes during my AI master degree.

And that's free.

You really are a legend Grant, thank you.

[liweicai]

22:20 Hidden fun fact here: the O(NlogN) algorithm is only discovered in 2019, and for it to be actually fast the number would be too long to fit in our universe. Naturally utilizing the FFT convolution introduced in this video yields an algorithm of complexity O(NlogNloglogN), known as the Schönhage–Strassen algorithm, discovered in 1971. It is fast for numbers with thousands of digits and is built-in for big integer computation in some programming languages.

[nosy-cat]

That transition animation at 5:28 is a work of art!

[janiKB]

You honestly bring me near to tears because I always thought I was "bad at math". But binge watching your videos and understanding concepts I never could have grasped have made me realize that I can learn math, with the right teacher. Thank you so much for making these videos!

[SupaJay]

As a guy that has never seen convolutions, i only came here because i saw Kirb in the thumbnail and wow I was enlightened

[exylic]

10:45 One correction: Putting your lens out of focus tends to actually produce, rather than a gaussian blur, a disc blur, which is actually a lot *more* similar to a box blur, just circular in shape rather than square. It's harder to compute than a gaussian or box blur, because with those two, you are able to use the 1D kernel twice rather than use a more expensive 2d kernel. Using a box blur is often undesirable because it produces a "bokeh" square in shape rather than circular, and other directional artifacts. The gaussian blur, on the other hand, is more akin to putting a translucent film in front of the camera, or covering the lens in vaseline.

[MrSpeakerCone]

Great stuff as always!
I'm an audio engineer and we generally use FFT convolution algorithms for creating reverb. Long story short, we can record how a physical space reacts to an impulse, then convolve other audio such that it sounds like it was produced in that space. It honestly feels like magic :)

[mandarbamane]

Video: But what is a convolution?
- LTI systems entered the chat.
- Laplace transform entered the chat.
- Fourier transform entered the chat.
- Z transform entered the chat.
- Correlation entered the chat.

[konstantine]

We also use convolution in audio. It's the equivalent of adding one sound inside the "space" of another sound. It is highly applicable to the reverberation of spaces but not limited to just that. Excellent video. Subscribed for more!

[sharkinahat]

Fun trick for doing blur - it's separable. If you have a 9x9 kernel, you just sample along one axis using a 1x9 kernel and do the same using the results along the other axis (9x1 kernel). You go down from 81 samples per pixel to just 18.

[azmodanpc]

The video I needed back in college when I was struggling to understand these concepts for my umpteenth math exam.

[PhobosB]

I've been struggling to visualise convolution for my University's Signal course, I've even watched some animations online and tried to get a hang of the discrete convolution and nothing, NOTHING comes close to this absolutely vivid imagery carefully chaperoned by your voice. You're the Richard Feynman of this century and Thank you for continuing making these videos. :)

[debaelwyn]

As someone who's spent much of the last ten years doing complex signal processing professionally and using FFTs and convolutions in a bunch of contexts, this is phenomenal and does a great job of capturing the intuitions I built up over the last decade and summarizing them in 23 minutes. Thank you!

[liammccreary]

I love Grant’s respect for his students’ variable exposure to math concepts and problem solving. Instead of saying “you should know by now that…” he says “just know that there are certain paths you could have walked in math that make this more of an expected step.” This really helps me feel more validated in my own experience with math.

[Holko]

Seeing so many different lectures on youtube on different topics is already an amazement in itself, but watching the highqualitity output, which has been kickstarteted by 3b1b with manim, transition to ofther channels, just increased youtubes potential as a learning platform. It is really amazing to see others using the library and creating their own content and I, as a humble viewer, am thankful for this addition.

[douglascheng]

I just graduated from school where I used convolution for image processing, signals, etc. and you just explained it more intuitively than anything I got out of school.

[wyattr]

My final project for my MS in Computer Engineering was implementing an FPGA based guitar speaker simulator. The convolution of an audio signal with an impulse response of a particular speaker will impart the characteristics of that speaker onto the signal (though the actual implementation was FFT based so it would work im real time). Thanks for this explanation so others in my life can understand what i was losing my mind over for months