Comment calculer la matrice de covariance approximative tridiagonale, pour une décorrélation rapide?

8

Étant donné une matrice de données de 1000000 observations 100 entités, existe-t-il un moyen rapide de construire une approximation tridiagonale ? On pourrait alors factoriser , tous 0 sauf et L_ {ii} , et faire une décorrélation rapide (blanchiment) en résolvant L x = x_ {blanc} . (Par "rapide", je veux dire O (taille \ X) .)X×Acov(X)
A=LLTLLi i1LiiLx=xwhiteO(size X)

(Ajouté, en essayant de clarifier): Je recherche un blanchisseur rapide et sale qui est plus rapide que le cov complet (X)cov(X) mais meilleur que la diagonale. Supposons que X est N points de données ×Nf caractéristiques, par exemple 1000000 × 100, avec des caractéristiques à 0 moyenne.

1) construire Fullcov=XTX , factoriser Cholesky comme LLT , résoudre Lx=xwhite pour blanchir de nouveaux x s. C'est quadratique dans le nombre de fonctionnalités.

2) diagonale: xwhite=x/σ(x) ignore complètement les corrélations croisées.

On pourrait obtenir une matrice tridiagonale de Fullcov simplement en mettant à zéro toutes les entrées en dehors de la tridiagonale, ou en ne les accumulant pas en premier lieu. Et là je commence à couler: il doit y avoir une meilleure approximation, peut-être hiérarchique, bloc diagonal → tridiagonal?


(Ajouté le 11 mai): Permettez-moi de diviser la question en deux:

1) existe-t-il une cov approximative rapide (X)cov(X) ?
Non (whuber), il faut regarder toutes les paires (N2) (ou avoir une structure, ou un échantillon).

2) étant donné un , à quelle vitesse peut-on blanchir de nouveaux s? Eh bien, factoriser , triangulaire inférieur, une fois, puis résoudre est assez rapide; scipy.linalg.solve_triangular, par exemple, utilise Lapack. Je cherchais un blanc encore plus rapide (), toujours à la recherche.cov(X)x
cov=LLTLLx=xwhite

denis
la source
Les colonnes ont-elles un ordre naturel? Ou voulez-vous trouver une approximation tridiagonale sous une permutation ("optimale") des colonnes? Je suppose que lorsque vous dites vous parlez de la structure de covariance des caractéristiques. Pouvez-vous le confirmer? A=Cov(X)
cardinal
Non, il n'y a pas d'ordre naturel et oui, la covariance des 100 fonctionnalités. Les méthodes qui additionnent une matrice de covariance complète, puis l'approximent, seraient >> O (taille X); Je recherche une approximation simple et rapide, qui sera forcément grossière.
denis
Donc, vous voulez une approximation tridiagonale sous une certaine permutation (à déterminer par les données), oui?
cardinal
ajouté, essayé de clarifier. Si une bonne permutation (satisfaisante) pouvait être trouvée dans O (Nfeatures), oui, cela ferait l'affaire.
denis
Il existe des approximations lorsque les variables ont une structure supplémentaire, par exemple lorsqu'elles forment une série chronologique ou la réalisation d'un processus stochastique spatial à divers emplacements. Ceux-ci reposent effectivement sur des hypothèses qui permettent de relier la covariance entre une paire de variables à celle entre d'autres paires de variables, comme entre des paires séparées par les mêmes décalages temporels. Les calculs peuvent être dans de tels cas. En l'absence d'un tel modèle, je ne vois pas comment vous pouvez éviter de calculer toutes les covariances par paires.O(Nflog(Nf)
whuber

Réponses:

2

Le simple calcul de la matrice de covariance - dont vous aurez besoin pour commencer dans tous les cas - est donc, asymptotiquement dans , rien n'est gagné en choisissant un algorithme pour le blanchiment.O((Nf)2)NO(Nf)

Il existe des approximations lorsque les variables ont une structure supplémentaire, par exemple lorsqu'elles forment une série chronologique ou la réalisation d'un processus stochastique spatial à divers emplacements. Ceux-ci reposent effectivement sur des hypothèses qui permettent de relier la covariance entre une paire de variables à celle entre d'autres paires de variables, comme entre des paires séparées par les mêmes décalages temporels. C'est la raison conventionnelle pour supposer qu'un processus est stationnaire ou intrinsèquement stationnaire , par exemple. Les calculs peuvent être dans de tels cas ( par exemple , en utilisant la transformée de Fourier rapide comme dans Yao & Journel 1998 ). En l'absence d'un tel modèle, je ne vois pas comment vous pouvez éviter de calculer toutes les covariances par paire.O(Nflog(Nf)

whuber
la source
2

Sur un coup de tête, j'ai décidé d'essayer de calculer (en R) la matrice de covariance pour un ensemble de données de la taille mentionnée dans l'OP:

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

Cela a pris moins d'une minute au total, sur un ordinateur portable assez générique fonctionnant sous Windows XP 32 bits. Il a probablement fallu plus de temps pour générer zen premier lieu que pour calculer la matrice vcv. Et R n'est pas particulièrement optimisé pour les opérations matricielles prêtes à l'emploi.

Compte tenu de ce résultat, la vitesse est-elle si importante? Si N >> p, le temps nécessaire pour calculer votre approximation ne sera probablement pas beaucoup moins important que pour obtenir la matrice de covariance réelle.

Hong Ooi
la source