The intuition behind using FFT for convolution
One of the most fundamental signal processing results states that convolution in the time domain is equivalent to multiplication in the frequency domain. For performing convolution, we can convert both the signals to their frequency domain representations and then take the inverse Fourier to transform of the Hadamard product (or dot product) to obtain the convoluted answer. The workflow can be summarized in the following way
Diagrammatic representation of the FFT workflow
Installation:
For this article’s purposes, we’ll be using some inbuilt functions from the Python libraries numpy and scipy. You can use the pip package manager to install them.
pip install scipy numpy
How to perform faster convolutions using Fast Fourier Transform(FFT) in Python?
Convolution is one of the most important mathematical operations used in signal processing. This simple mathematical operation pops up in many scientific and industrial applications, from its use in a billion-layer large CNN to simple image denoising. Convolution can be both analog and discrete in nature, but because of modern-day computers’ digital nature, discrete convolution is the one that we see all around!
The discrete convolution of two 1 dimensional vectors and , is defined as
As it requires the multiplication of two vectors, the time complexity of discrete convolution using multiplication(assuming vectors of length ) is . Here’s where Fast Fourier transform(FFT) comes in. Using FFT, we can reduce this complexity from to !