Editing Autocorrelation (section)

==Efficient computation==
For data expressed as a [[Discrete signal|discrete]] sequence, it is frequently necessary to compute the autocorrelation with high [[algorithmic efficiency|computational efficiency]]. A [[brute force method]] based on the signal processing definition <math>R_{xx}(j) = \sum_n x_n\,\overline{x}_{n-j}</math> can be used when the signal size is small. For example, to calculate the autocorrelation of the real signal sequence <math>x = (2,3,-1)</math> (i.e. <math>x_0=2, x_1=3, x_2=-1</math>, and <math>x_i = 0</math> for all other values of {{mvar|i}}) by hand, we first recognize that the definition just given is the same as the "usual" multiplication, but with right shifts, where each vertical addition gives the autocorrelation for particular lag values:
<math display=block>\begin{array}{rrrrrr}
       & 2 & 3 & -1 \\
\times & 2 & 3 & -1 \\
\hline
       &-2 &-3 & 1 \\
       &   & 6 & 9 & -3 \\
     + &   &   & 4 & 6 & -2 \\
\hline
       & -2 & 3 &14 & 3 & -2
\end{array}</math>

Thus the required autocorrelation sequence is <math>R_{xx}=(-2,3,14,3,-2)</math>, where <math>R_{xx}(0)=14,</math> <math>R_{xx}(-1)= R_{xx}(1)=3,</math> and <math>R_{xx}(-2)= R_{xx}(2) = -2,</math> the autocorrelation for other lag values being zero. In this calculation we do not perform the carry-over operation during addition as is usual in normal multiplication. Note that we can halve the number of operations required by exploiting the inherent symmetry of the autocorrelation. If the signal happens to be periodic, i.e. <math>x=(\ldots,2,3,-1,2,3,-1,\ldots),</math> then we get a circular autocorrelation (similar to [[circular convolution]]) where the left and right tails of the previous autocorrelation sequence will overlap and give <math>R_{xx}=(\ldots,14,1,1,14,1,1,\ldots)</math> which has the same period as the signal sequence <math>x.</math> The procedure can be regarded as an application of the convolution property of [[Z-transform]] of a discrete signal.

While the brute force algorithm is [[Big O notation|order]] {{math|''n''<sup>2</sup>}}, several efficient algorithms exist which can compute the autocorrelation in order {{math|''n'' log(''n'')}}. For example, the [[Wiener–Khinchin theorem]] allows computing the autocorrelation from the raw data {{math|''X''(''t'')}} with two [[fast Fourier transform]]s (FFT):<ref>{{cite book |last1=Box |first1=G. E. P. |first2=G. M. |last2=Jenkins |first3=G. C. |last3=Reinsel |title=Time Series Analysis: Forecasting and Control |edition=3rd |location=Upper Saddle River, NJ |publisher=Prentice–Hall |year=1994 |isbn=978-0130607744 }}</ref>{{page needed|date=March 2013}}

<math display=block>\begin{align}
F_R(f) &= \operatorname{FFT}[X(t)] \\
S(f) &= F_R(f) F^*_R(f) \\
R(\tau) &= \operatorname{IFFT}[S(f)]
\end{align}</math>

where IFFT denotes the inverse [[fast Fourier transform]]. The asterisk denotes [[complex conjugate]].

Alternatively, a multiple {{mvar|τ}} correlation can be performed by using brute force calculation for low {{mvar|τ}} values, and then progressively binning the {{math|''X''(''t'')}} data with a [[logarithm]]ic density to compute higher values, resulting in the same {{math|''n'' log(''n'')}} efficiency, but with lower memory requirements.<ref>{{cite book |first1=D. |last1=Frenkel |first2=B. |last2=Smit |title=Understanding Molecular Simulation |edition=2nd |location=London |publisher=Academic Press |year=2002 |chapter=chap. 4.4.2 |isbn=978-0122673511 }}</ref><ref>{{cite journal |first1=P. |last1=Colberg |first2=F. |last2=Höfling |title=Highly accelerated simulations of glassy dynamics using GPUs: caveats on limited floating-point precision |journal=[[Computer Physics Communications|Comput. Phys. Commun.]] |volume=182 |issue=5 |pages=1120–1129 |year=2011 |doi=10.1016/j.cpc.2011.01.009 |arxiv=0912.3824 |bibcode=2011CoPhC.182.1120C |s2cid=7173093 }}</ref>