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

Dada una matriz de datos de digamos 1000000 observaciones 100 características, ¿hay una manera rápida de construir una aproximación tridiagonal ? Entonces uno podría factorizar , todos 0 excepto y , y realizar una rápida descorrelación (blanqueamiento) resolviendo . (Por "rápido" me refiero a .) $X$ $\times$ $A \approx cov(X)$
$A = L L^T$ $L$ $L_{i\ i-1}$ $L_{i i}$ $L x = x_{white}$ $O( size\ X )$

(Agregado, tratando de aclarar): estoy buscando un blanqueador rápido y sucio que sea más rápido que el completo pero mejor que la diagonal. Digamos que es puntos de datos características, por ejemplo, 1000000 100, con características 0-mean. $cov(X)$ $X$ $N$ $\times Nf$ $\times$

1) construya , factor Cholesky como , resuelva para blanquear nuevas s. Esto es cuadrático en la cantidad de características. $Fullcov = X^T X$ $L L^T$ $L x = x_{white}$ $x$

2) diagonal: ignora las correlaciones cruzadas por completo. $x_{white} = x / \sigma(x)$

Se podría obtener una matriz tridiagonal de simplemente a cero todas las entradas fuera del tridiagonal, o no acumulándolas en primer lugar. Y aquí empiezo a hundirme: ¿debe haber una mejor aproximación, quizás jerárquica, diagonal de bloque → tridiagonal? $Fullcov$

(Agregado el 11 de mayo): Déjame dividir la pregunta en dos:

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

2) dado un , ¿qué tan rápido se puede blanquear nuevos s? Bueno, factorizando , triangular inferior, una vez, luego resolver es bastante rápido; scipy.linalg.solve_triangular, por ejemplo, usa Lapack. Estaba buscando un blanqueamiento aún más rápido (), todavía buscando. $cov(X)$ $x$
$cov = L L^T$ $L$ $L x = x_{white}$

variance approximation covariance-matrix denis
fuente

¿Las columnas tienen un orden natural para ellos? ¿O desea encontrar una aproximación tridiagonal bajo alguna permutación ("óptima") de las columnas? Supongo que cuando dices estás hablando de la estructura de covarianza de las características. ¿Puedes confirmar esto?

A = C o v (X)

$A = \mathrm{Cov}(X)$

Cardenal

No, no hay ordenamiento natural, y sí, covarianza de las 100 características. Los métodos que suman una matriz de covarianza completa y luego la aproximan serían >> O (tamaño X); Estoy buscando una aproximación simple y rápida, que necesariamente será cruda.

denis

Entonces, ¿quieres una aproximación tridiagonal bajo alguna permutación (a ser determinada por los datos), sí?

Cardenal

agregado, trató de aclarar. Si se pudiera encontrar una buena (satisfactoria) permutación en O (Nfeatures), sí, eso sería suficiente.

denis

Hay aproximaciones cuando las variables tienen una estructura adicional, como cuando forman una serie temporal o realizaciones de un proceso estocástico espacial en varias ubicaciones. Éstos se basan efectivamente en suposiciones que nos permiten relacionar la covarianza entre un par de variables y la existente entre otros pares de variables, como entre pares separados por los mismos retrasos de tiempo. Los cálculos pueden ser en tales casos. En ausencia de tal modelo, no veo cómo puede evitar calcular todas las covarianzas por pares.

O (N f \log (N f)

$O(Nf \log(Nf)$

whuber

Respuestas:

Simplemente calcular la matriz de covarianza, que necesitará para comenzar en cualquier caso, es , por lo que, asintóticamente en , no se gana nada eligiendo un algoritmo para el blanqueo. $O((Nf)^2)$ $N$ $O(Nf)$

Hay aproximaciones cuando las variables tienen una estructura adicional, como cuando forman una serie temporal o realizaciones de un proceso estocástico espacial en varias ubicaciones. Éstos se basan efectivamente en suposiciones que nos permiten relacionar la covarianza entre un par de variables y la existente entre otros pares de variables, como entre pares separados por los mismos retrasos de tiempo. Esta es la razón convencional para suponer que un proceso es estacionario o intrínsecamente estacionario , por ejemplo. Los cálculos pueden ser en tales casos ( p . Ej. , Utilizando la Transformada rápida de Fourier como en Yao & Journel 1998 ). En ausencia de tal modelo, no veo cómo puede evitar calcular todas las covarianzas por pares. $O(Nflog(Nf)$

whuber
fuente

Por capricho, decidí intentar calcular (en R) la matriz de covarianza para un conjunto de datos de aproximadamente el tamaño mencionado en el OP:

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

Esto tomó menos de un minuto en total, en una computadora portátil bastante genérica con Windows XP de 32 bits. Probablemente tomó más tiempo generar zen primer lugar que calcular la matriz vcv. Y R no está particularmente optimizado para operaciones matriciales listas para usar.

Dado este resultado, ¿es tan importante la velocidad? Si N >> p, el tiempo necesario para calcular su aproximación probablemente no será mucho menor que para obtener la matriz de covarianza real.

Hong Ooi
fuente