Computing a convolution using FFT

Question

I have two sequences of the same length, $(x_i), i=1, 2, \ldots, N$ and $(y_i), i=1, 2, \ldots, N$ and a function $K(t) = -t \times \exp(-t^2 / 2)/ \sqrt{2 \pi}$.

I need to compute the following quantity for each $m=1, 2, \ldots, N$:

$\sum_{j=1}^N K(x_m - x_j) \times y_j$

which is a tad slow when done directly (I need it when $N = O(10^4)$ ). I know this can be much improved on with the use of FFT, however it is something I never really worked with. Could anyone suggest any links or a way to rewrite it in FFT form?

I'd be very grateful for any help :)

Answer 1

Here you have a good link.

Basically you need to compute the FFT of each signal individually, multiply the spectrums and the do the inverse FFT of the resulting sectrum. That will be the result of the convolution.

Good luck!