[PYTHON] CNN Acceleration Series ~ FCNN: Introduction of Fourier Convolutional Neural Network ~

Overview

With the advent of convolutional neural networks (CNNs), the field of image recognition has made great strides. Starting with AlexNet, various networks such as VGGNet and GoogLeNet have been proposed and have shown their effects. Although it is such a CNN, the drawback is that it takes a lot of time because the convolution operation is heavy. Its weight is such that the fully connected layer can be completely ignored, and if the convolution process can be accelerated, the learning time can be significantly reduced. Therefore, what is attracting attention is the relationship ** convolution in the spatial region = element product in the frequency space **. In this article, we will explain the basic theory of convolution in the frequency domain. I couldn't find any articles in Japanese, so I'm trying my best to read them from the paper. Please point out that there may be some mistakes and misunderstandings.

The papers covered in this article are

• Fast Training of Convolutional Networks through FFTs; Michael Mathieu, Mikael Henaff, Yann LeCun; arXiv:1312.5851v5 [cs.CV] 6 Mar 2014

is.

table of contents

-[What is convolution](#What is convolution) -[Linear Convolution](#Linear Convolution) -[Circular convolution](#circular convolution) -[How to equalize linear convolution and circular convolution](#How to equalize linear convolution and circular convolution) -[Convolution with CNN](Convolution with #cnn) -[To frequency domain](#To frequency domain) -[2.2 Algorithm](# 22-Algorithm) -[2.3 Implementation and Spatial Complexity](# 23-Implementation and Spatial Complexity) -[3 Experiment](# 3-Experiment) -[4 About the future](# 4-About the future) -[Try to implement?](# Try to implement) -Appendix -[Strict Convolution and CNN](# Strict Convolution and cnn) -[Cooley-Tukey FFT algorithm](# cooley-turkey-fft algorithm)

What is convolution?

In order to correctly understand the convolution in the frequency domain, let us first reconsider the convolution in the spatial domain. There are two types of convolution processing, called ** linear convolution (straight convolution) ** and ** circular convolution (circular convolution) **, respectively. First, I will explain these two.

I will introduce the variables that will be used hereafter first.

-$ I \ cdots $ Input size -$ F \ cdots $ Filter size -$ O \ cdots $ Output size

Linear convolution

Linear convolution is the convolution process shown in the figure below. In this way, it feels like starting from the point where the right edge of the filter and the left edge of the input overlap, and ending when it passes through. I won't put a mathematical formula because it's unnecessary, but please understand that it works like this. And note that this linear convolution ** the input is not a periodic function **.

In addition, the following relational expression holds for size.

O = I + F - 1

In GIF, $ I = 9 $ and $ F = 3 $, so the output size is $ O = 9 + 3-1 = 11 $.

Circular convolution

Circular convolution is the convolution process shown in the figure below. It's like starting from the point where the left edge of the filter and the left edge of the input overlap, and ending when the right edge of the filter and the right edge of the input overlap. This is exactly the difference from linear convolution, in which case the ** input must be a periodic function **. I think it's okay to understand that the input is not necessary because the input is a periodic function for each of the two ends represented by the linear convolution GIF (I think that it is strictly different, but the strictness is not particularly required. ).

In addition, the following relational expression holds for size.

O = I - F + 1

In GIF, $ I = 9 $ and $ F = 3 $, so the output size is $ O = 9 --3 + 1 = 7 $.

How to equalize linear and circular convolutions

For linear and circular convolutions to be equal, both ends of the input must be zero padded so that $ O = I + F -1 $. You can see that the output is equal to the linear convolution.

Convolution on CNN

Now, which is the convolution operation on CNN? Think from an input point of view.

The data that is input to the CNN is usually an image, which is most likely a photo. This means that it can be expected that the image will not have periodicity unless the image is recognized as a pattern. This means that the input is aperiodic, so ** CNN needs to do a linear convolution **.

But it's still too early to conclude this. Please see the figure below. This shows how CNN is folded. As you can see, the filter does not pass through the input image, so it is ** circular convolution in this figure **. This means that ** the information cannot be obtained correctly ** from the convolution operation. However, assuming that ** the input images are periodically arranged vertically and horizontally (overlapping $ F -1 $) **, this convolution can be considered correct.

I'd like to say, "Which one is it after all?", But I still have something to think about. It's ** padding **, an essential technology for CNN. There aren't enough in this figure, but ** the circular convolution can be equal to the linear convolution if you pad the required number **. Then, if the input image is correctly padded, linear convolution can be performed, and ** information can be obtained correctly from the convolution operation **. In Article I wrote before, the role of padding is "maintaining size" and "getting all the information on the edge". That's it. (At the time of writing, I didn't think about that as much as dew, but lol)

Now, this process of padding makes the discussion even more complicated. Even more considering the stride peculiar to convolution on CNN ... This padding is often used ** to prevent (or reduce) the size attenuation of the output image due to convolution in the CNN. Therefore, the padding width increases or decreases depending on the stride, so we do not want to make the circular convolution a linear convolution at all. Then, the padding width will be excessive or insufficient. There is no problem if the padding width is large, but if it is small, the conversion to circular convolution $ \ rightarrow $ linear convolution will not be performed correctly.

After all, the conclusion is ** "Convolution on CNN is between linear / circular convolution" **. It seems like "I'm pulling this much and the conclusion is ambiguous", but it can't be helped because I can only say so. When it comes to theoretically rigorous discussions, it's actually different from the premise.

This is the premise. From here, we will finally move on to the theory in the frequency domain. By the way, if you are wondering "what is the mathematical rigor?", See [Appendix](#Strict convolution and cnn).

To the frequency domain

By the way, the story so far is a summary of the results of my research here and there, which I felt was necessary while reading the dissertation. It's still sweet, but I think it's okay if you have this much in mind. Now it's time to get into the content of the dissertation. The Backpropagation in Paper 2.1 only describes the part that compares the CNN in the spatial domain with the CNN in the frequency domain, so I will cut it and read from 2.2. By the way, the dissertation is not translated into Japanese but translated and added. The figures in this section are quoted from the paper.

2.2 Algorithm

It is well known that the convolution operation in the spatial domain is equivalent to the element product in the Fourier (frequency) domain **. Therefore, the convolution operation in the spatial region uses the Fourier transform $ \ mathcal {F} $ and its inverse operation $ \ mathcal {F} ^ {-1} $.

f * g = \mathcal{F}^{-1}\big(\mathcal{F}_f(k) \odot \mathcal{F}_g(k)\big)

Can be expressed as. However, the symbol $ * $ represents the convolution operation in the spatial region, and the symbol $ \ otimes $ represents the element product in the matrix operation. It should be noted that due to the nature of the element product, ** $ f and g $ must be close in size (or rather equal in size) ** in order to perform the operation of the above equation. However, in general, the input (size $ I_h \ times I_w $) and the filter (size $ F_h \ times F_w $) are completely different sizes. Therefore, when implementing it, padding is required to make the input and filter sizes uniform. (May be trimmed) For simplicity of discussion, let $ I_h = I_w = I $ and $ F_h = F_w = F $. We will also size the output to $ O_h \ times O_w $, which is also represented as $ O_h = O_w = O $. Also, set the number of input channels to $ C $, the number of filters to $ M $, and the size of the mini-batch to $ B $. The computational complexity of the convolution operation in the spatial area is no padding, stride $ 1 $

O^2 F^2 \quad (\because O = I - F + 1)

It will be. If the padding width is $ 2p $ and the stride is $ s $

O^2 F^2 \quad \left(\because O = \left\lceil \cfrac{I - F + 2p}{s} \right\rceil + 1 \right)

is not it.

On the other hand, the amount of calculation in the Fourier domain is $ 2C_ {order} O ^ 2 \ log {O} $ when the Fourier transform is performed by ** Fast Fourier Transformation (FFT) **, and the element product The amount of computation for is expressed as ** Note that it is a complex operation ** and $ 4O ^ 2 $. $ C_ {order} $ is a constant. Therefore, the sum of $ 2C_ {order} O ^ 2 \ log {O} + 4O ^ 2 $ is the computational complexity of the convolution operation in the Fourier region. It seems that $ O = I $ in the paper.

Each input channel and filter is independent, so you only need to perform one Fourier transform on each. Learning efficiency can be reduced for certain convolutions, but the FFT can be reused effectively, which can outweigh the overhead of reduced efficiency.

Computational complexity for forward and back propagation makes the advantage of convolution operations in the Fourier region more apparent.

It should be noted that the $ O $ here is $ O = I --F + 1 $ or $ O = \ left \ lceil \ cfrac {I --F + 2p} {s in both the spatial domain and the frequency domain. } \ right \ rceil + 1 $ means that it is calculated. Note that ** is different from the previous discussion, especially in the Fourier region **. Probably, it is arranged to make a correct comparison of computational complexity.

As can be read from this table, ** the complexity in the spatial region is represented by the product of 5 terms **, while the complexity in the Fourier region is represented by the product of up to 4 terms **. It means that it is represented. Roughly speaking, the order of complexity is 5th (more accurately 7th) in the spatial domain and 4th (more accurately 5th) in the Fourier domain. Let's actually calculate and see how much effect this will have on forward propagation.

B = 128 \quad C = 96 \\
M = 256 \quad F = 7

Assuming that $ I = 16, 64 $ is calculated, $ O = I --F + 1 = 10, 58 $, so about the spatial area

BCMO^2F^2 = 128 \times 96 \times 256 \times 10^2 \times 7^2 = 15,414,067,200 \simeq 15.4 billion\\
BCMO^2F^2 = 128 \times 96 \times 256 \times 58^2 \times 7^2 = 518,529,220,608 \simeq 518.5 billion

About the Fourier region

2C_{order}I^2(BM + BC + CM)\log{I} + 4BCMI^2 = 2 \times 16 \times 16^2 \times (128 \times 256 + 128 \times 96 + 96 \times 256) \log{16} + 4 \times 128 \times 96 \times 256 \times 16^2 = 1,581,554,875.654148 + 3,221,225,472 = 4,802,780,347.654148 \simeq 4.8 billion\\
2C_{order}I^2(BM + BC + CM)\log{I} + 4BCMI^2 = 2 \times 16 \times 64^2 \times (128 \times 256 + 128 \times 96 + 96 \times 256) \log{64} + 4 \times 128 \times 96 \times 256 \times 64^2 = 37,957,317,015.69955 + 51,539,607,552 = 89,496,924,567.69955 \simeq 89.5 billion

• Since the paper does not show how much $ C_ {order} $ was calculated, we adopted $ C_ {order} = 16 $, which roughly matches the graph.

With that feeling, the difference will widen as the input size increases.

2.3 Implementation and spatial complexity

Although the algorithm is a very simple convolution operation in the Fourier domain, there are two major problems in implementation.

1. The FFT implemented in the current GPU, mainly CUDA compatible with NVIDIA GPUs, is optimized for a limited number of FFTs with large inputs, so it is not optimal for this algorithm.
2. A large amount of memory area (spatial complexity) is required to hold the Fourier transformed filter.

The following optimizations and countermeasures have been proposed for each problem.

1. Implemented [Cooley-Turkey FFT algorithm](# cooleyturkey-fft algorithm) --Parallelization is possible in the mini-batch channel direction --Originally, 2D FFT can be parallelized in the row and column directions. --From the above, it is possible to efficiently and quickly Fourier transform a small and large amount of input with this algorithm.
2. Memory saving by reusing (overwriting) the memory used for each convolution. Also, by utilizing the fact that the Fourier transform of the real-valued input becomes a symmetric matrix, only the lower triangular matrix (or upper triangular matrix) is retained. --Re-FFT is required when calculating backpropagation due to memory reuse --The amount of memory that should be retained by holding it in a triangular matrix is $ X ^ 2 \ Rightarrow \ frac {X (X + 1)} {2} $

This is the end of the theoretical aspect. The rest is the experimental results. I wanted you to post a little more concretely what kind of calculation is progressing ... I had some questions when I tried to implement it ... Well, that area is similar to normal CNN I wonder if it should behave like this.

3 Experiment

The experiment was conducted using NVIDIA's GeForce GTX Titan GPU, comparing the CUD Conv GPU implementation with the Torch 7 machine learning environment. The accuracy obtained in the experiment is not listed, but it seems that it was within the margin of error.

Focusing on the second layer of a CNN where the number of input channels is $ C = 96 $ and the number of output channels (that is, the number of filters) is $ M = 256 , the filter size, input size, and mini-batch size of that layer are changed. The experimental results are shown in the figure below.  In most cases, the convolution operation in the Fourier region has been shown to be fast. A more remarkable advantage is recognized especially in $ \ cfrac {\ partial L} {\ partial y_M} * x_C $$, which has a large amount of time complexity. It is highly likely that this is because you are using a filter with a large filter size. Also, before applying the FFT, ** the filter is padded to the same size as the input **, which means that you can use a larger filter.

• Regarding this consideration, many of the current CNNs use a small filter size from the viewpoint of memory saving. Certainly, if the FCNN implementation remains as it is, it will consume a lot of memory anyway, so it may be ant to use a larger filter. By the way, the implementation as it is is unlikely to be used. Another memory-saving technology has been firmly established. I will write another article about that.

Next, for CNN, which was focused only on the second layer earlier, this time, focusing on the first to fifth layers, the result of the experiment by changing the mini-batch size $ B $ is shown in the figure below. .. No data has been collected because the gradient of the input layer to the input does not need to be calculated. It can be read that in most cases it boasts the fastest or second fastest speed. In addition, it can be said that FCNN is effective in almost all cases because it is the fastest in total. In addition, forward propagation is considerably faster, which suggests that ** the maximum benefit can be obtained when making inferences using a trained network **.

Finally, it is the experimental result when the pooling layer and the fully connected layer are added to the above CNN. This experiment is to see if implementation details such as padding and memory access change performance. FCNN also proved its superiority in this experiment.

4 About the future

I'll make a bullet point.

--Exploring ways to learn filters directly within the Fourier region --Exploring how to use nonlinear functions within the Fourier region --This eliminates the need for inverse conversion and makes it faster. --In the current implementation, the input image needs to be padded to a power of 2 size, so improve this. --Investigate the effect of increasing the filter size

The above is the content of the dissertation. It's a simple but powerful algorithm ~ It seems that various studies have been conducted since then.

Do you want to implement it?

I want to implement it ... but I have some doubts.

-Is it necessary to perform FFT / IFFT before and after the convolution operation? --In the schematic diagram of the paper, the number of input channels and the number of output channels are the same, but the number of output channels of the convolution layer in the spatial area should depend on the number of filters. —— Also, no matter which channel you choose to match, the problem is how to align it to that dimension.

Each of them is not specified in the paper ... It should be, but it can be read subtly, isn't it? For example, in [4 About the future](# 4-About the future)

--Explore ways to learn filters directly within the Fourier region --Exploring how to use nonlinear functions within the Fourier region --This eliminates the need for inverse conversion and makes it faster.

Because it says something like, it seems that FFT / IFFT is done only before and after the matrix product operation, or the number of channels changes in the same way as CNN in the last table of the experiment, I do not write directly However, there is a description that seems to be the case.

Also, I've been searching for and reading some later papers, but there was also a description of how to do FFT only once and execute it all in the Fourier region, so that area as well. Since I haven't studied enough including it, I will not implement it this time. I can't deny the lack of understanding about the Fourier transform.

appendix

As a bonus, I will post some mathematical things.

Strict convolution and CNN

Consider the following convolution of the input matrix $ \ boldsymbol {A} $ and the filter matrix $ \ boldsymbol {W} $. However, no padding, stride $ 1 $.

• I'm sorry if the index of the subsequent matrix elements is wrong.

\boldsymbol{A} = \left( \begin{array}[ccc]
  aa_{1, 1} & a_{1, 2} & a_{1, 3} & a_{1, 4} \\
  a_{2, 1} & a_{2, 2} & a_{2, 3} & a_{2, 4} \\
  a_{3, 1} & a_{3, 2} & a_{3, 3} & a_{3, 4} \\
  a_{4, 1} & a_{4, 2} & a_{4, 3} & a_{4, 4}
\end{array} \right) \qquad
\boldsymbol{W} = \left( \begin{array}[ccc]
  ww_{1, 1} & w_{1, 2} \\
  w_{2, 1} & w_{2, 2} \\
\end{array} \right)

The convolution result of this is as follows.

\begin{align}
  \boldsymbol{AW} &= \left( \begin{array}[ccc]
    aa_{1, 1}w_{1, 1} + a_{1, 2}w_{1, 2} + a_{2, 1}w_{2, 1} + a_{2, 2}w_{2, 2}
  & a_{1, 2}w_{1, 1} + a_{1, 3}w_{1, 2} + a_{2, 2}w_{2, 1} + a_{2, 3}w_{2, 2}
  & a_{1, 3}w_{1, 1} + a_{1, 4}w_{1, 2} +   a_{2, 3}w_{2, 1} + a_{2, 4}w_{2, 2} \\
    a_{2, 1}w_{1, 1} + a_{2, 2}w_{1, 2} + a_{3, 1}w_{2, 1} + a_{3, 2}w_{2, 2}
  & a_{2, 2}w_{1, 1} + a_{2, 3}w_{1, 2} + a_{3, 2}w_{2, 1} + a_{2, 3}w_{2, 2}
  & a_{2, 3}w_{1, 1} + a_{2, 4}w_{1, 2} + a_{3, 3}w_{2, 1} + a_{2, 4}w_{2, 2} \\
    a_{3, 1}w_{1, 1} + a_{3, 2}w_{1, 2} + a_{4, 1}w_{2, 1} + a_{4, 2}w_{2, 2}
  & a_{3, 2}w_{1, 1} + a_{3, 3}w_{1, 2} + a_{4, 2}w_{2, 1} + a_{4, 3}w_{2, 2}
  & a_{3, 3}w_{1, 1} + a_{3, 4}w_{1, 2} + a_{4, 3}w_{2, 1} + a_{4, 4}w_{2, 2}
  \end{array} \right) \\
  &= \left( \begin{array}[ccc]
    s\displaystyle\sum_{k=1}^{2}{\displaystyle\sum_{l=1}^{2}{a_{k, l}w_{k, l}}}
  & \displaystyle\sum_{k=1}^{2}{\displaystyle\sum_{l=1}^{2}{a_{k, l+1}w_{k, l}}}
  & \displaystyle\sum_{k=1}^{2}{\displaystyle\sum_{l=1}^{2}{a_{k, l+2}w_{k, l}}} \\
    \displaystyle\sum_{k=1}^{2}{\displaystyle\sum_{l=1}^{2}{a_{k+1, l}w_{k, l}}} 
  & \displaystyle\sum_{k=1}^{2}{\displaystyle\sum_{l=1}^{2}{a_{k+1, l+1}w_{k, l}}}
  & \displaystyle\sum_{k=1}^{2}{\displaystyle\sum_{l=1}^{2}{a_{k+1, l+2}w_{k, l}}} \\
    \displaystyle\sum_{k=1}^{2}{\displaystyle\sum_{l=1}^{2}{a_{k+2, l}w_{k, l}}}
  & \displaystyle\sum_{k=1}^{2}{\displaystyle\sum_{l=1}^{2}{a_{k+2, l+1}w_{k, l}}}
  & \displaystyle\sum_{k=1}^{2}{\displaystyle\sum_{l=1}^{2}{a_{k+2, l+2}w_{k, l}}}
  \end{array} \right)
\end{align}

You can see the regularity. Let's generalize it. When the filter size is $ F_h \ times F_w $, the output $ (i, j) $ component $ o_ {i, j} $ is

o_{i, j} = \displaystyle\sum_{k=1}^{F_h}{\displaystyle\sum_{l=1}^{F_w}{a_{i+k-1, j+l-1}w_{k, l}}}

Can be written as. Please note that the order of addition of subscripts has been changed for later.

This is the convolution operation on the CNN. It's a circular convolution. By the way, mathematically, the two-dimensional discrete convolution operation is expressed by the following equation.

(g * f)_{i, j} = o_{i, j} = \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{i-k+1, j-l+1}g_{k, l}}}

Somehow, $ f $ is entered, $ g $ is regarded as a filter, and the order is reversed from the general formula. Also, $ k and l $ take all values for which the index is valid. At this point, those who think "that?" Are sharp. If you write this in a matrix (the sizes will be the same for CNN)

\begin{align}
  \boldsymbol{g*f} &=　\left( \begin{array}[ccc]
    s\displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{2-k, 2-l}g_{k, l}}}
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{2-k, 3-l}g_{k, l}}}
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{2-k, 4-l}g_{k, l}}} 
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{2-k, 5-l}g_{k, l}}} 
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{2-k, 6-l}g_{k, l}}} \\
    \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{3-k, 2-l}g_{k, l}}}
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{3-k, 3-l}g_{k, l}}}
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{3-k, 4-l}g_{k, l}}} 
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{3-k, 5-l}g_{k, l}}} 
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{3-k, 6-l}g_{k, l}}} \\
  \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{4-k, 2-l}g_{k, l}}}
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{4-k, 3-l}g_{k, l}}}
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{4-k, 4-l}g_{k, l}}} 
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{4-k, 5-l}g_{k, l}}} 
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{4-k, 6-l}g_{k, l}}} \\
  \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{5-k, 2-l}g_{k, l}}}
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{5-k, 3-l}g_{k, l}}}
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{5-k, 4-l}g_{k, l}}} 
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{5-k, 5-l}g_{k, l}}} 
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{5-k, 6-l}g_{k, l}}} \\
\displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{6-k, 2-l}g_{k, l}}}
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{6-k, 3-l}g_{k, l}}}
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{6-k, 4-l}g_{k, l}}} 
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{6-k, 5-l}g_{k, l}}} 
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{6-k, 6-l}g_{k, l}}} \\
  \end{array} \right) \\
  &= \left( \begin{array}[ccccc]
    ff_{1, 1}g_{1, 1}
  & f_{1, 2}g_{1, 1} + f_{1, 1}g_{1, 2}
  & f_{1, 3}g_{1, 1} + f_{1, 2}g_{1, 2}
  & f_{1, 4}g_{1, 1} + f_{1, 3}g_{1, 2}
  & f_{1, 4}g_{1, 2} \\
    f_{2, 1}g_{1, 1} + f_{1, 1}g_{2, 1}
  & f_{2, 2}g_{1, 1} + f_{2, 1}g_{1, 2} + f_{1, 2}g_{2, 1} + f_{1, 1}g_{2, 2}
  & f_{2, 3}g_{1, 1} + f_{2, 2}g_{1, 2} + f_{1, 3}g_{2, 1} + f_{1, 2}g_{2, 2}
  & f_{2, 4}g_{1, 1} + f_{2, 3}g_{1, 2} + f_{1, 4}g_{2, 1} + f_{1, 3}g_{2, 2}
  & f_{2, 4}g_{1, 2} + f_{1, 4}g_{2, 2} \\
    f_{3, 1}g_{1, 1} + f_{2, 1}g_{2, 1}
  & f_{3, 2}g_{1, 1} + f_{3, 1}g_{1, 2} + f_{2, 2}g_{2, 1} + f_{2, 1}g_{2, 2}
  & f_{3, 3}g_{1, 1} + f_{3, 2}g_{1, 2} + f_{2, 3}g_{2, 1} + f_{2, 2}g_{2, 2}
  & f_{3, 4}g_{1, 1} + f_{3, 3}g_{1, 2} + f_{2, 4}g_{2, 1} + f_{2, 3}g_{2, 2}
  & f_{3, 4}g_{1, 2} + f_{2, 4}g_{2, 2} \\
    f_{4, 1}g_{1, 1} + f_{3, 1}g_{2, 1}
  & f_{4, 2}g_{1, 1} + f_{4, 1}g_{1, 2} + f_{3, 2}g_{2, 1} + f_{3, 1}g_{2, 2}
  & f_{4, 3}g_{1, 1} + f_{4, 2}g_{1, 2} + f_{3, 3}g_{2, 1} + f_{3, 2}g_{2, 2}
  & f_{4, 4}g_{1, 1} + f_{4, 3}g_{1, 2} + f_{3, 4}g_{2, 1} + f_{3, 3}g_{2, 2}
  & f_{4, 4}g_{1, 2} + f_{3, 4}g_{2, 2} \\
    f_{4, 1}g_{2, 1}
  & f_{4, 2}g_{2, 1} + f_{4, 1}g_{2, 2}
  & f_{4, 3}g_{2, 1} + f_{4, 2}g_{2, 2}
  & f_{4, 4}g_{2, 1} + f_{4, 3}g_{2, 2}
  & f_{4, 4}g_{2, 2}
  \end{array} \right) \\
\end{align}

It will be.

As you can see at a glance, the convolution in CNN and the convolution defined in mathematics are different. This difference is the difference between circular convolution and linear convolution ... ** but it's actually different **. Even if you apply ** padding, it will not be the same ** as in the [How to equalize linear convolution and circular convolution](#How to equalize linear convolution and circular convolution) introduced earlier. I will actually try it.

\boldsymbol{A} = \left( \begin{array}[cccccc]
  00 & 0 & 0 & 0 & 0 & 0 \\
  0& a_{1, 1} & a_{1, 2} & a_{1, 3} & a_{1, 4} & 0 \\
  0 & a_{2, 1} & a_{2, 2} & a_{2, 3} & a_{2, 4} & 0 \\
  0 & a_{3, 1} & a_{3, 2} & a_{3, 3} & a_{3, 4} & 0 \\
  0 & a_{4, 1} & a_{4, 2} & a_{4, 3} & a_{4, 4} & 0 \\
  0 & 0 & 0 & 0 & 0 & 0
\end{array} \right)

As

\boldsymbol{AW} = \left( \begin{array}[ccccc]
    aa_{1, 1}w_{2, 2}
  & a_{1, 1}w_{2, 1} + a_{1, 2}w_{2, 2}
  & a_{1, 2}w_{2, 1} + a_{1, 3}w_{2, 2}
  & a_{1, 3}w_{2, 1} + a_{1, 4}w_{2, 2} 
  & a_{1, 4}w_{2, 1} \\
    a_{1, 1}w_{1, 2} + a_{2, 1}w_{2, 2}
  & a_{1, 1}w_{1, 1} + a_{1, 2}w_{1, 2} + a_{2, 1}w_{2, 1} + a_{2, 2}w_{2, 2}
  & a_{1, 2}w_{1, 1} + a_{1, 3}w_{1, 2} + a_{2, 2}w_{2, 1} + a_{2, 3}w_{2, 2}
  & a_{1, 3}w_{1, 1} + a_{1, 4}w_{1, 2} + a_{2, 3}w_{2, 1} + a_{2, 4}w_{2, 2}
  & a_{1, 4}w_{1, 1} + a_{2, 4}w_{2, 1} \\
    a_{2, 1}w_{1, 2} + a_{3, 1}w_{2, 2}
  & a_{2, 1}w_{1, 1} + a_{2, 2}w_{1, 2} + a_{3, 1}w_{2, 1} + a_{3, 2}w_{2, 2}
  & a_{2, 2}w_{1, 1} + a_{2, 3}w_{1, 2} + a_{3, 2}w_{2, 1} + a_{3, 3}w_{2, 2}
  & a_{2, 3}w_{1, 1} + a_{2, 4}w_{1, 2} + a_{3, 3}w_{2, 1} + a_{3, 4}w_{2, 2}
  & a_{2, 4}w_{1, 1} + a_{3, 4}w_{2, 1} \\
    a_{3, 1}w_{1, 2} + a_{4, 1}w_{2, 2}
  & a_{3, 1}w_{1, 1} + a_{3, 2}w_{1, 2} + a_{4, 1}w_{2, 1} + a_{4, 2}w_{2, 2}
  & a_{3, 2}w_{1, 1} + a_{3, 3}w_{1, 2} + a_{4, 2}w_{2, 1} + a_{4, 3}w_{2, 2}
  & a_{3, 3}w_{1, 1} + a_{3, 4}w_{1, 2} + a_{4, 3}w_{2, 1} + a_{4, 4}w_{2, 2}
  & a_{3, 4}w_{1, 1} + a_{4, 4}w_{2, 1} \\
    a_{4, 1}w_{1, 2}
  & a_{4, 1}w_{1, 1} + a_{4, 2}w_{1, 2}
  & a_{4, 2}w_{1, 1} + a_{4, 3}w_{1, 2}
  & a_{4, 3}w_{1, 1} + a_{4, 4}w_{1, 2}
  & a_{4, 4}w_{1, 1}
\end{array} \right)

It will be. The shapes match, the number of additions for each element is the same, but the indexes are different. This means that ** CNN convolution is a separate operation from the mathematically defined convolution **.

This was a glimpse in the convolution of this article

When it comes to theoretically rigorous discussions, it's actually different from the premise.

That is. In the first place ** the premise that "CNN convolution is a mathematical convolution" was wrong **.

You may be wondering, "So what kind of definition is mathematically the convolution of CNN, or is there a corresponding mathematical definition?", But there is a proper mathematical definition for this. ** Mutual relationship **.

(g \star f)_{i, j} = o_{i, j} = \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{i+k-1, j+l-1}g_{k, l}}}

As with the mathematical convolution, $ k and l $ take all values that are valid indexes. This is a definition similar to CNN convolution, so you can imagine the same result.

This cross-correlation calculates how similar the two signals ($ f $ and $ g $) are. Since it is not so relevant, I will leave it to the reference site for details, but in other words, the CNN filter is similar to the specific pattern of input. You are learning the distribution function that you are using.

The important thing here is ** whether we can somehow bring the cross-correlation into a mathematical convolution **. The process of convolution, which used to be the norm, was not actually convolution, but it would cover the basis of the discussion, and it would be necessary to reconsider everything. Researchers who have been thinking hard about interpreting filters will cry ...

Let's compare the mathematical convolution with the CNN convolution when padding.

\left( \begin{array}[ccccc]
  ff_{1, 1}g_{1, 1}
& f_{1, 2}g_{1, 1} + f_{1, 1}g_{1, 2}
& f_{1, 3}g_{1, 1} + f_{1, 2}g_{1, 2}
& f_{1, 4}g_{1, 1} + f_{1, 3}g_{1, 2}
& f_{1, 4}g_{1, 2} \\
  f_{2, 1}g_{1, 1} + f_{1, 1}g_{2, 1}
& f_{2, 2}g_{1, 1} + f_{2, 1}g_{1, 2} + f_{1, 2}g_{2, 1} + f_{1, 1}g_{2, 2}
& f_{2, 3}g_{1, 1} + f_{2, 2}g_{1, 2} + f_{1, 3}g_{2, 1} + f_{1, 2}g_{2, 2}
& f_{2, 4}g_{1, 1} + f_{2, 3}g_{1, 2} + f_{1, 4}g_{2, 1} + f_{1, 3}g_{2, 2}
& f_{2, 4}g_{1, 2} + f_{1, 4}g_{2, 2} \\
  f_{3, 1}g_{1, 1} + f_{2, 1}g_{2, 1}
& f_{3, 2}g_{1, 1} + f_{3, 1}g_{1, 2} + f_{2, 2}g_{2, 1} + f_{2, 1}g_{2, 2}
& f_{3, 3}g_{1, 1} + f_{3, 2}g_{1, 2} + f_{2, 3}g_{2, 1} + f_{2, 2}g_{2, 2}
& f_{3, 4}g_{1, 1} + f_{3, 3}g_{1, 2} + f_{2, 4}g_{2, 1} + f_{2, 3}g_{2, 2}
& f_{3, 4}g_{1, 2} + f_{2, 4}g_{2, 2} \\
  f_{4, 1}g_{1, 1} + f_{3, 1}g_{2, 1}
& f_{4, 2}g_{1, 1} + f_{4, 1}g_{1, 2} + f_{3, 2}g_{2, 1} + f_{3, 1}g_{2, 2}
& f_{4, 3}g_{1, 1} + f_{4, 2}g_{1, 2} + f_{3, 3}g_{2, 1} + f_{3, 2}g_{2, 2}
& f_{4, 4}g_{1, 1} + f_{4, 3}g_{1, 2} + f_{3, 4}g_{2, 1} + f_{3, 3}g_{2, 2}
& f_{4, 4}g_{1, 2} + f_{3, 4}g_{2, 2} \\
  f_{4, 1}g_{2, 1}
& f_{4, 2}g_{2, 1} + f_{4, 1}g_{2, 2}
& f_{4, 3}g_{2, 1} + f_{4, 2}g_{2, 2}
& f_{4, 4}g_{2, 1} + f_{4, 3}g_{2, 2}
& f_{4, 4}g_{2, 2}
\end{array} \right) \\
\left( \begin{array}[ccccc]
    aa_{1, 1}w_{2, 2}
  & a_{1, 1}w_{2, 1} + a_{1, 2}w_{2, 2}
  & a_{1, 2}w_{2, 1} + a_{1, 3}w_{2, 2}
  & a_{1, 3}w_{2, 1} + a_{1, 4}w_{2, 2} 
  & a_{1, 4}w_{2, 1} \\
    a_{1, 1}w_{1, 2} + a_{2, 1}w_{2, 2}
  & a_{1, 1}w_{1, 1} + a_{1, 2}w_{1, 2} + a_{2, 1}w_{2, 1} + a_{2, 2}w_{2, 2}
  & a_{1, 2}w_{1, 1} + a_{1, 3}w_{1, 2} + a_{2, 2}w_{2, 1} + a_{2, 3}w_{2, 2}
  & a_{1, 3}w_{1, 1} + a_{1, 4}w_{1, 2} + a_{2, 3}w_{2, 1} + a_{2, 4}w_{2, 2}
  & a_{1, 4}w_{1, 1} + a_{2, 4}w_{2, 1} \\
    a_{2, 1}w_{1, 2} + a_{3, 1}w_{2, 2}
  & a_{2, 1}w_{1, 1} + a_{2, 2}w_{1, 2} + a_{3, 1}w_{2, 1} + a_{3, 2}w_{2, 2}
  & a_{2, 2}w_{1, 1} + a_{2, 3}w_{1, 2} + a_{3, 2}w_{2, 1} + a_{3, 3}w_{2, 2}
  & a_{2, 3}w_{1, 1} + a_{2, 4}w_{1, 2} + a_{3, 3}w_{2, 1} + a_{3, 4}w_{2, 2}
  & a_{2, 4}w_{1, 1} + a_{3, 4}w_{2, 1} \\
    a_{3, 1}w_{1, 2} + a_{4, 1}w_{2, 2}
  & a_{3, 1}w_{1, 1} + a_{3, 2}w_{1, 2} + a_{4, 1}w_{2, 1} + a_{4, 2}w_{2, 2}
  & a_{3, 2}w_{1, 1} + a_{3, 3}w_{1, 2} + a_{4, 2}w_{2, 1} + a_{4, 3}w_{2, 2}
  & a_{3, 3}w_{1, 1} + a_{3, 4}w_{1, 2} + a_{4, 3}w_{2, 1} + a_{4, 4}w_{2, 2}
  & a_{3, 4}w_{1, 1} + a_{4, 4}w_{2, 1} \\
    a_{4, 1}w_{1, 2}
  & a_{4, 1}w_{1, 1} + a_{4, 2}w_{1, 2}
  & a_{4, 2}w_{1, 1} + a_{4, 3}w_{1, 2}
  & a_{4, 3}w_{1, 1} + a_{4, 4}w_{1, 2}
  & a_{4, 4}w_{1, 1}
\end{array} \right)

Doesn't it feel cool? For example

\left( \begin{array}[ccc]
  gg_{1, 1} & g_{1, 2} \\
  g_{2, 1} & g_{2, 2} \\
\end{array} \right)
= \left( \begin{array}[ccc]
  ww_{2, 2} & w_{2, 1} \\
  w_{1, 2} & w_{1, 1} \\
\end{array} \right)

What do you do

\left( \begin{array}[ccccc]
  ff_{1, 1}g_{1, 1}
& f_{1, 2}g_{1, 1} + f_{1, 1}g_{1, 2}
& f_{1, 3}g_{1, 1} + f_{1, 2}g_{1, 2}
& f_{1, 4}g_{1, 1} + f_{1, 3}g_{1, 2}
& f_{1, 4}g_{1, 2} \\
  f_{2, 1}g_{1, 1} + f_{1, 1}g_{2, 1}
& f_{2, 2}g_{1, 1} + f_{2, 1}g_{1, 2} + f_{1, 2}g_{2, 1} + f_{1, 1}g_{2, 2}
& f_{2, 3}g_{1, 1} + f_{2, 2}g_{1, 2} + f_{1, 3}g_{2, 1} + f_{1, 2}g_{2, 2}
& f_{2, 4}g_{1, 1} + f_{2, 3}g_{1, 2} + f_{1, 4}g_{2, 1} + f_{1, 3}g_{2, 2}
& f_{2, 4}g_{1, 2} + f_{1, 4}g_{2, 2} \\
  f_{3, 1}g_{1, 1} + f_{2, 1}g_{2, 1}
& f_{3, 2}g_{1, 1} + f_{3, 1}g_{1, 2} + f_{2, 2}g_{2, 1} + f_{2, 1}g_{2, 2}
& f_{3, 3}g_{1, 1} + f_{3, 2}g_{1, 2} + f_{2, 3}g_{2, 1} + f_{2, 2}g_{2, 2}
& f_{3, 4}g_{1, 1} + f_{3, 3}g_{1, 2} + f_{2, 4}g_{2, 1} + f_{2, 3}g_{2, 2}
& f_{3, 4}g_{1, 2} + f_{2, 4}g_{2, 2} \\
  f_{4, 1}g_{1, 1} + f_{3, 1}g_{2, 1}
& f_{4, 2}g_{1, 1} + f_{4, 1}g_{1, 2} + f_{3, 2}g_{2, 1} + f_{3, 1}g_{2, 2}
& f_{4, 3}g_{1, 1} + f_{4, 2}g_{1, 2} + f_{3, 3}g_{2, 1} + f_{3, 2}g_{2, 2}
& f_{4, 4}g_{1, 1} + f_{4, 3}g_{1, 2} + f_{3, 4}g_{2, 1} + f_{3, 3}g_{2, 2}
& f_{4, 4}g_{1, 2} + f_{3, 4}g_{2, 2} \\
  f_{4, 1}g_{2, 1}
& f_{4, 2}g_{2, 1} + f_{4, 1}g_{2, 2}
& f_{4, 3}g_{2, 1} + f_{4, 2}g_{2, 2}
& f_{4, 4}g_{2, 1} + f_{4, 3}g_{2, 2}
& f_{4, 4}g_{2, 2}
\end{array} \right) \\
= \left( \begin{array}[ccccc]
  ff_{1, 1}w_{2, 2}
& f_{1, 2}w_{2, 2} + f_{1, 1}w_{2, 1}
& f_{1, 3}w_{2, 2} + f_{1, 2}w_{2, 1}
& f_{1, 4}w_{2, 2} + f_{1, 3}w_{2, 1}
& f_{1, 4}w_{2, 1} \\
  f_{2, 1}w_{2, 2} + f_{1, 1}w_{1, 2}
& f_{2, 2}w_{2, 2} + f_{2, 1}w_{2, 1} + f_{1, 2}w_{1, 2} + f_{1, 1}w_{1, 1}
& f_{2, 3}w_{2, 2} + f_{2, 2}w_{2, 1} + f_{1, 3}w_{1, 2} + f_{1, 2}w_{1, 1}
& f_{2, 4}w_{2, 2} + f_{2, 3}w_{2, 1} + f_{1, 4}w_{1, 2} + f_{1, 3}w_{1, 1}
& f_{2, 4}w_{2, 1} + f_{1, 4}w_{1, 1} \\
  f_{3, 1}w_{2, 2} + f_{2, 1}w_{1, 2}
& f_{3, 2}w_{2, 2} + f_{3, 1}w_{2, 1} + f_{2, 2}w_{1, 2} + f_{2, 1}w_{1, 1}
& f_{3, 3}w_{2, 2} + f_{3, 2}w_{2, 1} + f_{2, 3}w_{1, 2} + f_{2, 2}w_{1, 1}
& f_{3, 4}w_{2, 2} + f_{3, 3}w_{2, 1} + f_{2, 4}w_{1, 2} + f_{2, 3}w_{1, 1}
& f_{3, 4}w_{2, 1} + f_{2, 4}w_{1, 1} \\
  f_{4, 1}w_{2, 2} + f_{3, 1}w_{1, 2}
& f_{4, 2}w_{2, 2} + f_{4, 1}w_{2, 1} + f_{3, 2}w_{1, 2} + f_{3, 1}w_{1, 1}
& f_{4, 3}w_{2, 2} + f_{4, 2}w_{2, 1} + f_{3, 3}w_{1, 2} + f_{3, 2}w_{1, 1}
& f_{4, 4}w_{2, 2} + f_{4, 3}w_{2, 1} + f_{3, 4}w_{1, 2} + f_{3, 3}w_{1, 1}
& f_{4, 4}w_{2, 1} + f_{3, 4}w_{1, 1} \\
  f_{4, 1}w_{1, 2}
& f_{4, 2}w_{1, 2} + f_{4, 1}w_{1, 1}
& f_{4, 3}w_{1, 2} + f_{4, 2}w_{1, 1}
& f_{4, 4}w_{1, 2} + f_{4, 3}w_{1, 1}
& f_{4, 4}w_{1, 1}
\end{array} \right) \\
\underbrace{=}_{Change the order of addition}
\left( \begin{array}[ccccc]
    ff_{1, 1}w_{2, 2}
  & f_{1, 1}w_{2, 1} + f_{1, 2}w_{2, 2}
  & f_{1, 2}w_{2, 1} + f_{1, 3}w_{2, 2}
  & f_{1, 3}w_{2, 1} + f_{1, 4}w_{2, 2} 
  & f_{1, 4}w_{2, 1} \\
    f_{1, 1}w_{1, 2} + f_{2, 1}w_{2, 2}
  & f_{1, 1}w_{1, 1} + f_{1, 2}w_{1, 2} + f_{2, 1}w_{2, 1} + f_{2, 2}w_{2, 2}
  & f_{1, 2}w_{1, 1} + f_{1, 3}w_{1, 2} + f_{2, 2}w_{2, 1} + f_{2, 3}w_{2, 2}
  & f_{1, 3}w_{1, 1} + f_{1, 4}w_{1, 2} + f_{2, 3}w_{2, 1} + f_{2, 4}w_{2, 2}
  & f_{1, 4}w_{1, 1} + f_{2, 4}w_{2, 1} \\
    f_{2, 1}w_{1, 2} + f_{3, 1}w_{2, 2}
  & f_{2, 1}w_{1, 1} + f_{2, 2}w_{1, 2} + f_{3, 1}w_{2, 1} + f_{3, 2}w_{2, 2}
  & f_{2, 2}w_{1, 1} + f_{2, 3}w_{1, 2} + f_{3, 2}w_{2, 1} + f_{3, 3}w_{2, 2}
  & f_{2, 3}w_{1, 1} + f_{2, 4}w_{1, 2} + f_{3, 3}w_{2, 1} + f_{3, 4}w_{2, 2}
  & f_{2, 4}w_{1, 1} + f_{3, 4}w_{2, 1} \\
    f_{3, 1}w_{1, 2} + f_{4, 1}w_{2, 2}
  & f_{3, 1}w_{1, 1} + f_{3, 2}w_{1, 2} + f_{4, 1}w_{2, 1} + f_{4, 2}w_{2, 2}
  & f_{3, 2}w_{1, 1} + f_{3, 3}w_{1, 2} + f_{4, 2}w_{2, 1} + f_{4, 3}w_{2, 2}
  & f_{3, 3}w_{1, 1} + f_{3, 4}w_{1, 2} + f_{4, 3}w_{2, 1} + f_{4, 4}w_{2, 2}
  & f_{3, 4}w_{1, 1} + f_{4, 4}w_{2, 1} \\
    f_{4, 1}w_{1, 2}
  & f_{4, 1}w_{1, 1} + f_{4, 2}w_{1, 2}
  & f_{4, 2}w_{1, 1} + f_{4, 3}w_{1, 2}
  & f_{4, 3}w_{1, 1} + f_{4, 4}w_{1, 2}
  & f_{4, 4}w_{1, 1}
\end{array} \right) \\
\Leftrightarrow
\left( \begin{array}[ccccc]
    aa_{1, 1}w_{2, 2}
  & a_{1, 1}w_{2, 1} + a_{1, 2}w_{2, 2}
  & a_{1, 2}w_{2, 1} + a_{1, 3}w_{2, 2}
  & a_{1, 3}w_{2, 1} + a_{1, 4}w_{2, 2} 
  & a_{1, 4}w_{2, 1} \\
    a_{1, 1}w_{1, 2} + a_{2, 1}w_{2, 2}
  & a_{1, 1}w_{1, 1} + a_{1, 2}w_{1, 2} + a_{2, 1}w_{2, 1} + a_{2, 2}w_{2, 2}
  & a_{1, 2}w_{1, 1} + a_{1, 3}w_{1, 2} + a_{2, 2}w_{2, 1} + a_{2, 3}w_{2, 2}
  & a_{1, 3}w_{1, 1} + a_{1, 4}w_{1, 2} + a_{2, 3}w_{2, 1} + a_{2, 4}w_{2, 2}
  & a_{1, 4}w_{1, 1} + a_{2, 4}w_{2, 1} \\
    a_{2, 1}w_{1, 2} + a_{3, 1}w_{2, 2}
  & a_{2, 1}w_{1, 1} + a_{2, 2}w_{1, 2} + a_{3, 1}w_{2, 1} + a_{3, 2}w_{2, 2}
  & a_{2, 2}w_{1, 1} + a_{2, 3}w_{1, 2} + a_{3, 2}w_{2, 1} + a_{3, 3}w_{2, 2}
  & a_{2, 3}w_{1, 1} + a_{2, 4}w_{1, 2} + a_{3, 3}w_{2, 1} + a_{3, 4}w_{2, 2}
  & a_{2, 4}w_{1, 1} + a_{3, 4}w_{2, 1} \\
    a_{3, 1}w_{1, 2} + a_{4, 1}w_{2, 2}
  & a_{3, 1}w_{1, 1} + a_{3, 2}w_{1, 2} + a_{4, 1}w_{2, 1} + a_{4, 2}w_{2, 2}
  & a_{3, 2}w_{1, 1} + a_{3, 3}w_{1, 2} + a_{4, 2}w_{2, 1} + a_{4, 3}w_{2, 2}
  & a_{3, 3}w_{1, 1} + a_{3, 4}w_{1, 2} + a_{4, 3}w_{2, 1} + a_{4, 4}w_{2, 2}
  & a_{3, 4}w_{1, 1} + a_{4, 4}w_{2, 1} \\
    a_{4, 1}w_{1, 2}
  & a_{4, 1}w_{1, 1} + a_{4, 2}w_{1, 2}
  & a_{4, 2}w_{1, 1} + a_{4, 3}w_{1, 2}
  & a_{4, 3}w_{1, 1} + a_{4, 4}w_{1, 2}
  & a_{4, 4}w_{1, 1}
\end{array} \right)

And became the same! What this means is that ** cross-correlation and mathematical convolution can hopefully be the same operation **. In this case, "do well" is index inversion if discrete, plus or minus inversion if continuous.

So you can think of CNN's filters as learning an inverted convolution filter, and researchers don't have to cry.

Cooley-Tukey FFT algorithm

First, let's check the definition of the discrete Fourier transform in the first place. For simplicity, consider a one-dimensional vector $ \ boldsymbol {x} $ with a length of $ N $ as a discrete Fourier transform.

X_k = \mathcal{F}_{\boldsymbol{x}}(k) = \sum_{p=0}^{N-1}{x_p e^{-j\frac{2 \pi}{N}kp}} = \sum_{p=0}^{N-1}{x_p W_N^{kp}} \quad k = 0, 1, \ldots N-1 \\
W_N^{kp} = e^{-j\frac{2 \pi}{N}}

It will be. Here, the imaginary symbol is $ j $. Also, $ W_N = e ^ {-j \ frac {2 \ pi} {N}} $ is called ** turn factor **. The reason will be described later. This complexity is $ \ mathcal {O} (N ^ 2) $, but this calculation can be speeded up assuming $ N $ is even. The algorithm is called ** FFT: Fast Fourier Transformation ** and can be expressed as:

\begin{align}
  X_{2k} = \mathcal{F}_{\boldsymbol{x}}(2k) &= \sum_{p=0}^{N-1}{x_p W_N^{2kp}} & \\
  &= \sum_{p=0}^{N-1}{x_p W_{N/2}^{kp}} & (\because W_N^{2kp} = e^{-j\frac{2 \pi}{N}2kp} = e^{-j\frac{2 \pi}{N/2}kp} = W_{N/2}^{kp}) \\
  &= \sum_{p=0}^{N/2-1}{x_p W_{N/2}^{kp}} + \sum_{p=N/2}^{N-1}{x_p W_{N/2}^{kp}} & (\because divided into the first half and the second half, W_{N/2}^{kp}Number of elements\frac{N}{2}To match) \\
  &= \sum_{p=0}^{N/2-1}{x_p W_{N/2}^{kp}} + \sum_{p=0}^{N/2-1}{x_{p+N/2} W_{N/2}^{k(p+N/2)}} & (\because the sum of the latter half is p=Shift to 0 start) \\
  &= \sum_{p=0}^{N/2-1}{x_p W_{N/2}^{kp}} + \sum_{p=0}^{N/2-1}{x_{p+N/2} W_{N/2}^{kp}} & (\because W_{N/2}^{k(N/2)} = e^{-j\frac{2 \pi}{N/2}k(N/2)} = e^{-j2k \pi} = 1) \\
  &= \sum_{p=0}^{N/2-1}{(x_p + x_{p+N/2}) W_{N/2}^{kp}} \quad k = 0, 1, \ldots, \cfrac{N}{2} & \\

  X_{2k+1} = \mathcal{F}_{\boldsymbol{x}}(2k+1) &= \sum_{p=0}^{N-1}{x_p W_N^{(2k+1)p}} & \\
  &= \sum_{p=0}^{N-1}{x_p W_{N}^{p}W_{N/2}^{kp}} & \\
  &= \sum_{p=0}^{N/2-1}{x_p W_{N}^{p}W_{N/2}^{kp}} + \sum_{p=N/2}^{N-1}{x_p W_{N}^{p}W_{N/2}^{kp}} & \\
  &= \sum_{p=0}^{N/2-1}{x_p W_{N}^{p}W_{N/2}^{kp}} + \sum_{p=0}^{N/2-1}{x_{p+N/2} W_{N}^{p+N/2}W_{N/2}^{k(p+N/2)}} & \\
  &= \sum_{p=0}^{N/2-1}{x_p W_{N}^{p}W_{N/2}^{kp}} - \sum_{p=0}^{N/2-1}{x_{p+N/2} W_{N}^{p}W_{N/2}^{kp}} & \\
  &= \sum_{p=0}^{N/2-1}{(x_p - x_{p+N/2}) W_{N}^{p} W_{N/2}^{kp}} \quad k = 0, 1, \ldots, \cfrac{N}{2}-1 &
\end{align}

By definition, $ W $ is called a rotation factor because it represents a point on the unit circle whose rotation angle is ** clockwise ** and $ \ frac {2 \ pi} {N} $. .. Therefore, the following relational expression holds.

W_{2n}^{kn} = e^{-j\frac{2 \pi}{2n}kn} = e^{-j k \pi} = (-1)^k

In short, this relational expression is the value when the rotation angle is $ k \ pi $. This formula is used everywhere to transform the FFT formula.

e^{jx} = \cos x + j \sin x

e^{j \pi} = \cos \pi + j \sin \pi \Leftrightarrow e^{j \pi} = -1 + j0 \\
\therefore e^{j \pi} + 1 = 0

\begin{align}
  e^{j(-k \pi)} &= \cos (-k \pi) + j \sin (-k \pi) \\
  &= (-1)^k \\
\end{align}

Recommended Posts