Mise à jour de la décomposition SVD après l'ajout d'une nouvelle ligne à la matrice

17

Supposons que j'ai une matrice dense de taille , avec décomposition SVDDans Je peux calculer la SVD comme suit: .Am×n

A=USV.
Rsvd(A)

Si une nouvelle -ème ligne est ajoutée à , peut-on calculer la nouvelle décomposition SVD sur la base de l'ancienne (c'est-à-dire en utilisant , et ), sans recalculer SVD à partir de zéro?(m+1)AUSV

user1436187
la source
3
Consultez la littérature de rank 1 updates. Les révisions SVD en ligne rapides pour les systèmes de recommandation légers par marque sont un premier article accessible. Je n'ai pas vu quelque chose pour SVD déjà implémenté dans R malheureusement. Les mises à jour Cholesky existent ( updowndepuis Matrix) grâce à CHOLMOD. La rareté de votre matrice A fera vraiment une différence par rapport à votre solution finale; supposez-vous une matrice dense ou clairsemée?
usεr11852 dit Réintégrer Monic
2
+1 à @ usεr11852. Notez également qu'il est beaucoup plus facile et plus standard de mettre à jour QR et que dans certaines applications QR suffit et que l'on n'a pas vraiment besoin de SVD. Pensez donc aussi à votre candidature.
amibe dit Réintégrer Monica
Oui, la matrice est dense.
user1436187
1
Abandonnez ensuite la documentation recommandée et concentrez-vous sur le traitement d'image. Des questions similaires avec des visites ont été publiées en termes de "nouvelles images" dans une base de données. Par exemple, mon intuition est que quelqu'un doit avoir un algorithme pour mettre à jour les entrées de ses faces propres en ligne. Ces gars travaillent avec des représentations matricielles denses.
usεr11852 dit Réintégrer Monic
Quelques discussions sur d'autres sites Web SE: scicomp.stackexchange.com/questions/2678 , scicomp.stackexchange.com/questions/19253 , mathoverflow.net/questions/143375 .
amibe dit Réintégrer Monica

Réponses:

14

Oui, on peut mettre à jour une décomposition SVD après avoir ajouté une nouvelle ligne à la matrice existante.

En général, cette formulation de problème " ajouter un à " est connue sous le nom de mises à jour de rang un . Le lien MathOverflow fourni par @amoeba sur les « mises à jour efficaces de rang deux d'une décomposition de valeurs propres » est une excellente première étape si vous voulez commencer à approfondir la question; le premier article fournit une solution explicite à votre question spécifique. Juste pour clarifier ce que signifient le rang un et le rang deux afin que vous ne soyez pas confus, si votre nouveau est tel que:A

A=AuvT

et v sont des vecteurs, vous vous référez à cela comme une mise à jour de premier rang (ou perturbation ). Les bases de cette mise à jour sont dictées par la formule Sherman-Morrison. . Si la perturbation est supérieure à un rang, c.-à-d. A = A - U V Tuv

A=AUVT

la formule de Woodbury entre en jeu. Si vous voyez ces formules, vous remarquerez qu'il y a beaucoup d'inverse impliqué. Vous ne les résolvez pas directement. Comme vous avez déjà résolu une grande partie de leurs sous-systèmes (c'est-à-dire que vous avez déjà une décomposition calculée), vous les utilisez pour obtenir des estimations plus rapides et / ou plus stables. (C'est pourquoi les gens font encore des recherches dans ce domaine.) J'ai beaucoup utilisé le livre " Computational Statistics " de JE Gentle comme référence; Je pense que Chapt. 5 L'algèbre linéaire numérique vous configurera correctement. (L'Uber-classique: " Matrix Algebra From a Statistician's Perspective " de Harville ne porte malheureusement pas sur les mises à jour de classement.)

En ce qui concerne les statistiques / applications, les mises à jour de rang 1 sont courantes dans les systèmes de recommandation car on peut avoir des milliers d'entrées client et recalculer le SVD (ou toute décomposition donnée d'ailleurs) chaque fois qu'un nouvel utilisateur s'inscrit ou qu'un nouveau produit est ajouté ou supprimé est un gaspillage (sinon impossible). Les matrices système généralement recommandées sont rares et cela rend les algorithmes encore plus efficaces. Un premier article accessible est le manuscrit « Révisions SVD en ligne rapides pour les systèmes de recommandation légers » de M. Brand. En ce qui concerne les matrices denses, je pense que regarder les articles de Pattern Recognition and Imaging Processing peut vous aider à obtenir un algorithme réel à utiliser. Par exemple les papiers:

  1. Apprentissage incrémental des principaux composants bidirectionnels pour la reconnaissance faciale (2009) par Ren et Dai,
  2. Sur l'apprentissage incrémental et robuste du sous-espace (2003) par Li et al.
  3. Extraction séquentielle de la base de Karhunen-Loeve et son application aux images (2000) par Levey et Lindenbaum.
  4. Apprentissage incrémental pour un suivi visuel robuste (2007) par Ross et al.

tous semblent s'attaquer au même problème dans leur cœur; de nouvelles fonctionnalités arrivent et nous devons mettre à jour notre représentation en conséquence rapidement . Notez que ces matrices ne sont pas symétriques ni même carrées. Un autre travail de M. Brand peut également résoudre ce problème (voir l'article " Modifications rapides de bas rang de la décomposition en valeurs singulières minces (2006) " - cela est également mentionné dans le lien MO donné au début de l'article). de nombreux articles sur le sujet, mais la plupart ont tendance à être fortement mathématiques (par exemple, l'article de Benaych-Georgesa et Nadakuditi sur « Les valeurs singulières et les vecteurs de perturbations de bas rang des grandes matrices aléatoires rectangulaires (2012)") et je ne pense pas qu'ils vous aideront à trouver une solution prochainement. Je vous suggère de vous concentrer sur la littérature sur le traitement d'images.

Malheureusement, je n'ai rencontré aucune implémentation R pour les routines de mise à jour de premier rang. La réponse « Mise en œuvre SVD actualisable en Python, C ou Fortran? » De Computational Science SE donne un certain nombre d'implémentations MATLAB et C ++ que vous voudrez peut-être envisager. Habituellement, l'implémentation R, Python, etc. sont des enveloppes autour des implémentations C, C ++ ou FORTRAN.

usεr11852 dit Reinstate Monic
la source
6
C'est un joli commentaire, mais j'ai été déçu de ne pas trouver de réponse à la question. Il s'avère qu'un autre article de Matthew Brand , lié à la réponse de MO, contient une solution explicite.
whuber
5
+1 à vous et à @whuber (et je ne pense pas que la "duplication" des informations fournies sur un autre site SE soit à éviter! Je dirais que nous devrions essayer de faire en sorte que les informations fournies sur ce site soient auto-entretenues En effet, presque toutes les informations contenues ici sont en quelque sorte des doublons de manuels existants, de ressources en ligne ou de documents de recherche). Une question: vous avez mentionné les formules de Sherman-Morrison et Woodbury qui décrivent comment l'inverse de la matrice change après une mise à jour de rang un ou de rang supérieur; qu'est-ce qu'ils ont à voir avec SVD?
amibe dit Réintégrer Monica
1
Je comprends pourquoi vous voudrez peut-être diriger les gens vers les pages MO pour ce lien, mais vous pourriez envisager de déclarer directement que cela résout le problème! («Un bon premier pas» est un euphémisme énorme.) Une grande partie de votre commentaire pourrait être mal interprétée comme indiquant que vous n'avez pas encore trouvé une bonne solution.
whuber
1
@whuber: "Good" est devenu "great" et maintenant j'ai aussi mentionné le papier, mieux? :) (Merci pour les commentaires en passant.)
usεr11852 dit Réintégrer Monic
2
Juste pour l'amour de l'histoire: Bunch et Nielsen ont été les premiers à démontrer un moyen de mettre à jour et de rétrograder le SVD. La méthode de Brand généralise en effet les méthodes de cet article plus ancien.
JM n'est pas statisticien le