Performance comparison of FFT convolution with normal discrete convolution
- For computing the normal linear convolution of two vectors, we’ll use the np.convolve function.
- The %timeit magic function of Jupyter notebooks was used to calculate the total time required by each of the 2 functions for the given vectors.
Below is the implementation:
Python
import numpy as np from scipy import signal a = np.random.randn( 10 * * 5 ) b = np.random.randn( 10 * * 5 ) print ( 'Time required for normal discrete convolution:' ) % timeit np.convolve(a, b) print ( 'Time required for FFT convolution:' ) % timeit signal.fftconvolve(a, b) |
Output:
Time required for normal discrete convolution: 1.1 s ± 245 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) Time required for FFT convolution: 17.3 ms ± 8.19 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
You can see that the output generated by FFT convolution is 1000 times faster than the output produced by normal discrete convolution!
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 !