Quel est l'état actuel de la technique concernant les algorithmes de décomposition de valeurs singulières?

12

Je travaille sur une bibliothèque de matrices uniquement en-tête pour fournir un certain degré raisonnable de capacité d'algèbre linéaire dans un package aussi simple que possible, et j'essaie de faire le point sur l'état actuel de la technique: le calcul de la SVD d'un matrice complexe.

Je fais une décomposition en deux phases, une bidiagonalisation suivie d'un calcul de valeurs singulières. En ce moment, j'utilise la méthode des ménages pour la bidiagonalisation (je crois que LAPACK l'utilise également), et je pense que c'est à peu près aussi bon qu'il l'est actuellement (à moins que quelqu'un ne connaisse un algorithme pour ça..). O(N2)

Le calcul des valeurs singulières est le suivant sur ma liste, et je suis un peu en dehors de la boucle sur les algorithmes courants pour ce faire. J'ai lu ici que la recherche se dirigeait vers une méthode d'itération inverse qui garantit l'orthogonalité avec la complexité . Je serais intéressé d'en entendre parler ou d'autres avancées.O(N)

linear-algebra matrix svd gct
la source
existe-t-il un document pour votre matrice de lib uniquement en-tête (à part le .h)? Veuillez également ajouter la balise "svd".
denis

Réponses:

7

Les "algorithmes randomisés" sont récemment devenus très populaires pour les SVD partiels. Une implémentation uniquement en-tête peut être téléchargée ici: http://code.google.com/p/redsvd/

Une revue des méthodes actuelles peut être trouvée ici: http://arxiv.org/abs/0909.4061

Pour les svd complets, je ne sais pas si vous pouvez faire mieux que Householder.

dranxo
la source
Cela semble très intéressant, je vais devoir jeter un œil à ce document d'enquête, merci!
gct
OP s'intéresse aux algorithmes pour les matrices denses. Je ne pense pas que les algorithmes randomisés soient compétitifs dans ce contexte, s'ils fonctionnent.
Federico Poloni
Ce post a indiqué que les méthodes randomisées fonctionnent très bien sur les matrices denses research.facebook.com/blog/294071574113354/fast-randomized-svd
dranxo
@dranxo Il n'y a aucune comparaison de précision sur ce post, et les résultats de synchronisation ne semblent pas très méticuleux. De plus, les algorithmes randomisés sont basés sur la projection + la solution exacte d'un problème à petite échelle. Cela signifie que l'OP aurait de toute façon besoin d'une implémentation d'une "méthode standard" pour le problème à petite échelle qui en résulte.
Federico Poloni
C'est suffisant. Bien que je sois un peu confus pourquoi nous devrions penser que ces méthodes ne fonctionnent que sur des matrices clairsemées. À droite de l'abstrait de l'article de Joel Tropp: "Pour une matrice d'entrée dense, les algorithmes randomisés nécessitent O (mn log (k)) opérations en virgule flottante (flops) en contraste avec O (mnk) pour les algorithmes classiques." arxiv.org/pdf/0909.4061v2.pdf
dranxo
4

J'ai lu ici que la recherche se dirigeait vers une méthode d'itération inverse qui garantit l'orthogonalité avec la complexité . Je serais intéressé d'en entendre parler ou d'autres avancées.O(N)

(Je voulais juste faire quelques commentaires car je n'ai pas le temps d'écrire les détails, mais c'est devenu assez gros pour la zone de commentaire.)

Je pense que ce serait l' algorithme MRRR (plusieurs représentations relativement robustes) de Dhillon et Parlett. Ceci est enraciné dans les travaux antérieurs de Fernando, qui à son tour a été inspiré par un problème posé par Jim Wilkinson dans son livre monumental sur les problèmes de valeurs propres. La partie "itération inverse" pour obtenir des vecteurs singuliers est enracinée dans le concept de "factorisations torsadées" par Fernando , qui utilise des matrices de factorisation en et décompositions .U D U ⊤LDL⊤UDU⊤

La partie "valeur singulière" de l'algorithme, d'autre part, provient de l'algorithme (décalé) de différence de quotient différentiel (dqd (s)) , qui est l'aboutissement de travaux antérieurs de Fernando, Parlett , Demmel et Kahan (avec inspiration de Heinz Rutishauser).

Comme vous le savez peut-être, les méthodes SVD procèdent généralement à une décomposition bidiagonale avant que les valeurs singulières soient obtenues à partir de la matrice bidiagonale. Malheureusement, je ne suis pas trop à jour sur la meilleure méthode actuelle pour la décomposition bidiagonale frontale; la dernière fois que j'ai vérifié, la méthode habituelle est de commencer par la décomposition QR avec pivotement des colonnes, puis d'appliquer les transformations orthogonales de manière appropriée au facteur triangulaire pour finalement obtenir la décomposition bidiagonale.

Je comprends que j'ai été maigre avec les détails; J'essaierai d'étoffer cette réponse une fois que j'aurai accès à ma bibliothèque ...

JM
la source
Matrice à la forme bi-diagonale, faites une colonne puis une ligne, répétez en bas de la diagonale: utilisez des données ou un chef de ménage pour mettre à zéro la colonne jusqu'à la diagonale, puis faites de même pour la ligne jusqu'à la super-diagonale.
adam W
Ignorer mon commentaire précédent, je pensais à la forme tri-diagonale. Pardon. La bi-diagonalisation n'est pas triviale dans une similitude (elle révélerait en fait les valeurs propres), mais votre référence ne fait pas une similitude, elle fait autre chose; gauche et droite se multiplient avec différentes matrices orthogonales. est bi-diagonal avec et , ce qui peut être fait comme vous le dites avec QR en premier, mais pas si facilement décrit dans un commentaire. Je serais peut-être intéressé si vous étoffez la réponse plus loin (mais je pourrais aussi le comprendre car mes études vont dans ce sens en ce moment). U U ⊤ = I V V ⊤ = IUAVUU⊤=IVV⊤=I
adam W