5
$\begingroup$

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 together

When 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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
6
$\begingroup$

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).

Improve this answer
$\endgroup$
4
  • $\begingroup$ I have a hard time imagining a FFT on a small, say 3x3, kernel as there isnt much information there. Is this method better for larger kernels, or does it not matter? $\endgroup$
    – Simon
    Commented Mar 1, 2017 at 22:53
  • $\begingroup$ The method works accurately on small kernels, FFT is a discrete algorithm and works fine on e.g. 3x3 in terms of numeric precision. My numeric unit tests include small 3x3 kernels: github.com/neilslater/convolver/blob/master/spec/… - the results are identical to within $10^{-9}$ mean square error. However, the CPU overhead for conversion is relatively high when kernel and signal sizes are smaller. $\endgroup$
    – Neil Slater
    Commented Mar 2, 2017 at 7:49
  • $\begingroup$ In fact looking at my code, the FFT copes just fine with 1x1 kernels, and this is tested. The kernel and signal are padded out to a combined size before running FFT, so a single point will have lots of high-frequency components across the space. $\endgroup$
    – Neil Slater
    Commented Mar 2, 2017 at 8:01
  • $\begingroup$ Could someone take a look on a question I have with similar topic? $\endgroup$
    – Eduardo Reis
    Commented Jan 10, 2019 at 2:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.