Autocorrelation - Efficient Computation

Efficient Computation

For data expressed as a discrete sequence, it is frequently necessary to compute the autocorrelation with high computational efficiency. The brute force method based on the definition can be used. For example, to calculate the autocorrelation of, we employ the usual multiplication method with right shifts:

2 3 1
× 2 3 1
________
2 3 1
6 9 3
4 6 2
_____________
2 9 14 9 2

Thus the required autocorrelation is (2,9,14,9,2). In this calculation we do not perform the carry-over operation during addition because the vector has been defined over a field of real numbers. Note that we can halve the number of operations required by exploiting the inherent symmetry of the autocorrelation.

While the brute force algorithm is order n2, several efficient algorithms exist which can compute the autocorrelation in order n log(n). For example, the Wiener–Khinchin theorem allows computing the autocorrelation from the raw data X(t) with two Fast Fourier transforms (FFT):

F_R(f) = FFT

S(f) = F_R(f) F_R*(f)

R(τ) = IFFT

where IFFT denotes the inverse Fast Fourier transform. The asterisk denotes complex conjugate.

Alternatively, a multiple τ correlation can be performed by using brute force calculation for low τ values, and then progressively binning the X(t) data with a logarithmic density to compute higher values, resulting in the same n log(n) efficiency, but with lower memory requirements.