Abstract
1D convolutions are extensively used in digital signal processing (filtering/denoising) and analysis (also through CNNs). As their computational complexity is of the order O(N^2), their fast execution is a must.
This lecture will overview linear systems, linear and cyclic convolution and correlation. Then it will present their fast execution through FFTs, resulting in algorithms having computational complexity of the order O(Nlog2N). Optimal Winograd 1D convolution algorithms will be presented having theoretically minimal number of computations. Parallel block-based 1D convolution/calculation methods will be overviewed.
FFT algorithm.
1D Winograd convolution.
Fast-1D-Convolution-Algorithms-v4.1.1-SummaryUnderstanding Questionnaire
https://docs.google.com/forms/fast-1d-convolution-algorithms