I am teaching myself how to write artificial intelligence from scratch including all the math myself
I have a pretty solid understanding of a neural network and mine is working fairly well
I started teaching myself about how convolutional neural networks work and that led me to the Fast Fourier Transform Convolution which from what I'm reading is about 1000x faster than a straight convolution
So I just want to make sure I understand what I think I understand
Basis:
Straight convolution as a starting point
in a list of [1,2,3] convolved with [4, 5, 6]
the resultant convolved list is [4, 13, 28, 27, 18]
and here is my math
(1 * 4) 4
(2 * 4) + (1 * 5) 13
(1 * 6) + (2 * 5) + (3 * 4)
28
(2 * 6) + (3 * 5) 27
(6 * 3) 18
Discrete Fourier Transform
DFT[K] = SIGMA(LIST[x] * e ^ (-i * 2 * pi * k * (n / N)))
where
'K' is a sort of sigma step where you loop through each item in the list
'n' is the individual steps in each sigma step "K"
'N' is the total number of steps
code example
int [] LIST = {1, 2, 3}
var sigma = 0;
for ( int k = 0; k < N; k++) {
sigma = 0
for ( int n = 0; n < N; n++) {
sigma += LIST[n] * e ^ (-i * 2 * pi * k * (n / N)))
}
RESULT_LIST[k] = SIGMA
}
```
RESULT_LIST = {6, 0.5 - 4.33012702 i, -1.5 + 0.866025404 i}
Inverse discrete Discrete Fourier Transform
DFT[K] = (SIGMA(LIST[x] * e ^ (i * 2 * pi * k * (n / N))))/N
where
'K' is a sort of sigma step where you loop through each item in the list
'n' is the individual steps in each sigma step "K"
'N' is the total number of steps
code example
LIST = {6, 0.5 - 4.33012702 i, -1.5 + 0.866025404 i}
var sigma = 0;
for ( int k = 0; k < N; k++) {
sigma = 0
for ( int n = 0; n < N; n++) {
sigma += LIST [n] * e ^ (i * 2 * pi * k * (n / N))
}
RESULT_LIST[k] = sigma / N;
}
```
RESULT_LIST = {2, 3.33333333 - 1.15470054 i, 3.66666667 + 1.15470054 i}
To accomplish a discrete fourier transform convolution
the math im reading
DFT_Result_List_1 * DFT_Result_List_2
and to make sure its clear that is not a dot product it is element wise multiplication
RESULT_LIST = {6, 0.5 - 4.33012702 i, -1.5 + 0.866025404 i}
- RESULT_LIST = {6, 0.5 - 4.33012702 i, -1.5 + 0.866025404 i}
or
6 * 6 = 36
(0.5 - 4.33012702 i) * (0.5 - 4.33012702 i) = -18.5 - 4.33012702 i
(-1.5 + 0.866025404 i) * (-1.5 + 0.866025404 i) = 1.5 - 2.59807621 i
DFT_MULT_LIST = {36,-18.5 - 4.33012702 i, 1.5 - 2.59807621 i}
and then you take that list and run it through the Inverse DFT
This is where I get lost because when i run the above example through the IDFT
it does not remove 'i' from the list which is needed for DFT Convolution to match
the original result
a convolution should not have an i it
there is something im missing
Generally, for the different Fourier transforms, you have the convolution theorems. These theorems state the following: $\mathcal{F}( f \ast g ) = \mathcal{F}(f) \odot \mathcal{F}(g),$ where $\ast$ is convolution and $\odot$ is point-wise multiplication. You have to be careful, though, because the convolution is different based on the types of things you’re working with.
When working with vectors and using the Discrete Fourier Transform, the convolution is CIRCULAR convolution. So $f$ convolved with $g$ yields a vector the same size as $f$. When convolving, use periodic extensions. So the convolution of your calculation is inappropriate.
I hope that helps!
(You can see some details from my class notes here: https://nicholasdwork.com/teaching/1706ee102a/lectures/lecture09.pdf.)