info prev up next book cdrom email home

Autocorrelation

The autocorrelation function is defined by

\begin{displaymath}
C_f(t) \equiv f\star f = f^*(-t)*f(t) = \int_{-\infty}^\infty f^*(\tau)f(t+\tau)\,d\tau,
\end{displaymath} (1)

where $*$ denotes Convolution and $\star$ denotes Cross-Correlation. A finite autocorrelation is given by
$\displaystyle C_f(\tau)$ $\textstyle \equiv$ $\displaystyle \left\langle{[y(t)-\bar y][y(t+\tau)-\bar y]}\right\rangle{}$ (2)
  $\textstyle =$ $\displaystyle \lim_{T\to\infty} \int_{-T/2}^{T/2} [y(t)-\bar y][y(t+\tau)-\bar y]\,dt.$ (3)

If $f$ is a Real Function,
\begin{displaymath}
f^*=f,
\end{displaymath} (4)

and an Even Function so that
\begin{displaymath}
f(-\tau)=f(\tau),
\end{displaymath} (5)

then
\begin{displaymath}
C_f(t) = \int_{-\infty}^\infty f(\tau)f(t+\tau)\,d\tau.
\end{displaymath} (6)

But let $\tau'\equiv -\tau$, so $d\tau'=-d\tau$, then
$\displaystyle C_f(t)$ $\textstyle =$ $\displaystyle \int_\infty^{-\infty} f(-\tau)f(t-\tau)\,(-d\tau)$  
  $\textstyle =$ $\displaystyle \int_{-\infty}^\infty f(-\tau)f(t-\tau)\,d\tau$  
  $\textstyle =$ $\displaystyle \int_{-\infty}^\infty f(\tau)f(t-\tau)\,d\tau = f*f.$ (7)

The autocorrelation discards phase information, returning only the Power. It is therefore not reversible.


There is also a somewhat surprising and extremely important relationship between the autocorrelation and the Fourier Transform known as the Wiener-Khintchine Theorem. Let ${\mathcal F}[f(x)] = F(k)$, and $F^*$ denote the Complex Conjugate of $F$, then the Fourier Transform of the Absolute Square of $F(k)$ is given by

\begin{displaymath}
{\mathcal F}[\vert F(k)\vert^2] = \int_{-\infty}^\infty f^*(\tau)f(\tau+x)\,d\tau.
\end{displaymath} (8)


The autocorrelation is a Hermitian Operator since $C_f(-t) = {C_f}^*(t)$. $f\star f$ is Maximum at the Origin. In other words,

\begin{displaymath}
\int_{-\infty}^\infty f(u)f(u+x)\,du \leq \int_{-\infty}^\infty f^2(u)\,du.
\end{displaymath} (9)

To see this, let $\epsilon$ be a Real Number. Then
\begin{displaymath}
\int_{-\infty}^\infty [f(u)+\epsilon f(u+x)]^2\,du > 0
\end{displaymath} (10)


\begin{displaymath}
\int_{-\infty}^\infty f^2(u)\,du +2\epsilon \int_{-\infty}^\...
...f(u+x)\,du + \epsilon^2 \int_{-\infty}^\infty f^2(u+x)\,du > 0
\end{displaymath} (11)


\begin{displaymath}
\int_{-\infty}^\infty f^2(u)\,du +2\epsilon \int_{-\infty}^\...
...)f(u+x)\,du + \epsilon^2 \int_{-\infty}^\infty f^2(u)\,du > 0.
\end{displaymath} (12)

Define

$\displaystyle a$ $\textstyle \equiv$ $\displaystyle \int_{-\infty}^\infty f^2(u)\,du$ (13)
$\displaystyle b$ $\textstyle \equiv$ $\displaystyle 2 \int_{-\infty}^\infty f(u)f(u+x)\,du.$ (14)

Then plugging into above, we have $a \epsilon^2+b \epsilon+c > 0$. This Quadratic Equation does not have any Real Root, so $b^2-4ac \leq 0$, i.e., ${b/2} \leq a$. It follows that
\begin{displaymath}
\int_{-\infty}^\infty f(u)f(u+x)\,du \leq \int_{-\infty}^\infty f^2(u)\,du,
\end{displaymath} (15)

with the equality at $x=0$. This proves that $f\star f$ is Maximum at the Origin.

See also Convolution, Cross-Correlation, Quantization Efficiency, Wiener-Khintchine Theorem


References

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.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-25