# Convolutional neural network fast fourier transform

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?

• 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. – Neil Slater Mar 2 '17 at 7:49