Quels sont les algorithmes efficaces pour calculer la décomposition en valeurs singulières (SVD)?

17

L'article de Wikipedia sur l' analyse des composants principaux indique que

Il existe des algorithmes efficaces pour calculer la SVD de sans avoir à former la matrice , donc le calcul de la SVD est désormais le moyen standard de calculer une analyse des composants principaux à partir d'une matrice de données, à moins qu'une poignée de composants seulement soit requise.XXTX

Quelqu'un pourrait-il me dire quels sont les algorithmes efficaces dont parle l'article? Aucune référence n'est donnée (URL ou citation d'un article proposant ce mode de calcul serait bien).

pca algorithms svd numerics svd
la source
4
Une recherche Google sur l' algorithme de décomposition de valeurs singulières fait un excellent travail de mise en évidence des informations pertinentes.
whuber
1
N'oubliez pas de supprimer la moyenne avant SVD pour PCA!
Memming
Essayez Lanczos SVD!
ciri

Réponses:

12

Le principal cheval de bataille derrière le calcul de SVD est l' algorithme QR . Cela dit , il existe de nombreux algorithmes différents pour calculer la décomposition en valeurs singulières d'un générique de matrice . Un excellent schéma sur le problème disponible ici (à partir de la documentation du MKL d'Intel ) est le suivant:MNUNEentrez la description de l'image ici

Comme vous le voyez, selon votre cas d'utilisation, il existe différentes approches (les conventions de dénomination de routine peuvent être trouvées ici ). C'est parce que, par exemple, il existe des formes matricielles où une réduction du nombre de ménages peut être plus coûteuse qu'une rotation de Givens (pour nommer deux façons "évidentes" d'obtenir QR). Une référence standard en la matière est les calculs matriciels de Golub et Van Loan (je suggérerais d'utiliser au moins la 3e édition). J'ai également trouvé Å. Méthodes numériques de Björck pour les problèmes des moindres carrés très bonne ressource à ce sujet; tandis que SVD n'est pas l'objectif principal du livre, il aide à contextualiser son utilisation.

Si je dois vous donner un conseil général à ce sujet, n'essayez pas d'écrire vos propres algorithmes SVD, sauf si vous avez déjà suivi avec succès quelques cours d'algèbre linéaire numérique et que vous savez ce que vous faites. Je sais que cela semble contre-intuitif mais vraiment, il y a une tonne de choses qui peuvent mal tourner et vous vous retrouvez avec (au mieux) des implémentations sous-optimales (sinon erronées). Il y a de très bonnes suites gratuites sur la question (par exemple. Eigen , Armadillo et Trilinos pour n'en nommer que quelques-unes.)

usεr11852 dit Reinstate Monic
la source
La question portait sur le calcul de la SVD de la matrice de données, pas de sa matrice de covariance (en utilisant votre notation, , pas ). L'algorithme QR n'est-il pas applicable uniquement aux matrices carrées? Si oui, comment peut-il aider à calculer la SVD de la matrice de données (non carrée)? XUNE
Amoeba dit Reinstate Monica
1
MNUNEXTX
2
Oui, j'avais tort: ​​QR n'est pas limité aux matrices carrées. +1, au fait. Cette question était l'une des questions sans réponse les plus votées avec la balise pca , il est donc agréable de voir enfin sa réponse.
Amoeba dit Reinstate Monica
Votre réponse ne mentionne pas toute une variété d'algorithmes itératifs. Était-ce exprès? Quelqu'un a posé une question sur les algorithmes SVD itératifs, voir Quels algorithmes rapides existent pour calculer la SVD tronquée? , et j'y ai posté une réponse en essayant de donner un aperçu. Peut-être devrions-nous au moins croiser nos réponses. Et ce serait certainement formidable si vous pouvez étendre le vôtre en discutant des algorithmes QR par rapport aux algorithmes itératifs.
amibe dit Réintégrer Monica le
Non, c'était accidentel. Vous avez répondu à votre propre question dans votre message; les SVD tronquées sont essentiellement des compositions d’égend tronquées (voir par exemple ARPACK ). Il y a de belles différences mais elles sont bien ; certains logiciels (par exemple MATLAB svds) vont jusqu'à utiliser simplement leur fonction SVD tronquée comme enveloppe pour leurs eigsroutines eigendecomposition ( ) tronquées .
usεr11852 dit Réintégrer Monic le