I've read that some convolution implementations use FFT to calculate the output feature/activation maps and I'm wondering how they're related. I'm familiar with applying CNNs, and (mildly) familiar with the use of FFT in signal processing, but I'm not sure how the 2 work togetherWhen I think of convolutions, I imagine taking a kernel, flipping it, multiplying (and adding) the elements of the kernel with the overlapping input, shifting the kernel and repeating the process. How does a FFT fit into this process?
Convolutional neural network fast fourier transform
machine learning;neural network;convnet
By transforming both your signal and kernel tensors into frequency space, a convolution becomes a single element-wise multiplication, with no shifting or repeating.So you can convert your data and kernel into frequencies using FFT, multiply them once then convert back with an inverse FFT. There are some fiddly details about aligning your data first, and correcting for gain caused by the conversion.If you have a good FFT library, this can be very efficient, but there is overhead cost for running the Fourier transform and its inverse, so your convolution needs to be relatively large before it is worth looking at FFT.I have explored this a while ago in a Ruby gem called convolver. You can see some of the code for an FFT-based convolution here and the project includes unit tests that prove that direct convolution gets same numerical results as FFT-based convolution. There is also code that attempts to estimate when it would be more efficient to calculate convolutions directly by repeated multiplications or use FFT-based solution (that is rough and ready guesswork though, and implementation-dependent). 