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

8

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×Acov(X)
A=LLTLLi i1LiiLx=xwhiteO(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)XN×Nf×

1) construa , Cholesky o fator como , resolva para embranquecer novos s. Isso é quadrático no número de recursos.Fullcov=XTXLLTLx=xwhitex

2) diagonal: ignora completamente as correlações cruzadas.xwhite=x/σ(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


(Adicionado em 11 de maio): Deixe-me dividir a pergunta em duas:

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)
(N2)

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=LLTLLx=xwhite

denis
fonte
As colunas têm uma ordem natural para elas? Ou você deseja encontrar uma aproximação tridiagonal sob alguma permutação ("ótima") das colunas? Estou assumindo que, quando você diz está falando da estrutura de covariância dos recursos. Você pode confirmar isso? A=Cov(X)
cardeal
Não, não há pedidos naturais e, sim, covariância dos 100 recursos. Os métodos que somam uma matriz de covariância completa e depois a aproximam seria >> O (tamanho X); Estou procurando uma aproximação rápida e simples, que será necessariamente grosseira.
Denis
Então, você quer uma aproximação tridiagonal sob alguma permutação (a ser determinada pelos dados), sim?
cardeal
adicionado, tentou esclarecer. Se uma permutação boa (satisfatória) pudesse ser encontrada em O (Nfeatures), sim, isso serviria.
Denis
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. Os cálculos podem ser , nesses casos, tal modelo um Ausente, eu não vejo como você pode evitar computação todos covariâncias pares..O(Nflog(Nf)
whuber

Respostas:

2

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)NO(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)

whuber
fonte
2

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.

Hong Ooi
fonte