In the theory of stochastic processes, the Karhunen–Loève theorem (named after Kari Karhunen and Michel Loève), also known as the Kosambi–Karhunen–Loève theorem states that a stochastic process can be represented as an infinite linear combination of orthogonal functions, analogous to a Fourier series representation of a function on a bounded interval. The transformation is also known as Hotelling transform and eigenvector transform, and is closely related to principal component analysis (PCA) technique widely used in image processing and in data analysis in many fields.Karhunen–Loeve transform (KLT) , Computer Image Processing and Analysis (E161) lectures, Harvey Mudd College
There exist many such expansions of a stochastic process: if the process is indexed over , any orthonormal basis of yields an expansion thereof in that form. The importance of the Karhunen–Loève theorem is that it yields the best such basis in the sense that it minimizes the total mean squared error.
In contrast to a Fourier series where the coefficients are fixed numbers and the expansion basis consists of sinusoidal functions (that is, sine and cosine functions), the coefficients in the Karhunen–Loève theorem are random variables and the expansion basis depends on the process. In fact, the orthogonal basis functions used in this representation are determined by the covariance function of the process. One can think that the Karhunen–Loève transform adapts to the process in order to produce the best possible basis for its expansion.
In the case of a centered stochastic process (centered means for all ) satisfying a technical continuity condition, admits a decomposition
where are pairwise uncorrelated random variables and the functions are continuous real-valued functions on that are pairwise orthogonal in . It is therefore sometimes said that the expansion is bi-orthogonal since the random coefficients are orthogonal in the probability space while the deterministic functions are orthogonal in the time domain. The general case of a process that is not centered can be brought back to the case of a centered process by considering which is a centered process.
Moreover, if the process is Gaussian, then the random variables are Gaussian and stochastically independent. This result generalizes the Karhunen–Loève transform. An important example of a centered real stochastic process on is the Wiener process; the Karhunen–Loève theorem can be used to provide a canonical orthogonal representation for it. In this case the expansion consists of sinusoidal functions.
The above expansion into uncorrelated random variables is also known as the Karhunen–Loève expansion or Karhunen–Loève decomposition. The empirical version (i.e., with the coefficients computed from a sample) is known as the Karhunen–Loève transform (KLT), principal component analysis, proper orthogonal decomposition (POD), empirical orthogonal functions (a term used in meteorology and geophysics), or the Hotelling transform.
Formulation
Throughout this article, we will consider a random process defined over a probability space and indexed over a closed interval , which is square-integrable, has zero-mean, and with covariance function . In other words, we have:
The square-integrable condition is logically equivalent to being finite for all .
We associate to a linear operator (more specifically a Hilbert–Schmidt integral operator) defined in the following way:
Since is a linear endomorphism, it makes sense to talk about its eigenvalues λk and eigenfunctions , which are found by solving the homogeneous Fredholm integral equation of the second kind .
Statement of the theorem
Theorem. Let be a zero-mean square-integrable stochastic process defined over a probability space and indexed over a closed and bounded interval [a, b], with continuous covariance function .
Then is a Mercer kernel and letting be an orthonormal basis on formed by the eigenfunctions of with respective eigenvalues admits the following representation
where the convergence is in , uniform in t and
Furthermore, the random variables have zero-mean, are uncorrelated and have variance λk
Note that by generalizations of Mercer's theorem we can replace the interval [a, b] with other compact spaces C and the Lebesgue measure on [a, b] with a Borel measure whose support is C.
Proof
The covariance function satisfies the definition of a Mercer kernel. By Mercer's theorem, there consequently exists a set , of eigenvalues and eigenfunctions of forming an orthonormal basis of , and can be expressed as
The process can be expanded in terms of the eigenfunctions as:
where the coefficients (random variables) are given by the projection of on the respective eigenfunctions
We may then derive
where we have used the fact that the are eigenfunctions of and are orthonormal.
Let us now show that the convergence is in . Let
Then:
which goes to 0 by Mercer's theorem.
Properties of the Karhunen–Loève transform
Special case: Gaussian distribution Since the limit in the mean of jointly Gaussian random variables is jointly Gaussian, and jointly Gaussian random (centered) variables are independent if and only if they are orthogonal, we can also conclude:
Theorem. The variables have a joint Gaussian distribution and are stochastically independent if the original process is Gaussian.
In the Gaussian case, since the variables are independent, we can say more:
almost surely.
The Karhunen–Loève transform decorrelates the process This is a consequence of the independence of the .
The Karhunen–Loève expansion minimizes the total mean square error In the introduction, we mentioned that the truncated Karhunen–Loeve expansion was the best approximation of the original process in the sense that it reduces the total mean-square error resulting of its truncation. Because of this property, it is often said that the KL transform optimally compacts the energy.
More specifically, given any orthonormal basis } of , we may decompose the process as:
where
and we may approximate by the finite sum
for some integer N.
Claim. Of all such approximations, the KL approximation is the one that minimizes the total mean square error (provided we have arranged the eigenvalues in decreasing order).
The optimality of the Karhunen–Loève basis can be stated as three distinct properties, each of which characterizes the KL expansion uniquely when it is used as a transform (up to ordering of equal-variance components) among all linear orthogonal transforms:
Decorrelation: The KL components are mutually uncorrelated (orthogonal in the probability-theoretic sense), meaning the covariance matrix of the expansion coefficients is diagonal. Variance concentration: Among all orthogonal decompositions, the first K KL components capture more variance than the first K components of any other orthogonal basis, for every K. Minimum reconstruction error: Truncating the expansion to K terms yields the lowest mean squared error among all linear K-term approximations.
These properties make the KL transform the theoretical benchmark against which other linear transforms—such as the discrete Fourier transform and discrete cosine transform—are compared. The DFT and DCT are optimal only when the covariance structure has the specific symmetry (circulant or centrosymmetric, respectively) that matches their basis functions; the KL transform is optimal for any covariance structure.
Explained variance An important observation is that since the random coefficients Zk of the KL expansion are uncorrelated, the Bienaymé formula asserts that the variance of Xt is simply the sum of the variances of the individual components of the sum:
Integrating over [a, b] and using the orthonormality of the ek, we obtain that the total variance of the process is:
In particular, the total variance of the N-truncated approximation is
As a result, the N-truncated expansion explains
of the variance; and if we are content with an approximation that explains, say, 95% of the variance, then we just have to determine an such that
The Karhunen–Loève expansion has the minimum representation entropy property Given a representation of , for some orthonormal basis and random , we let , so that . We may then define the representation entropy to be . Then we have , for all choices of . That is, the KL-expansion has minimal representation entropy.
Proof:
Denote the coefficients obtained for the basis as , and for as .
Choose . Note that since minimizes the mean squared error, we have that
Expanding the right hand size, we get:
Using the orthonormality of , and expanding in the basis, we get that the right hand size is equal to:
We may perform identical analysis for the , and so rewrite the above inequality as:
Subtracting the common first term, and dividing by , we obtain that:
This implies that:
Linear Karhunen–Loève approximations
Consider a whole class of signals we want to approximate over the first vectors of a basis. These signals are modeled as realizations of a random vector of size . To optimize the approximation we design a basis that minimizes the average approximation error. This section proves that optimal bases are Karhunen–Loeve bases that diagonalize the covariance matrix of . The random vector can be decomposed in an orthogonal basis
as follows:
where each
is a random variable. The approximation from the first vectors of the basis is
The energy conservation in an orthogonal basis implies
This error is related to the covariance of defined by
For any vector we denote by the covariance operator represented by this matrix,
The error is therefore a sum of the last coefficients of the covariance operator
The covariance operator is Hermitian and Positive and is thus diagonalized in an orthogonal basis called a Karhunen–Loève basis. The following theorem states that a Karhunen–Loève basis is optimal for linear approximations.
Theorem (Optimality of Karhunen–Loève basis). Let be a covariance operator. For all , the approximation error
is minimum if and only if
is a Karhunen–Loeve basis ordered by decreasing eigenvalues.
Non-Linear approximation in bases
Linear approximations project the signal on M vectors a priori. The approximation can be made more precise by choosing the M orthogonal vectors depending on the signal properties. This section analyzes the general performance of these non-linear approximations. A signal is approximated with M vectors selected adaptively in an orthonormal basis for
Let be the projection of f over M vectors whose indices are in :
The approximation error is the sum of the remaining coefficients
To minimize this error, the indices in must correspond to the M vectors having the largest inner product amplitude
These are the vectors that best correlate f. They can thus be interpreted as the main features of f. The resulting error is necessarily smaller than the error of a linear approximation which selects the M approximation vectors independently of f. Let us sort
in decreasing order
The best non-linear approximation is
It can also be written as inner product thresholding:
with
The non-linear error is
this error goes quickly to zero as M increases, if the sorted values of have a fast decay as k increases. This decay is quantified by computing the norm of the signal inner products in B:
The following theorem relates the decay of to
Theorem (decay of error). If with then
and
Conversely, if then
for any .
Non-optimality of Karhunen–Loève bases