Computing Autocorrelation via FFT

Question

I have seen several methods to calculate Autocorrelations using FFTs, and am confused about why they differ.

Zero-Pad it to double its original length.Take the FFT. Then replace all the coefficients with their square magnitude, except for the first, which you set to 0. Now take the IFFT. Divide every element by the first one. This gives you the autocorrelation. https://stackoverflow.com/questions/4583950/cepstral-analysis-for-pitch-detection

1. create a centered version of x by setting x_cent = x / mean(x);
2. pad x_cent at the end with entries of value 0 to get a new vector of length L = 2^ceil(log2(N));
3. run x_pad through a forward discrete fast fourier transform to get an L-vector z of complex values;
4. replace the entries in z with their norms (the norm of a complex number is the real number resulting of summing the squared real component and squared imaginary component).
5. run z through the inverse discrete FFT to produce an L-vector acov of (unadjusted) autocovariances;
6. trim acov to size N;
7. create a L-vector named mask consisting of N entries with value 1 followed by L-N entries with value 0;
8. compute the forward FFT of mask and put the result in the L-vector adj
9. to get adjusted autocovariance estimates, divide each entry acov[n] by norm(adj[n]), where norm is the complex norm defined above; and
10. to get autocorrelations, set acorr[n] = acov[n] / acov[0] (acov[0], the autocovariance at lag 0, is just the variance). https://lingpipe-blog.com/2012/06/08/autocorrelation-fft-kiss-eigen/

And of course there is simply the first method but without setting the first element in the frequency domain to zero (i.e. what you'd expect from the Wiener–Khinchin theorem) https://stackoverflow.com/questions/3949324/calculate-autocorrelation-using-fft-in-matlab.

Why do the first two methods differ from the naive implementation of Wiener–Khinchin theorem. Are there any references that may help me figure out which method is best (and maybe on fast convolutions in general)?

Answer 1

The first method zeros out the "DC" in the signal see. If you compute the autocorrelation of $sin(\pi x / k) + 1$ using matlab's xcorr, you do not get a negative correlation for the kth lag. This doesn't make sense as a statistical correlation so you need to remove/zero out the "DC" in the spectrum corresponding to the $+ 1$.

The second method does not double the length and so will alias the signal. Maybe it is correcting for the aliasing. But also there are different definitions of autocorrelation see and may also be calculating the statistical autocorrelation assuming stationarity.