Fast 1D Convolution Algorithms Lecture
Digital signals are ubiquitous and have many applications in several disciplines:
-Digital Media, Social Media (music, voice signals),
-Biomedical Signal Analysis and Diagnosis,
-Bioinformatics
-Autonomous cars, drones, marine vessels, robots
-Big Data Analytics,
-Internet and Communications (music broadcasting, streaming).
-Scientific signal acquisition of any sort, e.g., Environment Sensing, Geophysical Prospecting.
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.