{"page":"\n\n
\n
\n
\n
\n
\n\nVideo\n
\n

\nBut what is a convolution?\n

\n
\n
\nGet Free Access for 10 Days!\n
\n
\n
\n
\n
\n
×
\n\n\n
\n\nPublisher:\n\n3Blue1Brown\n\n\n
\n
\nA 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,...\nA 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.
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\n
\n
\n\n
\n
\n
\n
\n

Resource Details

\n
\n
\n
\n
Curator Rating
\n
\n
\n
\n
\n
\n
Educator Rating
Not yet Rated
\n
\n
\n
\n
\n
Media Length
\n
22:34
\n
\n
\n
\n
\n
Grade
12th - Higher Ed
\n
\n
\n
\n
\n
Subjects
Math
1 more...
\n
\n
\n
\n
\n
Media Type
Instructional Videos
\n
\n
\n
\n
\n
Source:
\n
\n3Blue1Brown\n\n
\n
\n
\n
\n
\n
Date
\n
2022
\n
\n
\n
\n
\n\n
Language
English
\n
\n
\n
\n
\n
Audiences
For Teacher Use
2 more...
\n
\n
\n
\n
\n
Usage Permissions
Fine Print: Educational Use
\n
\n
\n
\n
\n
\n

Additional Materials

\n
\n\nSign in or Join Now
\" data-title=\"Get Full Access\" data-container=\"body\" rel=\"popover\" tabindex=\"0\" href=\"/subscription/new\">Video Transcript\n
\n
\n\nSign in or Join Now
\" data-title=\"Get Full Access\" data-container=\"body\" rel=\"popover\" tabindex=\"0\" href=\"/subscription/new\">Video Preview\n
\n
\n
\n

Concepts

\n
\n
products, data, arrays
\n
\n\n\n
\n
\n
\n
\n

Additional Tags

\n
\n
mathematics, three blue one brown, 3 blue 1 brown, 3b1b, 3brown1blue, 3 brown 1 blue, three brown one blue, red dye, sneaky backdoor, elementary school, pairwise products, fft algorithm, 1st place, blue dye, moving average, fast algorithm, convolve function, single pixel, image processing, offset values, smaller list, negative values, distinct pairs, algorithm, blue, average, function, product, system, pixel, picture, pair, bottom, table
\n
\n\n\n
\n
\n
\n
\n

Classroom Considerations

\n
Best For: Explaining a topic
Video is ad-free
\n
\n
\n

Educator Ratings

\n
\n
\n
\n
\n
\n\nShow resource details\n
\n
\n\" data-title=\"Get Full Access\" data-container=\"body\" rel=\"popover\" tabindex=\"0\" aria-label=\"Play video: But what is a convolution?\" href=\"/subscription/new\">\"But\n\n
\n
\n
\n\n\n\n"}