Can anyone explain why autocorrelation can be more efficiently calculated using the fft ?


The cross-correlation between two functions $f(t)$ and $g(t)$ can be seen as a convolution of $f(t)$ and $g(-t)$. The auto-correlation is of course a special case where $f=g$. This operation in the frequency domain corresponds to a multiplication. Therefore, an efficient way to compute the cross-correlation is to compute the Fourier Transform of both $g(t)$ and $f(t)$, multiply them in the frequency domain and the anti-transform the result, to go back to the time domain.

This approach apparently looks more computationally expensive, however in the discrete case, if we use the fast algorithm of the FFT (Fast Fourier Transform) to compute the DFT (Discrete Fourier Transform), which uses $N\log N$ arithmetic operations, it leads to more efficient algorithm than the actual computation of the cross-correlation function in the time domain, which requires $N^2$ operations, where $N$ is the number of samples. So the number of operations is much lower if $N$ is particularly high, which is often the case ...

You can watch this video if you want to know more about this https://www.youtube.com/watch?v=iTMn0Kt18tg

| improve this answer | |
  • $\begingroup$ you've compared FFT to DFT, I would suggest for better understanding of readers instead of DFT refer to autocorrelation itself. $\endgroup$ – MimSaad Aug 6 '19 at 0:59
  • $\begingroup$ I modified this, I apologize for the delay. I will be quicker next time. $\endgroup$ – EmThorns Jun 11 at 21:27

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.