Could there be any reason to prefer convolution-based calculation of autocorrelation?

Question

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)?

Answer 1

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.

Answer 2

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.

Answer 3

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.