But What Is a Convolution?

Explore the concept of convolution in this 23-minute video that covers its applications in probability, image processing, and Fast Fourier Transforms (FFTs). Dive into discrete convolutions, starting with their role in adding random variables and moving averages. Discover how convolutions are used in image processing techniques and polynomial multiplication. Learn about runtime complexity and how FFTs can speed up convolution operations. Gain insights into the mathematical foundations and practical applications of convolutions, from basic examples to advanced algorithms used in various fields of mathematics and computer science.

Another small correction at . I describe ON^2 as meaning "the number of operations needed scales with N^2". However, this is technically what ThetaN^2 would mean. ON^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.
- Where do convolutions show up?
- Add two random variables
- A simple example
- Moving averages
- Image processing
- Measuring runtime
- Polynomial multiplication
- Speeding up with FFTs
- Concluding thoughts