2
$\begingroup$

Theoretically both of ways of calculating autocorrelation function are identical: strightforward convolution and Fourier-based method where we use FFT/iFFT in practice. And as it is well known, the computational complexity is $\mathcal O(N^2)$ and $\mathcal O(N\log N)$ for them respectively.

So the question is: are there any reasons why one could prefer convolution over the FFT-based method?

I could imagine only the memory-related argument (e.g. when we don't have any extra memory for calculations), but thinking of a regular PCs, at the time when memory constrains start to play role, the time complexity of $N^2$ will already be a killer for the first method.

Are there any particular numerical issue of the FFT that one needs to be aware of here (and choose convolution to avoid it)?

$\endgroup$
  • $\begingroup$ In twenty-five years of daily practice, I never implemented a single convolution via FFT, mostly because of relatively small $N$ and special requirements such as non-rectangular domains. $\endgroup$ – Yves Daoust Jul 27 '16 at 17:05
2
$\begingroup$

And as it is well known, the computational complexity is $\mathcal{O}(N^2)$ and $\mathcal{O}(N \log N)$ for them respectively.

$\mathcal{O}$ notation ignores any constants that determine exactly how fast those functions run. Depending on the constants out front, it may be faster to compute the convolution (or correlation) directly.

For example, the Fourier transform method to convolve may take $10^5 N \log N$ seconds while the direct method may take $10^{-3} N^2$ seconds. If $N = 100$, the direct method is faster.

In general for large $N$, the Fourier method tends to be faster with speedups of up. For more detail on computing which method is faster, see scipy PR #5608.

Below is a graph that times the Fourier transform method of convolution as fftconvolve and the direct method as convolve. We see that the direct method is faster for many arrays of practical size.

Note: this graph is when convolving 1D signals. For more higher dimensional signals (2D, 3D, etc) fftconvolve tends to be faster more often

To time these graphs, I used scipy.signal.fftconvolve and np.convolve with the default parameters. As of scipy version 0.19, scipy.signal.convolve will choose between the direct and Fourier transform methods to choose the faster method.

$\endgroup$
  • $\begingroup$ I can't see the graph unfortunately $\endgroup$ – Florian Castellane Jul 28 '16 at 8:18
  • $\begingroup$ many thanks, @scott! Could you please upload the figure? - I can't see it too $\endgroup$ – user3160867 Aug 5 '16 at 9:41
  • $\begingroup$ Different image host used -- can you see it now? $\endgroup$ – Scott Aug 8 '16 at 3:27
  • $\begingroup$ I think I can't see it because I'm behind a company firewall that blocks image sharing -- too bad images can't be hosted here $\endgroup$ – Florian Castellane Aug 12 '16 at 13:17
0
$\begingroup$

Perhaps you have just omitted mentioning this in your question, but one fundamental difference is that you can only calculate circular correlation/convolution in the Fourier domain. This can, of course, be overcome by zero padding your time signal, but it is a fundamental difference that might influence your decision on which way to go.

$\endgroup$
0
$\begingroup$

I can imagine the following cases where the convolution based calculation may be preferred:

1- You need to evaluate the correlation only for few lags. If the number of lags $M$ is roughly smaller than $\log(N)$ then the convolution method is actually faster. You may encounter this for example when trying to track the time delay between a signal and its delayed version. During the tracking the time delay may change a bit. So you have a good idea where the maximum correlation happens and you calculate the correlation only around that lag.

2- If you have an integer implementation in a configurable hardware like a FPGA. In this case: - Implementing the FFT takes a lot of resource. - To represent the output of the FFT you may need more bits than the original signal. In this case the multiplications after the FFT may take more resources. The extreme case is the correlation between two binary sequences.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.