Answers.Body: <p>I had that same exact question when trying to develop some kind of implementation of the Conv2D using the FFT.
  To do this we need to consider that there are three steps that the layer needs to be able to do to actually be able to use it for inference and training:</p>
  <ul>
  <li>1° calculate the convolution of the input samples with all of the filters:
  <span class="math-container">$$y_{f'}=\sum_f x_f\ast w_{f'f}$$</span></li>
  <li>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:
  <span class="math-container">$$\frac{\partial L}{\partial w_{f'f}} = \frac{\partial L}{\partial y_{f'}}\ast x_f$$</span></li>
  <li>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:
  <span class="math-container">$$\frac{\partial L}{\partial x_f} = \frac{\partial L}{\partial y_{f'}}\ast w_{f'f}^{T}$$</span></li>
  </ul>
  <p>This means that since you can apply the FFT in all of these steps in the same manner you can apply in the inference step.</p>
  <p>If you want to know more you can try reading <a href="https://arxiv.org/pdf/1312.5851.pdf" rel="nofollow noreferrer">this</a> 2014 article about doing convolution with the FFT by Yann LeCunn and some of his peers.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-03-18T13:48:18.333Z
Answers.LastActivityDate: 2023-03-18T13:50:47.447Z
Answers.LastEditDate: 2023-03-18T13:50:47.447Z
Answers.UserDisplayName: Gabriel Miranda
Body: <p>CNNs (convolutional neural networks) are adept at processing images, as their construction is based on the biological neural networks found in the human eye. &quot;Kernels&quot;, sometimes called &quot;filters&quot;, are small feature detectors in the form of small matricies that are slid (called &quot;convulving&quot;) 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.</p>
  <p>Recently I found <a href="https://medium.com/analytics-vidhya/fast-cnn-substitution-of-convolution-layers-with-fft-layers-a9ed3bfdc99a" rel="nofollow noreferrer">here</a> that you can use FFT to do the convolutions up to ~4.8 times faster than with all that multiplication.</p>
  <p>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.</p>
  <p>So, how do you train the CNN kernels when using the FFT method of CNN convolutions? Is backpropagation still relevant?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-03-19T14:27:15.383Z
Comments.Text: See [my attempt](https://ai.stackexchange.com/a/38192/38980) 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.
Comments.UserDisplayName: Lutz Lehmann
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-02-02T23:47:02.490Z
Comments.Text: Have you checked the backpropagation algorithm (ref: https://brilliant.org/wiki/backpropagation/)? There is a Python code at the end. Please, check if you could apply FFT similar to that.
Comments.UserDisplayName: Cloud Cho
Tags: <convolutional-neural-networks><convolution><convolutional-layers>
Title: How are CNN kernels trained when using FFT for convolutions?
UserDisplayName: Steve Mucci
ThreadText: # How are CNN kernels trained when using FFT for convolutions?
  
  (Asked by: username_0 on 2022-04-14)
  
  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](https://medium.com/analytics-vidhya/fast-cnn-substitution-of-convolution-layers-with-fft-layers-a9ed3bfdc99a) 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?
  
  **Tags:** convolutional-neural-networks, convolution, convolutional-layers
  
  > **Comments:**
  > **username_2**: Have you checked the backpropagation algorithm (ref: https://brilliant.org/wiki/backpropagation/)? There is a Python code at the end. Please, check if you could apply FFT similar to that.  
  > **username_1**: See [my attempt](https://ai.stackexchange.com/a/38192/38980) 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.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2023-03-18. Score: 0
  
  I had that same exact question when trying to develop some kind of implementation of the Conv2D using the FFT.
  To do this we need to consider that there are three steps that the layer needs to be able to do to actually be able to use it for inference and training:
  
  * 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}$$
  
  This means that since you can apply the FFT in all of these steps in the same manner you can apply in the inference step.
  
  If you want to know more you can try reading [this](https://arxiv.org/pdf/1312.5851.pdf) 2014 article about doing convolution with the FFT by Yann LeCunn and some of his peers.
  
  
  ---
  
  