8 votos

Cómo calcular tridiagonal aproximada de la matriz de covarianza, para una rápida descorrelación?

Dada una matriz de datos $X$ de decir 1000000 observaciones $\times$ 100 características, hay una forma rápida de construir una aproximación tridiagonal $A \approx cov(X)$ ?
Entonces uno podría factor de $A = L L^T$, $L$ 0 todos con la excepción de$L_{i\ i-1}$$L_{i i}$, y qué rápido descorrelación (blanqueamiento) mediante la resolución de $L x = x_{white}$. (Por "rápido", me refiero a $O( size\ X )$.)

(Añadido, tratando de aclarar): estoy buscando un rápido y sucio blanqueador que es más rápido que el total $cov(X)$, pero mejor que la diagonal. Decir que $X$ $N$ puntos de datos $\times Nf$ características, por ejemplo, 1000000$\times$ 100, con las características de 0-media.

1) construir el $Fullcov = X^T X$, el factor de Cholesky como $L L^T$, solucionar $L x = x_{white}$ a blanquear nueva $x$ s. Este es cuadrática en el número de características.

2) diagonal: $x_{white} = x / \sigma(x)$ ignora cruz-correlaciones completamente.

Uno podría obtener una matriz tridiagonal de $Fullcov$ sólo por la puesta a cero de todas las entradas fuera de la tridiagonal, o no la acumulación de puntos en el primer lugar. Y aquí me empiezan a descender: debe haber una mejor aproximación, tal vez jerárquica, bloque diagonal → tridiagonal ?


(Añadido el 11 de Mayo): voy a dividir la pregunta en dos:

1) hay un rápido aproximado de $cov(X)$ ?
No (whuber), se debe mirar a todos los ${N \choose 2}$ pares (o estructura, o de la muestra).

2) dada una $cov(X)$, ¿qué tan rápido puede uno blanquear nueva $x$ s ?
Bueno, factoring $cov = L L^T$, $L$ bajar de forma triangular, de una vez, a continuación, la solución de $L x = x_{white}$ es bastante rápido; scipy.linalg.solve_triangular, por ejemplo, utiliza Lapack.
Yo estaba buscando una aún más rápido blanquear(), sigo buscando.

2voto

jldugger Puntos 7490

Simplemente informática de la matriz de covarianza--que vas a necesitar para empezar en cualquier caso--es$O((Nf)^2)$, por lo que, asintóticamente en $N$, no se gana nada por la elección de un $O(Nf)$ algoritmo para el blanqueamiento.

Hay aproximaciones cuando las variables tienen una estructura adicional, como por ejemplo cuando se forma una serie de tiempo o de la realización de un espaciales proceso estocástico en varios lugares. Estos efectivamente se basan en supuestos que nos permiten relacionar la covarianza entre un par de variables para que entre el resto de los pares de variables, tales como entre pares, separados por la misma época de los gal. Este es el convencional razón para suponer que el proceso es estacionario o intrínsecamente estacionaria, por ejemplo. Los cálculos pueden ser $O(Nflog(Nf)$ en estos casos (por ejemplo, el uso de la transformada Rápida de Fourier como en Yao & Journel 1998). Ausente un modelo de este tipo, no veo cómo se puede evitar la informática de todos los pares de covarianzas.

2voto

Factor Mystic Puntos 12465

En un capricho, me decidí a probar la informática (en R) la matriz de covarianza de un conjunto de datos sobre el tamaño de los mencionados en el OP:

z <- rnorm(1e8)
dim(z) <- c(1e6, 100)
vcv <- cov(z)

Este tomó menos de un minuto en total, en una forma bastante genérica portátil que ejecuta Windows XP de 32 bits. Probablemente tomó más tiempo para generar z en el primer lugar que para calcular la matriz vcv. Y R no está especialmente optimizada para operaciones de matriz fuera de la caja.

Dado este resultado, es la velocidad que importante? Si N >> p, el tiempo que se toma para calcular su aproximación es, probablemente, no va a ser mucho menor que para calcular la matriz de covarianza.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X