how to do fourier frequency matrix multiplication if size is different?

Question

sorry this is not a program issue.

I just get confused for this Theory:

The FFT of a convolution is equal to the multiplication of their own's FFT.

i.e.:

FFT(conv(x,y)) = FFT(x) * FFT(y)

for the left side: lets say i have a image with 100x100 size and kernel 3x3, if I convolve, i will get a matrix of 98x98, then its FFT will also be 98x98

for the right side: if I take FFT for each I will get a frequency matrix of 3x3 and 100x100 respectively.

Then how should i do the multiplication? Some of you may say we can pad the 3x3 kernel to 100x100 and take FFT, but still we will get a matrix of 100x100 instead of 98x98?

Can someone give me some hints?

Pad the smaller image with zeroes to make it the same size as the larger image. (This also helps to avoid circular convolution.) — Paul R
Please also note that this question really belongs on dsp.stackexchange.com, not here. — Paul R

Agustin Barrachina Agustin Barrachina · Accepted Answer · 2020-07-17T16:47:51

A convolution of two signals of size L and P respectively will have a result of size N = L + N - 1. Therefore, the mathematically correct implementation of conv(x,y) will have size 102x102. You should zero pad to both x and y to make them of size 102.

When you perform the convolution as CNN convolution layers does (which is what I think you are doing) without any zero padding, you are actually cropping the result (you are leaving outside the border results). Therefore, you can just do a 102x102 fft result and crop accordingly for the 98x98 result (crop 2 at the start and 2 and the end).

ATTENTION: Unlike how zero padding usually works for Convolutional layers, for this case add zeros at the END. If not, you will be adding a shift that will be reflected in a shift in the output. ex. the expected result could be [1, 2, 3, 4] and if you apply 1 zero at the beggining and 1 at the end (instead of 2 at the end) you will have [4, 1, 2, 3].

ATTENTION 2: Not making the sizes to 102 when using iff(fft()) technique will produce something call Aliasing. This will make for example, an expected result of 30, 31, 57, 47, 87, 47, 33, 27, 5 to be 77, 64, 84, 52, 87. Note this results is actually product of making:

  30, 31, 57, 47, 87 
+ 47, 33, 27, 5
--------------------
  77, 64, 84, 52, 87

how to do fourier frequency matrix multiplication if size is different?

1 Answers