TOPICS
Search

Autocorrelation


Let {a_i}_(i=0)^(N-1) be a periodic sequence, then the autocorrelation of the sequence, sometimes called the periodic autocorrelation (Zwillinger 1995, p. 223), is the sequence

 rho_i=sum_(j=0)^(N-1)a_ja^__(j+i),
(1)

where a^_ denotes the complex conjugate and the final subscript is understood to be taken modulo N.

Similarly, for a periodic array a_(ij) with 0<=i<=M-1 and 0<=j<=N-1, the autocorrelation is the (2M)×(2N)-dimensional matrix given by

 rho_(ij)=sum_(m=0)^(M-1)sum_(n=0)^(N-1)a_(mn)a^__(m+i,n+j),
(2)

where the final subscripts are understood to be taken modulo M and N, respectively.

For a complex function f, the autocorrelation is defined by

f*f=int_(-infty)^inftyf(tau)f^_(tau-t)dtau
(3)
=int_(-infty)^inftyf^_(tau)f(tau+t)dtau,
(4)

where * denotes cross-correlation and f^_ is the complex conjugate (Bracewell 1965, pp. 40-41).

Note that the notation rho_f(t) is sometimes used for f*f and that the quantity

 R_f(t)=lim_(T->infty)1/(2T)int_(-T)^Tf(tau)f(t+tau)dtau
(5)

is sometimes also known as the autocorrelation of a continuous real function f(t) (Papoulis 1962, p. 241).

The autocorrelation discards phase information, returning only the power, and is therefore an irreversible operation.

There is also a somewhat surprising and extremely important relationship between the autocorrelation and the Fourier transform known as the Wiener-Khinchin theorem. Let F_t[f(t)](omega)=F(omega), and F^_ denote the complex conjugate of F, then the Fourier transform of the absolute square of F(omega) is given by

 F_omega[|F(omega)|^2](t)=int_(-infty)^inftyf^_(tau)f(tau+t)dtau.
(6)

f*f is maximum at the origin; in other words,

 int_(-infty)^inftyf(tau)f(tau+x)dtau<=int_(-infty)^inftyf^2(tau)dtau.
(7)

To see this, let epsilon be a real number. Then

 int_(-infty)^infty[f(tau)+epsilonf(tau+x)]^2dtau>0
(8)
 int_(-infty)^inftyf^2(tau)dtau+2epsilonint_(-infty)^inftyf(tau)f(tau+x)dtau+epsilon^2int_(-infty)^inftyf^2(tau+x)dtau>0
(9)
 int_(-infty)^inftyf^2(tau)dtau+2epsilonint_(-infty)^inftyf(tau)f(tau+x)dtau+epsilon^2int_(-infty)^inftyf^2(tau)dtau>0.
(10)

Define

a=int_(-infty)^inftyf^2(tau)dtau
(11)
b=2int_(-infty)^inftyf(tau)f(tau+x)dtau.
(12)

Then plugging into above, we have aepsilon^2+bepsilon+c>0. This quadratic equation does not have any real root, so b^2-4ac<=0, i.e., b/2<=a. It follows that

 int_(-infty)^inftyf(tau)f(tau+x)dtau<=int_(-infty)^inftyf^2(tau)dtau,
(13)

with the equality at x=0. This proves that f*f is maximum at the origin.


See also

Average Power, Correlation, Convolution, Cross-Correlation, Quantization Efficiency, Recurrence Plot, Wiener-Khinchin Theorem

Explore with Wolfram|Alpha

References

Bracewell, R. "The Autocorrelation Function." The Fourier Transform and Its Applications. New York: McGraw-Hill, pp. 40-45, 1965.Papoulis, A. The Fourier Integral and Its Applications. New York: McGraw-Hill, 1962.Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. "Correlation and Autocorrelation Using the FFT." §13.2 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 538-539, 1992.Zwillinger, D. (Ed.). CRC Standard Mathematical Tables and Formulae. Boca Raton, FL: CRC Press, p. 223, 1995.

Referenced on Wolfram|Alpha

Autocorrelation

Cite this as:

Weisstein, Eric W. "Autocorrelation." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Autocorrelation.html

Subject classifications