Wiener–Khinchin theorem

In applied mathematics, the Wiener–Khinchin theorem, also known as the Wiener–Khintchine theorem and sometimes as the Wiener–Khinchin–Einstein theorem or the Khinchin–Kolmogorov theorem, states that the autocorrelation function of a wide-sense-stationary random process has a spectral decomposition given by the power spectrum of that process.^{[1][2][3][4][5][6][7]}

History

Norbert Wiener proved this theorem for the case of a deterministic function in 1930;^[8] Aleksandr Khinchin later formulated an analogous result for stationary stochastic processes and published that probabilistic analogue in 1934.^[9][10] Albert Einstein explained, without proofs, the idea in a brief two-page memo in 1914.^[11]

The case of a continuous-time process

For continuous time, the Wiener–Khinchin theorem says that if $x$ is a wide-sense stationary process such that its autocorrelation function (sometimes called autocovariance) defined in terms of statistical expected value E, $r_{xx}(\tau) = \operatorname{E}\big[\, x(t)x^*(t-\tau) \, \big] \$ exists and is finite at every lag $\tau$, then there exists a monotone function $F(f)$ in the frequency domain $-\infty < f < \infty$ such that

$r_{xx} (\tau) = \int_{-\infty}^\infty e^{2\pi i\tau f} dF(f)$

where the integral is a Riemann–Stieltjes integral.^[1][12] This is a kind of spectral decomposition of the auto-correlation function. F is called the power spectral distribution function, and is a statistical distribution function. It is sometimes called the integrated spectrum.

(The asterisk denotes complex conjugate, and of course it can be omitted if the random process is real-valued.)

Note that the Fourier transform of $x(t)\,$ does not exist in general, because stationary random functions are not generally either square integrable or absolutely integrable. Nor is $r_{xx}$ assumed to be absolutely integrable, so it need not have a Fourier transform, either.

But if $F(f)$ is absolutely continuous, for example if the process is purely indeterministic, then $F$ is differentiable almost everywhere. In this case, one can define $S(f)$, the power spectral density of $x(t)\,$, by taking the averaged derivative of $F$. Because the left and right derivatives of $F$ exist everywhere, we can put $S(f) = \frac12 (\lim_{\epsilon\downarrow 0} \frac1\epsilon (F(f+\epsilon)-F(f))+ \lim_{\epsilon\uparrow 0} \frac1\epsilon (F(f+\epsilon)-F(f)))$ everywhere,^[13] (obtaining that F is the integral of its averaged derivative^[14]), and the theorem simplifies to

$r_{xx} (\tau) = \int_{-\infty}^\infty S(f) e^{2\pi i\tau f} df.$

If now one assumes that r and S satisfy the necessary conditions for Fourier inversion to be valid, the Wiener–Khinchin theorem takes the simple form of saying that r and S are a Fourier transform pair, and

$S(f) = \int_{-\infty}^\infty r_{xx} (\tau) e^{-2\pi if\tau} d\tau.$

The case of a discrete-time process

For the discrete-time case, the power spectral density of the function with discrete values $x[n]\,$ is

$S(f)=\sum_{k=-\infty}^\infty r_{xx}[k]e^{-i(2\pi f) k},$

where

$r_{xx}[k] = \operatorname{E}\big[ \, x[n] x^*[n-k] \, \big] \$

is the discrete autocorrelation function of $x[n]\,$, provided this is absolutely integrable. Being a sampled and discrete-time sequence, the spectral density is periodic in the frequency domain. This is due to the problem of aliasing: the contribution of any frequency higher than the Nyquist frequency seems to be equal to that of its alias between 0 and 1. For this reason, the domain of the function $S$ is usually restricted to lie between 0 and 1.

Application

The theorem is useful for analyzing linear time-invariant systems, LTI systems, when the inputs and outputs are not square integrable, so their Fourier transforms do not exist. A corollary is that the Fourier transform of the autocorrelation function of the output of an LTI system is equal to the product of the Fourier transform of the autocorrelation function of the input of the system times the squared magnitude of the Fourier transform of the system impulse response.^[15] This works even when the Fourier transforms of the input and output signals do not exist because these signals are not square integrable, so the system inputs and outputs cannot be directly related by the Fourier transform of the impulse response.

Since the Fourier transform of the autocorrelation function of a signal is the power spectrum of the signal, this corollary is equivalent to saying that the power spectrum of the output is equal to the power spectrum of the input times the energy transfer function.

This corollary is used in the parametric method for power spectrum estimation.

Discrepancies in terminology

In many textbooks and in much of the technical literature it is tacitly assumed that Fourier inversion of the autocorrelation function and the power spectral density is valid, and the Wiener–Khinchin theorem is stated, very simply, as if it said that the Fourier transform of the autocorrelation function was equal to the power spectral density, ignoring all questions of convergence.^[16] (Einstein is an example.) But the theorem (as stated here), was applied by Norbert Wiener and Aleksandr Khinchin to the sample functions (signals) of wide-sense-stationary random processes, signals whose Fourier transforms do not exist. The whole point of Wiener's contribution was to make sense of the spectral decomposition of the autocorrelation function of a sample function of a wide-sense-stationary random process even when the integrals for the Fourier transform and Fourier inversion do not make sense.

Further complicating the issue is that the discrete Fourier transform always exists for digital, finite length sequences, meaning that the theorem can be blindly applied to calculate auto-correlations of numerical sequences. As mentioned earlier, the relation of this discrete sampled data to a mathematical model is often misleading and related errors can show up as a divergence when the sequence length is modified.

Some authors refer to $R$ as the autocovariance function. They then proceed to normalise it, by dividing by $R(0)$, to obtain what they refer to as the autocorrelation function.

References

1. C. Chatfield (1989). The Analysis of Time Series—An Introduction (fourth ed.). Chapman and Hall, London. pp. 94–95. ISBN 0-412-31820-2.
2. Norbert Wiener (1964). Time Series. M.I.T. Press, Cambridge, Massachusetts. p. 42.
3. Hannan, E.J., "Stationary Time Series", in: John Eatwell, Murray Milgate, and Peter Newman, editors, The New Palgrave: A Dictionary of Economics. Time Series and Statistics, Macmillan, London, 1990, p. 271.
4. Dennis Ward Ricker (2003). Echo Signal Processing. Springer. ISBN 1-4020-7395-X.
5. Leon W. Couch II (2001). Digital and Analog Communications Systems (sixth ed.). Prentice Hall, New Jersey. pp. 406–409. ISBN 0-13-522583-3.
6. Krzysztof Iniewski (2007). Wireless Technologies: Circuits, Systems, and Devices. CRC Press. ISBN 0-8493-7996-2.
7. Joseph W. Goodman (1985). Statistical Optics. Wiley-Interscience. ISBN 0-471-01502-4.
8. Wiener, Norbert (1930). "Generalized Harmonic Analysis". Acta Mathematica. 55: 117–258. doi:10.1007/bf02546511.
9. D.C. Champeney (1987). "Power spectra and Wiener's theorems". A Handbook of Fourier Theorems. Cambridge University Press. p. 102. Wiener's basic theory of 'generalised harmonic analysis' is in no way probabilistic, and the theorems apply to single well defined functions rather than to ensembles of functions [...] A further development of these ideas occurs in the work of A. I. Khintchine (1894–1959) on stationary random processes (or stochastic processes) [...] in contexts in which it is not important to distinguish the two aproaches the theory is often referred to as the Wiener—Khintchine theory.
10. Khintchine, Alexander (1934). "Korrelationstheorie der stationären stochastischen Prozesse". Mathematische Annalen. 109 (1): 604–615. doi:10.1007/BF01449156.
11. Jerison, David; Singer, Isadore Manuel; Stroock, Daniel W. (1997). The Legacy of Norbert Wiener: A Centennial Symposium (Proceedings of Symposia in Pure Mathematics). American Mathematical Society. p. 95. ISBN 0-8218-0415-4.
12. Hannan, E. J. (1990). "Stationary Time Series". In Eatwell, John; Milgate, Murray; Newman, Peter. The New Palgrave: A Dictionary of Economics. Time Series and Statistics. London: Macmillan. p. 271.
13. Chatfield, C. (1989). The Analysis of Time Series—An Introduction (Fourth ed.). London: Chapman and Hall. p. 96. ISBN 0-412-31820-2.
14. Champeney, D. C. (1987). A Handbook of Fourier Theorems. Cambridge Univ. Press. pp. 20–22.
15. Shlomo Engelberg (2007). Random signals and noise: a mathematical introduction. CRC Press. p. 130. ISBN 978-0-8493-7554-5.
16. C. Chatfield (1989). The Analysis of Time Series—An Introduction (fourth ed.). Chapman and Hall, London. p. 98. ISBN 0-412-31820-2.

Further reading

• Brockwell, Peter A.; Davis, Richard J. (2002). Introduction to Time Series and Forecasting (Second ed.). New York: Springer-Verlag. ISBN 038721657X.
• Chatfield, C. (1989). The Analysis of Time Series—An Introduction (Fourth ed.). London: Chapman and Hall. ISBN 0412318202.
• Fuller, Wayne (1996). Introduction to Statistical Time Series. Wiley Series in Probability and Statistics (Second ed.). New York: Wiley. ISBN 0471552399.
• Wiener, Norbert (1949). "Extrapolation, Interpolation, and Smoothing of Stationary Time Series". Cambridge, Massachusetts: Technology Press and Johns Hopkins Univ. Press. (a classified document written for the Dept. of War in 1943).
• Yaglom, A. M. (1962). An Introduction to the Theory of Stationary Random Functions. Englewood Cliffs, New Jersey: Prentice–Hall.