Como calcular a matriz de covariância aproximada tridiagonal, para rápida correlação?

Dada uma matriz de dados digamos 1000000 observações 100 recursos, existe uma maneira rápida de construir uma aproximação tridiagonal ? Então, pode-se fatorar , todos 0, exceto e , e realizar uma correlação rápida (clareamento) resolvendo . (Por "rápido", quero dizer .)$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 )$

(Adicionado, tentando esclarecer): Estou procurando um branqueador rápido e sujo que seja mais rápido que o completo mas melhor que a diagonal. Digamos que seja pontos de dados recursos, por exemplo, 1000000 100, com recursos 0-média.$cov(X)$$X$$N$$\times Nf$$\times$

1) construa , Cholesky o fator como , resolva para embranquecer novos s. Isso é quadrático no número de recursos.$Fullcov = X^T X$$L L^T$$L x = x_{white}$$x$

2) diagonal: ignora completamente as correlações cruzadas.$x_{white} = x / \sigma(x)$

Um poderia obter uma matriz tridiagonal de apenas zerando todas as entradas fora do tridiagonal, ou não acumular-los em primeiro lugar. E aqui começo a afundar: deve haver uma melhor aproximação, talvez hierárquica, de bloco diagonal → tridiagonal?$Fullcov$

1) existe um aproximado rápido ? Não (whuber), é preciso olhar para todos os {N \ escolher 2} pares (ou ter estrutura ou amostra).$cov(X)$
${N \choose 2}$

2) dado um , com que rapidez se pode embranquecer novos s? Bem, fatorar , triangular inferior, uma vez, e resolver é bem rápido; scipy.linalg.solve_triangular, por exemplo, usa Lapack. Eu estava procurando por um branqueamento ainda mais rápido (), ainda procurando.$cov(X)$$x$
$cov = L L^T$$L$$L x = x_{white}$

O simples cálculo da matriz de covariância - que você precisará iniciar em qualquer caso - é Assim, assintoticamente em , nada é ganho ao escolher um algoritmo para o branqueamento.$O((Nf)^2)$$N$$O(Nf)$

Existem aproximações quando as variáveis ​​possuem estrutura adicional, como quando formam uma série temporal ou realizações de um processo estocástico espacial em vários locais. Elas se baseiam efetivamente em suposições que permitem relacionar a covariância entre um par de variáveis ​​com a de outros pares de variáveis, como entre pares separados pelos mesmos atrasos de tempo. Essa é a razão convencional para assumir que um processo é estacionário ou intrinsecamente estacionário , por exemplo. Os cálculos podem ser nesses casos ( por exemplo , usando a Transformada Rápida de Fourier como em Yao & Journel 1998 ). Na ausência desse modelo, não vejo como você pode evitar o cálculo de todas as covariâncias aos pares.$O(Nflog(Nf)$

Por um capricho, decidi tentar computar (em R) a matriz de covariância para um conjunto de dados do tamanho mencionado no OP:

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

Isso levou menos de um minuto no total, em um laptop bastante genérico executando o Windows XP de 32 bits. Provavelmente, levou mais tempo para gerar zem primeiro lugar do que para calcular a matriz vcv. E R não é particularmente otimizado para operações matriciais prontas para uso.

Dado esse resultado, a velocidade é importante? Se N >> p, o tempo necessário para calcular sua aproximação provavelmente não será muito menor do que obter a matriz de covariância real.