[Math] fft of point wise product

convolutionfourier analysisfourier transformMATLAB

I have a sequence 

  a =   [1     2     3     4     5     6     7     8],

and a weighting 

   w = [ 2     3     4     5     6     7     1     2],

Now, based on convolution theorem, the Fourier transform of point-wise multiplication of two sequences is equivalent to the convolution of the Fourier transform of the two:

$\mathcal{F}\{w \cdot a\}= \mathcal{F}\{w\}*\mathcal{F}\{a\}$

where $\cdot$ indicates point-wise multiplication, $*$ in dicates cpnvolution, and $\mathcal{F}$ indicates Fourier transform.

However, my problem is when I apply this theorem to above example, it does not seem to match the convolution theorem. I am using MATLAB, to calculate

the Fourirt transform the point-wise product of the two:

 fft(w.*a) = fft([ 2     6    12    20    30    42     7    16]) 

= 1.0e+02 *[  
     1.3500 + 0.0000i  
    -0.5628 + 0.1763i   
     0.1300 - 0.1200i  
     0.0028 + 0.2763i  
    -0.3300 + 0.0000i   
     0.0028 - 0.2763i   
     0.1300 + 0.1200i  
    -0.5628 - 0.1763i]

and the convolution of the Fourier transform of the two:

conv(fft(w),fft(a)) =

1.0e+03 * [
     1.0800 + 0.0000i  
    -0.4422 + 0.2072i   
     0.0459 - 0.0653i  
    -0.0239 + 0.1975i  
    -0.2640 + 0.0127i  
    -0.0597 - 0.2067i   
     0.0461 + 0.0187i
    -0.4503 - 0.1410i   
     0.0000 + 0.0000i  
    -0.0081 - 0.0661i   
     0.0581 - 0.0307i   
     0.0261 + 0.0235i   
     0.0000 - 0.0127i   
     0.0619 - 0.0143i
     0.0579 + 0.0773i]

Obviously,

fft(w.*a) $\neq$ conv(fft(w), fft(a)).

Therefore, from what I tested, it does not seem that the fft of the point-wise multiplication equals the convolution of the fft. I don't find an explanation. So where is the problem? Can anyone help please?

Thanks alot.

Best Answer

You need to do circular convolution.

 1. fft(w.*a) 
 2. cconv(fft(w), fft(a), 8)/8

Try above two lines in MATLAB, and you will find they generate the same results. In MATLAB, the circular convolution can be performed by cconv(). Find the explanation yourself, it is quite simple.

Basically, taking the fft of the two individually, then circularly convolve them together, restrict the length (assuming your two sequence are of same length, otherwise you zero-pad the shorter one) to be the same as the sequences, and finally inversely scale the result by the sequence length. Then you will have the same result as the fft of the point-wise product.

Related Question