Comment calculer la SVD d'une énorme matrice clairsemée?

26

Quelle est la meilleure façon de calculer la décomposition en valeurs singulières (SVD) d'une très grande matrice positive (65M x 3,4M) où les données sont extrêmement rares?

Moins de 0,1% de la matrice n'est pas nul. J'ai besoin d'un moyen qui:

  • s'inscrira dans la mémoire (je sais qu'il existe des méthodes en ligne)
  • sera calculé dans un délai raisonnable: 3,4 jours
  • sera suffisamment précis, mais la précision n'est pas ma principale préoccupation et je voudrais pouvoir contrôler la quantité de ressources que j'y consacre.

Ce serait formidable d'avoir une bibliothèque Haskell, Python, C # etc. qui l'implémente. Je n'utilise pas mathlab ou R mais si nécessaire je peux aller avec R.

svd numerics Sonia
la source
3
De combien de mémoire disposez-vous? 0,1% de 65M * 3,4M est toujours 221e9 des valeurs non nulles. Si vous utilisez 4 octets par valeur, c'est toujours plus de 55 Go en supposant qu'il n'y ait pas de surcharge, donc la rareté ne résout toujours pas le problème ... Avez-vous besoin de charger l'ensemble entier en mémoire à la fois?
Bitwise
J'aurais dû être plus précis. Pas plus de 250-500 Mo avec un entier 32 bits. Probablement beaucoup moins, mais la dimensionnalité est le problème tel que je le comprends. J'ai une machine de 16 Go.
Sonia
Que dis-tu de ça? quora.com/...
Bitwise
Cette page Web renvoie à une bibliothèque Python qui implémente "un algorithme SVD rapide, incrémentiel, à faible mémoire et à grande matrice": en.wikipedia.org/wiki/Latent_semantic_analysis
Bitwise
Voir aussi stats.stackexchange.com/questions/2806 .
amibe dit Réintégrer Monica

Réponses:

21

S'il tient dans la mémoire, construisez une matrice clairsemée dans R à l'aide du package Matrix et essayez irlba pour le SVD. Vous pouvez spécifier combien de vecteurs singuliers vous voulez dans le résultat, ce qui est une autre façon de limiter le calcul.

C'est une assez grosse matrice, mais j'ai eu de très bons résultats avec cette méthode dans le passé. irlbaest assez à la pointe de la technologie. Il utilise l' algorithme de bi-diagonalisation Lanczos redémarré implicitement .

Il peut parcourir l'ensemble de données de prix netflix (480 189 lignes par 17 770 colonnes, 100 480 807 entrées non nulles) en millisecondes. Votre ensemble de données est ~ 200 000 fois plus grand que l'ensemble de données Netflix, donc cela prend beaucoup plus de temps que cela. Il pourrait être raisonnable de s'attendre à ce qu'il puisse effectuer le calcul en quelques jours.

Zach
la source
la matrice de données s'inscrit dans la mémoire, irlba gérera-t-il également la décomposition de manière efficace?
Sonia
@Sonia: irlba est très efficace en mémoire: il calcule une solution approximative, vous pouvez limiter le nombre de vecteurs singuliers, et il a été conçu pour fonctionner sur des matrices clairsemées. Pour autant que je sache, c'est aussi rapide que vous obtiendrez pour calculer des SVD partiels.
Zach
@Sonia: Bonne chance!
Zach
Je lui ai donné un essai - de mémoire ... Je vais calculer une forme de bloc triangle avant de l'exécuter.
Sonia
@Sonia l'avez-vous stocké en tant que clairsemé Matrix? Essayez de limiter le nombre de valeurs singulières que vous calculez ... regardez peut-être simplement le top 10?
Zach