How are CNN kernels trained when using FFT for convolutions?

CNNs (convolutional neural networks) are adept at processing images, as their construction is based on the biological neural networks found in the human eye. "Kernels", sometimes called "filters", are small feature detectors in the form of small matricies that are slid (called "convulving") across an image detecting features in a sample image. This process is computationally intensive, as each time we slide one or more units we have to multiply each kernel value by the section of feature map we are sliding over.

Recently I found here that you can use FFT to do the convolutions up to ~4.8 times faster than with all that multiplication.

Kernels are regularly trained by backpropagation, treating each kernel entry almost like its own axon weight. However with the FFT method I am at a loss as to how to train the kernels.

So, how do you train the CNN kernels when using the FFT method of CNN convolutions? Is backpropagation still relevant?

• Have you checked the backpropagation algorithm (ref: brilliant.org/wiki/backpropagation)? There is a Python code at the end. Please, check if you could apply FFT similar to that. Feb 2 at 23:47
• See my attempt at explaining this. Technical points to consider are the restriction of the convolution to a rectangular domain that can be considered as a separate linear operation, and that the forward mode is usually a "reversed filter" convolution that devolves to the scalar product in the "single output" case, as you also described. The reverse operation in the back-propagation of gradients is then the normal convolution. Mar 19 at 14:27

• 1° calculate the convolution of the input samples with all of the filters: $$y_{f'}=\sum_f x_f\ast w_{f'f}$$
• 2° calculate the gradients (derivatives) of the loss with respect to the parameters of the convolution, if you apply the chain rule carefully you will find that this can be done using a convolution, specifically: $$\frac{\partial L}{\partial w_{f'f}} = \frac{\partial L}{\partial y_{f'}}\ast x_f$$
• 3° calculate the gradients of the inputs with respect to the loss (necessary for the layer before this convolution layer to do backprop as well) which can also be done using a convolution: $$\frac{\partial L}{\partial x_f} = \frac{\partial L}{\partial y_{f'}}\ast w_{f'f}^{T}$$