Convolution FFT implementation is referenced from Siraj Raval video:
https://www.youtube.com/watch?v=FTr3n7uBIuE

University of California, Berkeley

This node before explained how it works, and now we need to understand how to write the operation mathematically and more importantly code it efficiently. So suppose we have the input I with the shape H x H x C, where B - the batch, H - is the height and width of the image( just taking square image for the example), C - the amount of channels. One kernel k has a size of K x K x C( also taking square kernel for the sake of the example). b is the bias for that kernel

$ ( I * K)_{i,j} = \sum_{m=0}^{k-1} \sum_{n=0}^{k-1} \sum_{c=0}^{C} K_{m,n,c} I_{i + m, j + n, c} + b$
-------------------------------------------------
$ ( I * K)$ - is the output matrix for the current kernel with size of H-K+1, H-K+1. This is the variation of the Convolution with no padding and stride one. Most of the libraries call it convolution but it is actually an operation called cross-correlation. In terms of coding the formula for convolution, there are several ways to implement it. One of them might be just straight brute force with nested loops, turning everything int a big matrix multiplication, and even using Fourier transforms. While brute force solution is straight forward, other two ways are not that easy to visualize and understand


Mathematical Implementation of Forward Propagation

Here is the source that explains the implementation of the convolution operation using a large matrix multiplication:
https://sgugger.github.io/convolution-in-depth.html

Convolution in Depth

So the intuition behind this approach is to build a new matrix in which each row is each receptive field flattened. So int the end if we multiply that matrix with flattened kernel(in the same way) we get a flattened output matrix so we need just to reshape. The image shows an example of such matrix. Let's go over a code sample taken from the source(with a bit change for simplicity) that creates this matrix for a case with stride 1 and no padding
```python
import numpy as np
k1,k2 = k.shape # Kernel size(kernel k)
mb, ch, n1, n2 = x.shape # batches, channels, height and width (input x)
```
Over here we just define dimension variables
```python
start_idx = np.array([j + (n2)*i for i in range(0,n1-k1+1) for j in range(0,n2-k2+1) ])
# Output: numpy.array([1, ..., 33])
```
This is the list of all indexes that can have 0,0 index in a receptive field
```python
grid = np.array([j + (n2)*i + (n1) * (n2) * k for k in range(0,ch) for i in range(k1) for j in range(k2)])
Output: numpy.array([0, 1,2, 7,8,9,14,15, 16])
```
This means a list of indexes of a any receptive field relative to the receptive field if we would flatten it

```python
to_take = start_idx[:,None] + grid[None,:]
```
so over here we are adding each starting index to each index in the flattened receptive field related to itself and we would get the matrix where each row is the list of indexes of the receptive field(now relative to x) so now we can use numpy function take that takes an numpy array, and some list of indexes and changes those indexes for the value of this index in that numpy array

```python
batch = np.array(range(0,mb)) * ch * (n1) * (n2)
```
list of indexces of batches

```python
x.take(batch[:,None,None] + to_take[None,:,:])
```
now we using the take function so it returns the matrix we need for the convolution

Matrix Multiplication Implementation for the forward prop

Mathieu, M., Henaff, M., & LeCun, Y. (2013). Fast training of convolutional networks through ffts. arXiv preprint arXiv:1312.5851.

Fast Training of Convolutional Networks through FFTs

Convolutional Neural Networks - The Math of Intelligence (Week 4)

The Convolution theorem states that convolution of two signals is the pointwise multiplication of their Fourier transforms. So if we take an inverse of the product of two Fourier transforms we can get the convolution of two signals. So here is how it can be done in python:
```python
fft_result = np.fft.fft2(image, target_dim) * np.fft.fft2(feature, target_dim)
target = np.fft.ifft2(fft_result).real
```
And this way works a lot faster than usual implementation of the convolution

Learn Before

Related