But what is a convolution?

From the creator

Discrete convolutions, from probability to image processing and FFTs. Video on the continuous case: https://youtu.be/IaSGqQa5O-M Help fund future projects: https://www.patreon.com/3blue1brown Special thanks to these supporters: https://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 https://youtu.be/8rrHTtUzyZA Lecture on Discrete Fourier Transforms https://youtu.be/g8RkArhtCc4 Reducible video on FFTs https://youtu.be/h7apO7q16V0 Veritasium video on FFTs https://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 Italia

Published 2022-11-18 · Watch on YouTube ↗
Availability and playback restrictions are controlled by the original channel.