# Why autocorrelation can be more efficiently calculated using the fft

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 $$2N\log_2 N$$ real multiplications and $$2N\log_2 N$$ real additions, 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've compared FFT to DFT, I would suggest for better understanding of readers instead of DFT refer to autocorrelation itself. Aug 6, 2019 at 0:59
• I modified this, I apologize for the delay. I will be quicker next time. Jun 11, 2020 at 21:27

Convolution, cross correlation, convolution theorem formula

$$g(t)=f_1(t)*f_2(t)=\int_{-\infty}^{\infty}f_1(\tau)f_2(t-\tau)d\tau \tag{1}$$ $$R_{12}(\tau)=R_{21}(-\tau)=\int_{-\infty}^{\infty}f_1(t)f_2(t+\tau)dt \tag{2}$$ $$F[f_1(t)*f_2(t)]=F_1(\omega) \cdot F_2(\omega) \tag{3}$$

$$R_{11}$$ is autocorrelation when f1=f2.

FFT can efficiently calculate autocorrelation based on formula (3) convolution theorem, set the signal length as N, the time complexity of autocorrelation directly calculated by formula (1) is $$O(N^2)$$.

Set M as N's ceil power two, The time complexity of the convolution theorem formula (3) is $$O (2Mlog_2 (M))$$, $$F1$$and $$F2$$ are conjugate to each other, which requires a fft calculation, and another ifft, that is, $$O (2Mlog_2 (M))$$.

According to the above time complexity comparison, in general, $$O(2Mlog_2 (M))$$ is much better than $$O (N ^ 2)$$, and fft plays a performance acceleration role, but when N is small, such as N=5, M=8, $$N^2>2Mlog_2(M))$$ , fft will be slower than direct calculation.