É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) .)
(Ajouté, en essayant de clarifier): Je recherche un blanchisseur rapide et sale qui est plus rapide que le cov complet (X) mais meilleur que la diagonale. Supposons que est points de données caractéristiques, par exemple 1000000 100, avec des caractéristiques à 0 moyenne.
1) construire , factoriser Cholesky comme , résoudre pour blanchir de nouveaux s. C'est quadratique dans le nombre de fonctionnalités.
2) diagonale: ignore complètement les corrélations croisées.
On pourrait obtenir une matrice tridiagonale de 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) ?
Non (whuber), il faut regarder toutes les paires (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.
Réponses:
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) N O(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)
la source
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:
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
z
en premier lieu que pour calculer la matricevcv
. 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.
la source