FFT convolution in Python
For computing convolution using FFT, we’ll use the fftconvolve() function in scipy.signal library in Python.
Syntax: scipy.signal.fftconvolve(a, b, mode=’full’)
Parameters:
- a: 1st input vector
- b: 2nd input vector
- mode: Helps specify the size and type of convolution output
- ‘full’: The function will return the full convolution output
- ‘same’: The function will return an output with dimensions same as the vector ‘a’ but centered at the centre of the output from the ‘full’ mode
- ‘valid’: The function will return those values only which didn’t rely on zero-padding to be computed
Below is the implementation:
Python
from scipy import signal a = [ 1 , 2 , 3 ] b = [ 4 , 5 , 6 ] y = signal.fftconvolve(a, b, mode = 'full' ) print ( 'The convoluted sequence is ' , y) |
Output
The convoluted sequence is [ 4. 13. 28. 27. 18.]
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 !