En la teoría de los procesos estocásticos , el teorema de Karhunen-Loève (llamado así por Kari Karhunen y Michel Loève ), también conocido como el teorema de Kosambi-Karhunen-Loève [1] [2] es una representación de un proceso estocástico como una combinación lineal infinita de funciones ortogonales , análoga a una representación en serie de Fourier de una función en un intervalo acotado. La transformación también se conoce como transformación de Hotelling y transformación de vector propio , y está estrechamente relacionada con el análisis de componentes principales.(PCA) técnica ampliamente utilizada en el procesamiento de imágenes y en el análisis de datos en muchos campos. [3]
Los procesos estocásticos dados por series infinitas de esta forma fueron considerados por primera vez por Damodar Dharmananda Kosambi . [4] [5] Existen muchas expansiones de este tipo de un proceso estocástico: si el proceso se indexa sobre [ a , b ] , cualquier base ortonormal de L 2 ([ a , b ]) produce una expansión del mismo en esa forma. La importancia del teorema de Karhunen-Loève es que produce la mejor base en el sentido de que minimiza el error cuadrático medio total .
A diferencia de una serie de Fourier donde los coeficientes son números fijos y la base de expansión consta de funciones sinusoidales (es decir, funciones seno y coseno ), los coeficientes del teorema de Karhunen-Loève son variables aleatorias y la base de expansión depende del proceso. De hecho, las funciones de base ortogonal utilizadas en esta representación están determinadas por la función de covarianza del proceso. Se puede pensar que la transformada Karhunen-Loève se adapta al proceso para producir la mejor base posible para su expansión.
En el caso de un proceso estocástico centrado { X t } t ∈ [ a , b ] ( centrado significa E [ X t ] = 0 para todo t ∈ [ a , b ] ) que satisface una condición de continuidad técnica, X t admite una descomposición
donde Z k son variables aleatorias no correlacionadas por pares y las funciones e k son funciones continuas de valor real en [ a , b ] que son ortogonales por pares en L 2 ([ a , b ]) . Por lo tanto, a veces se dice que la expansión es bi-ortogonal ya que los coeficientes aleatorios Z k son ortogonales en el espacio de probabilidad mientras que las funciones deterministas e k son ortogonales en el dominio del tiempo. El caso general de un proceso X t que no está centrado puede devolverse al caso de un proceso centrado considerando X t - E [ X t ] que es un proceso centrado.
Además, si el proceso es gaussiano , entonces las variables aleatorias Z k son gaussianas y estocásticamente independientes . Este resultado generaliza la transformada Karhunen-Loève . Un ejemplo importante de un proceso estocástico real centrado en [0, 1] es el proceso de Wiener ; el teorema de Karhunen-Loève se puede utilizar para proporcionar una representación ortogonal canónica para él. En este caso, la expansión consta de funciones sinusoidales.
A lo largo de este artículo, consideraremos un proceso aleatorio de media cero integrable al cuadrado X t definido sobre un espacio de probabilidad (Ω, F , P ) e indexado sobre un intervalo cerrado [ a , b ] , con función de covarianza K X ( s , t ) . Así tenemos:
Asociamos a K X un operador lineal T K X definido de la siguiente manera:
Dado que T K X es un operador lineal, tiene sentido hablar de sus valores propios λ k y funciones propias e k , que se encuentran resolviendo la ecuación integral de Fredholm homogénea de segundo tipo
Declaración del teorema
Teorema . Sea X t un proceso estocástico integrable al cuadrado de media cero definido sobre un espacio de probabilidad (Ω, F , P ) e indexado sobre un intervalo cerrado y acotado [ a , b ], con función de covarianza continua K X ( s , t ) .
Entonces K X ( s, t ) es un núcleo de Mercer y dejando que e k sea una base ortonormal en L 2 ([ a , b ]) formada por las funciones propias de T K X con sus respectivos valores propios λ k , X t admite la siguiente representación
donde la convergencia está en L 2 , uniforme en t y
Además, las variables aleatorias Z k tienen media cero, no están correlacionadas y tienen varianza λ k
Tenga en cuenta que por las generalizaciones del teorema de Mercer podemos reemplazar el intervalo [ a , b ] con otros espacios compactos C y la medida de Lebesgue en [ un , b ] con una medida de Borel cuyo soporte es C .
Prueba
La función de covarianza K X satisface la definición de un núcleo de Mercer. Según el teorema de Mercer , existe en consecuencia un conjunto λ k , e k ( t ) de valores propios y funciones propias de T K X que forman una base ortonormal de L 2 ([ a , b ]) , y K X se puede expresar como
El proceso X t se puede expandir en términos de las funciones propias e k como:
donde los coeficientes (variables aleatorias) Z k están dados por la proyección de X t sobre las respectivas funciones propias
Entonces podemos derivar
donde hemos utilizado el hecho de que las e k son funciones propias de T K X y son ortonormales.
Demostremos ahora que la convergencia está en L 2 . Dejar
Luego:
que va a 0 por el teorema de Mercer.
Propiedades de la transformada Karhunen-Loève
Caso especial: distribución gaussiana
Dado que el límite en la media de las variables aleatorias conjuntamente gaussianas es conjuntamente gaussianas, y las variables aleatorias (centradas) conjuntamente gaussianas son independientes si y solo si son ortogonales, también podemos concluir:
Teorema . Las variables Z i tienen una distribución gaussiana conjunta y son estocásticamente independientes si el proceso original { X t } t es gaussiano.
En el caso de Gauss, dado que las variables Z i son independientes, podemos decir más:
casi seguro.
La transformación Karhunen-Loève decorrelaciona el proceso
Esto es consecuencia de la independencia de Z k .
La expansión de Karhunen-Loève minimiza el error cuadrático medio total
En la introducción, mencionamos que la expansión de Karhunen-Loeve truncada fue la mejor aproximación del proceso original en el sentido de que reduce el error cuadrático medio total resultante de su truncamiento. Debido a esta propiedad, a menudo se dice que la transformada KL compacta óptimamente la energía.
Más específicamente, dada cualquier base ortonormal { f k } de L 2 ([ a , b ]) , podemos descomponer el proceso X t como:
dónde
y podemos aproximar X t por la suma finita
para algún entero N .
Reclamo . De todas estas aproximaciones, la aproximación KL es la que minimiza el error cuadrático medio total (siempre que hayamos dispuesto los valores propios en orden decreciente).
[Prueba]
Considere el error resultante del truncamiento en el N -ésimo término en la siguiente expansión ortonormal:
El error cuadrático medio ε N 2 ( t ) se puede escribir como:
Luego integramos esta última igualdad sobre [ a , b ]. La ortonormalidad de la f k produce:
El problema de minimizar el error cuadrático medio total se reduce a minimizar el lado derecho de esta igualdad sujeto a la restricción de que f k se normalice. Por lo tanto, introducimos β k , los multiplicadores lagrangianos asociados con estas restricciones, y nuestro objetivo es minimizar la siguiente función:
Diferenciar con respecto a f i ( t ) (esta es una derivada funcional ) y establecer la derivada en 0 produce:
que se satisface en particular cuando
En otras palabras, cuando f k se eligen para ser las funciones propias de T K X , por lo tanto, resulta en la expansión KL.
Varianza explicada
Una observación importante es que dado que los coeficientes aleatorios Z k de la expansión KL no están correlacionados, la fórmula de Bienaymé afirma que la varianza de X t es simplemente la suma de las varianzas de los componentes individuales de la suma:
Integrando sobre [ a , b ] y usando la ortonormalidad de la e k , obtenemos que la varianza total del proceso es:
En particular, la varianza total de la aproximación N truncada es
Como resultado, la expansión N -truncada explica
de la varianza; y si estamos contentos con una aproximación que explica, digamos, el 95% de la varianza, entonces solo tenemos que determinar un tal que
La expansión Karhunen-Loève tiene la propiedad de entropía de representación mínima
Dada una representación de , por alguna base ortonormal y al azar , dejamos , así que eso . Entonces podemos definir la entropía de representación como. Entonces nosotros tenemos, para todas las opciones de . Es decir, la expansión KL tiene una entropía de representación mínima.
Prueba:
Denote los coeficientes obtenidos para la base como , y para como .
Escoger . Tenga en cuenta que desde minimiza el error cuadrático medio, tenemos que
Ampliando el tamaño de la mano derecha, obtenemos:
Usando la ortonormalidad de y expandiendo en el base, obtenemos que el tamaño de la mano derecha es igual a:
Podemos realizar un análisis idéntico para el , y reescriba la desigualdad anterior como:
Restar el primer término común y dividir por , obtenemos que:
Esto implica que:
Aproximaciones lineales de Karhunen-Loève
Considere toda una clase de señales que queremos aproximar sobre los primeros M vectores de una base. Estas señales se modelan como realizaciones de un vector aleatorio Y [ n ] de tamaño N . Para optimizar la aproximación diseñamos una base que minimiza el error de aproximación promedio. En esta sección se demuestra que las bases óptimas son bases Karhunen-Loeve que diagonalizan la matriz de covarianza de Y . El vector aleatorio Y se puede descomponer de forma ortogonal
como sigue:
donde cada
es una variable aleatoria. La aproximación de los primeros M ≤ N vectores de la base es
La conservación de energía en forma ortogonal implica
Este error está relacionado con la covarianza de Y definida por
Para cualquier vector x [ n ] denotamos por K el operador de covarianza representado por esta matriz,
El error ε [ M ] es, por tanto, una suma de los últimos N - M coeficientes del operador de covarianza.
El operador de covarianza K es hermitiano y positivo y, por lo tanto, está diagonalizado en una base ortogonal llamada base Karhunen-Loève. El siguiente teorema establece que una base de Karhunen-Loève es óptima para aproximaciones lineales.
Teorema (Optimidad de base Karhunen-Loève). Sea K un operador de covarianza. Para todo M ≥ 1 , el error de aproximación
es mínimo si y solo si
es una base de Karhunen-Loeve ordenada por valores propios decrecientes.
Aproximación no lineal en 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 [definition needed]
Let be the projection of f over M vectors whose indices are in IM:
The approximation error is the sum of the remaining coefficients
To minimize this error, the indices in IM 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 ε[M] to
Theorem (decay of error). If with p < 2 then
and
Conversely, if then
for any q > p.
Non-optimality of Karhunen–Loève bases
To further illustrate the differences between linear and non-linear approximations, we study the decomposition of a simple non-Gaussian random vector in a Karhunen–Loève basis. Processes whose realizations have a random translation are stationary. The Karhunen–Loève basis is then a Fourier basis and we study its performance. To simplify the analysis, consider a random vector Y[n] of size N that is random shift modulo N of a deterministic signal f[n] of zero mean
The random shift P is uniformly distributed on [0, N − 1]:
Clearly
and
Hence
Since RY is N periodic, Y is a circular stationary random vector. The covariance operator is a circular convolution with RY and is therefore diagonalized in the discrete Fourier Karhunen–Loève basis
The power spectrum is Fourier transform of RY:
Example: Consider an extreme case where . A theorem stated above guarantees that the Fourier Karhunen–Loève basis produces a smaller expected approximation error than a canonical basis of Diracs . Indeed, we do not know a priori the abscissa of the non-zero coefficients of Y, so there is no particular Dirac that is better adapted to perform the approximation. But the Fourier vectors cover the whole support of Y and thus absorb a part of the signal energy.
Selecting higher frequency Fourier coefficients yields a better mean-square approximation than choosing a priori a few Dirac vectors to perform the approximation. The situation is totally different for non-linear approximations. If then the discrete Fourier basis is extremely inefficient because f and hence Y have an energy that is almost uniformly spread among all Fourier vectors. In contrast, since f has only two non-zero coefficients in the Dirac basis, a non-linear approximation of Y with M ≥ 2 gives zero error.[6]
Análisis de componentes principales
We have established the Karhunen–Loève theorem and derived a few properties thereof. We also noted that one hurdle in its application was the numerical cost of determining the eigenvalues and eigenfunctions of its covariance operator through the Fredholm integral equation of the second kind
However, when applied to a discrete and finite process , the problem takes a much simpler form and standard algebra can be used to carry out the calculations.
Note that a continuous process can also be sampled at N points in time in order to reduce the problem to a finite version.
We henceforth consider a random N-dimensional vector . As mentioned above, X could contain N samples of a signal but it can hold many more representations depending on the field of application. For instance it could be the answers to a survey or economic data in an econometrics analysis.
As in the continuous version, we assume that X is centered, otherwise we can let (where is the mean vector of X) which is centered.
Let us adapt the procedure to the discrete case.
Covariance matrix
Recall that the main implication and difficulty of the KL transformation is computing the eigenvectors of the linear operator associated to the covariance function, which are given by the solutions to the integral equation written above.
Define Σ, the covariance matrix of X, as an N × N matrix whose elements are given by:
Rewriting the above integral equation to suit the discrete case, we observe that it turns into:
where is an N-dimensional vector.
The integral equation thus reduces to a simple matrix eigenvalue problem, which explains why the PCA has such a broad domain of applications.
Since Σ is a positive definite symmetric matrix, it possesses a set of orthonormal eigenvectors forming a basis of , and we write this set of eigenvalues and corresponding eigenvectors, listed in decreasing values of λi. Let also Φ be the orthonormal matrix consisting of these eigenvectors:
Principal component transform
It remains to perform the actual KL transformation, called the principal component transform in this case. Recall that the transform was found by expanding the process with respect to the basis spanned by the eigenvectors of the covariance function. In this case, we hence have:
In a more compact form, the principal component transform of X is defined by:
The i-th component of Y is , the projection of X on and the inverse transform X = ΦY yields the expansion of X on the space spanned by the :
As in the continuous case, we may reduce the dimensionality of the problem by truncating the sum at some such that
where α is the explained variance threshold we wish to set.
We can also reduce the dimensionality through the use of multilevel dominant eigenvector estimation (MDEE).[7]
Ejemplos de
The Wiener process
There are numerous equivalent characterizations of the Wiener process which is a mathematical formalization of Brownian motion. Here we regard it as the centered standard Gaussian process Wt with covariance function
We restrict the time domain to [a, b]=[0,1] without loss of generality.
The eigenvectors of the covariance kernel are easily determined. These are
and the corresponding eigenvalues are
[Proof]
In order to find the eigenvalues and eigenvectors, we need to solve the integral equation:
differentiating once with respect to t yields:
a second differentiation produces the following differential equation:
The general solution of which has the form:
where A and B are two constants to be determined with the boundary conditions. Setting t = 0 in the initial integral equation gives e(0) = 0 which implies that B = 0 and similarly, setting t = 1 in the first differentiation yields e' (1) = 0, whence:
which in turn implies that eigenvalues of TKX are:
The corresponding eigenfunctions are thus of the form:
A is then chosen so as to normalize ek:
This gives the following representation of the Wiener process:
Theorem. There is a sequence {Zi}i of independent Gaussian random variables with mean zero and variance 1 such that
Note that this representation is only valid for On larger intervals, the increments are not independent. As stated in the theorem, convergence is in the L2 norm and uniform in t.
The Brownian bridge
Similarly the Brownian bridge which is a stochastic process with covariance function
can be represented as the series
Aplicaciones
Adaptive optics systems sometimes use K–L functions to reconstruct wave-front phase information (Dai 1996, JOSA A). Karhunen–Loève expansion is closely related to the Singular Value Decomposition. The latter has myriad applications in image processing, radar, seismology, and the like. If one has independent vector observations from a vector valued stochastic process then the left singular vectors are maximum likelihood estimates of the ensemble KL expansion.
Applications in signal estimation and detection
Detection of a known continuous signal S(t)
In communication, we usually have to decide whether a signal from a noisy channel contains valuable information. The following hypothesis testing is used for detecting continuous signal s(t) from channel output X(t), N(t) is the channel noise, which is usually assumed zero mean Gaussian process with correlation function
Signal detection in white noise
When the channel noise is white, its correlation function is
and it has constant power spectrum density. In physically practical channel, the noise power is finite, so:
Then the noise correlation function is sinc function with zeros at Since are uncorrelated and gaussian, they are independent. Thus we can take samples from X(t) with time spacing
Let . We have a total of i.i.d observations to develop the likelihood-ratio test. Define signal , the problem becomes,
The log-likelihood ratio
As t → 0, let:
Then G is the test statistics and the Neyman–Pearson optimum detector is
As G is Gaussian, we can characterize it by finding its mean and variances. Then we get
where
is the signal energy.
The false alarm error
And the probability of detection:
where Φ is the cdf of standard normal, or Gaussian, variable.
Signal detection in colored noise
When N(t) is colored (correlated in time) Gaussian noise with zero mean and covariance function we cannot sample independent discrete observations by evenly spacing the time. Instead, we can use K–L expansion to uncorrelate[check spelling] the noise process and get independent Gaussian observation 'samples'. The K–L expansion of N(t):
where and the orthonormal bases are generated by kernel , i.e., solution to
Do the expansion:
where , then
under H and under K. Let , we have
are independent Gaussian r.v's with variance
under H: are independent Gaussian r.v's.
under K: are independent Gaussian r.v's.
Hence, the log-LR is given by
and the optimum detector is
Define
then
How to find k(t)
Since
k(t) is the solution to
If N(t)is wide-sense stationary,
which is known as the Wiener–Hopf equation. The equation can be solved by taking fourier transform, but not practically realizable since infinite spectrum needs spatial factorization. A special case which is easy to calculate k(t) is white Gaussian noise.
The corresponding impulse response is h(t) = k(T − t) = CS(T − t). Let C = 1, this is just the result we arrived at in previous section for detecting of signal in white noise.
Test threshold for Neyman–Pearson detector
Since X(t) is a Gaussian process,
is a Gaussian random variable that can be characterized by its mean and variance.
Hence, we obtain the distributions of H and K:
The false alarm error is
So the test threshold for the Neyman–Pearson optimum detector is
Its power of detection is
When the noise is white Gaussian process, the signal power is
Prewhitening
For some type of colored noise, a typical practise is to add a prewhitening filter before the matched filter to transform the colored noise into white noise. For example, N(t) is a wide-sense stationary colored noise with correlation function
The transfer function of prewhitening filter is
Detection of a Gaussian random signal in Additive white Gaussian noise (AWGN)
When the signal we want to detect from the noisy channel is also random, for example, a white Gaussian process X(t), we can still implement K–L expansion to get independent sequence of observation. In this case, the detection problem is described as follows:
X(t) is a random process with correlation function
The K–L expansion of X(t) is
where
and are solutions to
So 's are independent sequence of r.v's with zero mean and variance . Expanding Y(t) and N(t) by , we get
where
As N(t) is Gaussian white noise, 's are i.i.d sequence of r.v with zero mean and variance , then the problem is simplified as follows,
The Neyman–Pearson optimal test:
so the log-likelihood ratio is
Since
is just the minimum-mean-square estimate of given 's,
K–L expansion has the following property: If
where
then
So let
Noncausal filter Q(t,s) can be used to get the estimate through
By orthogonality principle, Q(t,s) satisfies
However, for practical reasons, it's necessary to further derive the causal filter h(t,s), where h(t,s) = 0 for s > t, to get estimate . Specifically,
Ver también
Principal component analysis
Polynomial chaos
Notas
^Sapatnekar, Sachin (2011), "Overcoming variations in nanometer-scale technologies", IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 1 (1): 5–18, Bibcode:2011IJEST...1....5S, CiteSeerX 10.1.1.300.5659, doi:10.1109/jetcas.2011.2138250
^Ghoman, Satyajit; Wang, Zhicun; Chen, PC; Kapania, Rakesh (2012), A POD-based Reduced Order Design Scheme for Shape Optimization of Air VehiclesUnknown parameter |book-title= ignored (help)
^Karhunen–Loeve transform (KLT), Computer Image Processing and Analysis (E161) lectures, Harvey Mudd College
^Raju, C.K. (2009), "Kosambi the Mathematician", Economic and Political Weekly, 44 (20): 33–45
^Kosambi, D. D. (1943), "Statistics in Function Space", Journal of the Indian Mathematical Society, 7: 76–88, MR 0009816.
^A wavelet tour of signal processing-Stéphane Mallat
^X. Tang, “Texture information in run-length matrices,” IEEE Transactions on Image Processing, vol. 7, No. 11, pp. 1602–1609, Nov. 1998
Referencias
Stark, Henry; Woods, John W. (1986). Probability, Random Processes, and Estimation Theory for Engineers. Prentice-Hall, Inc. ISBN 978-0-13-711706-2. OL 21138080M.
Ghanem, Roger; Spanos, Pol (1991). Stochastic finite elements: a spectral approach. Springer-Verlag. ISBN 978-0-387-97456-9. OL 1865197M.
Guikhman, I.; Skorokhod, A. (1977). Introduction a la Théorie des Processus Aléatoires. Éditions MIR.
Simon, B. (1979). Functional Integration and Quantum Physics. Academic Press.
Karhunen, Kari (1947). "Über lineare Methoden in der Wahrscheinlichkeitsrechnung". Ann. Acad. Sci. Fennicae. Ser. A. I. Math.-Phys. 37: 1–79.
Loève, M. (1978). Probability theory. Vol. II, 4th ed. Graduate Texts in Mathematics. 46. Springer-Verlag. ISBN 978-0-387-90262-3.
Dai, G. (1996). "Modal wave-front reconstruction with Zernike polynomials and Karhunen–Loeve functions". JOSA A. 13 (6): 1218. Bibcode:1996JOSAA..13.1218D. doi:10.1364/JOSAA.13.001218.
Wu B., Zhu J., Najm F.(2005) "A Non-parametric Approach for Dynamic Range Estimation of Nonlinear Systems". In Proceedings of Design Automation Conference(841-844) 2005
Wu B., Zhu J., Najm F.(2006) "Dynamic Range Estimation". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 25 Issue:9 (1618–1636) 2006
Jorgensen, Palle E. T.; Song, Myung-Sin (2007). "Entropy Encoding, Hilbert Space and Karhunen–Loeve Transforms". Journal of Mathematical Physics. 48 (10): 103503. arXiv:math-ph/0701056. Bibcode:2007JMP....48j3503J. doi:10.1063/1.2793569.
enlaces externos
Mathematica KarhunenLoeveDecomposition function.
E161: Computer Image Processing and Analysis notes by Pr. Ruye Wang at Harvey Mudd College [1]