Multiplication in the Frequency Domain (ANTS Book Chapter 11.10)

Hello, I’m currently on chapter 11 in the Analyzing Neural Time Series Data book. In chapter 11.10 it is stated that the two pipelines of convolution are:

  1. Convolution(Signal, Kernel)
  2. FFT -->Multiplication of FFTs (Signal, Kernel) --> IFFT

In the latter, the code provided online shows the following:

image

It doesn’t go beyond this, and I was wondering how the multiplication is done since the Kernel is a shorter length than the signal.

Great question, Asimio! The answer is coming up in the next few chapters. I hope you don’t being patient for a bit longer, and feel free to post back if you still have questions.

1 Like

Great, looking forward to it!

Hi @MikeXCohen! I got stuck again, in the exercise section it says:

Reproduce the top three panels of figure 11.12 three times. First, perform time-domain
convolution using the “manual ” convolution method shown in chapter 10. Second, perform
frequency-domain convolution using the discrete time Fourier transform presented at the
beginning of this chapter […]

Top three panels (11.12) showing the signal, kernel and [signal convolution_result], respectively:

image

The code for the discrete time Fourier transform that I find in the script is the following:

data    = randn(1,N); % random numbers
srate   = 200;        % sampling rate in Hz
nyquist = srate/2;    % Nyquist frequency -- the highest frequency you can measure in the data


% initialize Fourier output matrix
fourier = zeros(size(data)); 

% These are the actual frequencies in Hz that will be returned by the
% Fourier transform. The number of unique frequencies we can measure is
% exactly 1/2 of the number of data points in the time series (plus DC). 
frequencies = linspace(0,nyquist,N/2+1);
time = ((1:N)-1)/N;

% Fourier transform is dot-product between sine wave and data at each frequency
for fi=1:N
    sine_wave   = exp(-1i*2*pi*(fi-1).*time);
    fourier(fi) = sum(sine_wave.*data);
end
fourier=fourier/N;

From what I understand, this question is asking for a convolution by multiplying in the frequency domain—or am I misinterpreting it?

Yes, that’s correct – frequency domain multiplication. The goal of this exercise is to provide an illustration of what’s shown in figure 11.10 (page 135).

But please don’t code the Fourier transform in the loop. That’s there to show how the FT works for educational purposes, but it’s slow and inefficient and easy to make mistakes. In practice, you should always use the FFT (MATLAB function fft() ).

1 Like

Ah okay, so the question is how do I zero-pad the kernel to get the same convolution result? I tried just adding zeros on each of the ends to make it the same size as the signal (640)

The gaussian was originally made with 513 elements:

time = -1:1/EEG.srate:1;
s = 5/(2*pi*30);
gaussian = exp((-time.^2)/(2*s^2))/30;

But when I multiply in the frequency domain I get this:

image

Green = correct convolution
Red = convolution via frequency domain

I feel the zero padding is being done incorrectly since doing the calculation via fft() and ifft() also produces the results in red.

Zero-padding in convolution is tricky, as is removing the convolution “wings.” I suggest following the book code to see how it’s done, and then adapting that code to this exercise. Hope it works out!

1 Like

Thanks for the tip. Time to hit the books! (well, singular in this case but you get the point :upside_down_face:)