R manipulation interne des matrices clairsemées

Question

J'ai été de comparer la performance de plusieurs APC implémentations de Python et R, et a remarqué un comportement intéressant:
Alors qu'il semble impossible de calculer le PCA d'une matrice creuse en Python (la seule approche serait scikit-learn TruncatedSVD, mais il ne prend pas en charge la moyenne de centrage doivent être équivalent à une covariance solution pour cancer de la prostate. Leur argumentation est, qu'il détruirait la rareté des biens de la matrice. D'autres implémentations comme Facebook PCA de l'algorithme ou de la PCA/randomPCA méthode dans scikit learn ne prennent pas en charge matrices creuses pour des raisons similaires.

Alors que tout cela fait sens pour moi, plusieurs packages R, comme irlba, rsvd, etc., sont capables de gérer les matrices creuses (par exemple, généré avec rsparsematrix), et permettent même de spécifique center=True arguments.

Ma question est, comment R gère en interne, comme cela semble être beaucoup plus efficace que le comparable Python de mise en œuvre. Ne R toujours maintenir la densité en faisant Absolue de mise à l'Échelle au lieu (ce qui serait théoriquement de fausser les résultats, mais, au moins, maintenir sparsity)? Ou est-il de toute façon dans laquelle la moyenne peuvent être stockées de façon explicite pour les valeurs égales à zéro, et ne sont stockées qu'une seule fois (au lieu de pour chaque valeur séparément)?

Pour se mettre en garde: Comment R en interne stocker des matrices avec une moyenne de centrage sans explosion de l'utilisation de la RAM. Espère que c'est assez concis....

Answer 1

La clé ici est que les sous-tendent la mise en œuvre partielle SVD (redémarrage de Lanczos bidiagonalization code C) ne pas stocker la matrice. Au lieu de cela vous enregistrez le résultat de l'opération linéaire à partir de la matrice appliquée à un petit ensemble de vecteurs obtenus à partir de l'itération précédente.

Plutôt que d'expliquer le concret de la méthode utilisée dans le code c, ce qui est assez avancé (voir le document pour une description),je vais vous expliquer avec beaucoup plus simple algorithme qui permet de saisir l'idée clé en termes de la façon de préserver l'efficacité de rareté: la puissance de la méthode (ou le sous-espace d'itération de la méthode pour sa généralisation à plusieurs valeurs propres). L'algorithme renvoie la plus grande valeur propre d'une matrice A par itérative de l'application d'un opérateur linéaire, puis à la normale (ou orthogonalizing un petit ensemble de vecteurs, dans le cas de sous-espace d'itération)

Ce que vous faites à chaque itération est

v=A*v
v=v/norm(v)

La multiplication de matrice étape est cruciale, donc nous allons voir ce qui se passe quand on essaye de faire la même chose avec un centré A. La formule de matrice pour, centrée sur Un (avec center comme le vecteur avec la moyenne des valeurs de la colonne et de l' ones comme le vecteur de ceux) est:

A_center=A-ones*transpose(center)

Donc, si nous appliquons l'algorithme itératif de cette nouvelle matrice, nous aurions

v=A*v-dotproduct(center,v)*ones

Depuis Un clairsemés, nous pouvons utiliser la matrice creuse-produit vectoriel sur (A,v) et -dotproduct(center,v)*ones seulement implique soustrayant le produit scalaire de centre et v le vecteur résultant, qui est linéaire sur la dimension de l' A.