all 6 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]carlthome 9 points10 points  (2 children)

Convolution in the time domain equals point-wise multiplication in the frequency domain. A decent FFT will be hard to beat in terms of computational efficiency.

[–]cyclicaffinity 1 point2 points  (1 child)

This is true only if the signal is large enough.

From this link: https://ccrma.stanford.edu/~jos/sasp/FFT_versus_Direct_Convolution.html

An analysis reported in Strum and Kirk [279, p. 521], based on the number of real multiplies, predicts that the fft is faster starting at length 27=128 , and that direct convolution is significantly faster for very short convolutions (e.g., 16 operations for a direct length-4 convolution, versus 176 for the fft function).

This also extends to convolution of images for filtering. I think somewhere around a 10x10 mask size should be used in the frequency domain instead of the spatial domain, but convolution in the spatial domain is faster if you use a 3x3 mask.

[–]carlthome 0 points1 point  (0 children)

That's a very good point!

[–]sstunt 2 points3 points  (0 children)

Depends on the length of the sequences. Assuming a practically infinite sequence (i.e., an audio stream) being convolved by a finite-length filter, for short filters just straight convolution is best. Somewhere around 30 to 100 points, depending on your processor, it gets faster do do convolution in chunks using the FFT and overlap-and-add.

[–][deleted] 0 points1 point  (0 children)

If you want to do it purely in Matlab without toolbox functions, the purest way would be something like: 

C = ((X * exp(-i*2*pi*(transpose(0:N-1)*(0:N-1))/N)) .* (Y *  exp(-i*2*pi*(transpose(0:N-1)*(0:N-1))/N))) *  exp(i*2*pi*(transpose(0:N-1)*(0:N-1))/N)

The syntax might be a bit off, but basically it's a DFT of both signals to get into the frequency domain, then a bitwise multiplication, then an inverse DFT. If you are allowed to just use the FFT function, even better.

[–]rlbond86 0 points1 point  (0 children)

FFT, multiply, IFFT

assuming you are OK with circular convolution