calculer la SVD tronquée, une valeur / vecteur singulier à la fois

Existe-t-il un algorithme SVD tronqué qui calcule les valeurs singulières une par une?

Mon problème: je voudrais calculer les premières valeurs singulières (et vecteurs singuliers) d'une grande matrice dense M , mais je ne sais pas ce que serait une valeur appropriée de k . M est grand, donc pour des raisons d'efficacité, je préfère ne pas évaluer le SVD complet uniquement pour tronquer les plus petits SV par la suite.$k$$M$$k$$M$

Idéalement, il y aurait un moyen de calculer les valeurs singulières série, de la plus grande ( σ 1 ) à la plus petite ( σ n ). De cette façon, je pourrais simplement arrêter le calcul après avoir calculé la k ème valeur singulière si σ k / σ 1 tombe en dessous d'un certain seuil.$\sigma_1, \sigma_2,\ldots$$\sigma_1$$\sigma_n$$k$$\sigma_k/\sigma_1$

Un tel algorithme existe-t-il (de préférence avec une implémentation Python)? Dans mes recherches, je n'ai trouvé que des fonctions SVD tronquées qui prennent k en paramètre, vous forçant ainsi à le deviner a priori.

Il y a quelques options disponibles si vous voulez une factorisation approximative de rang k.

1. Factorisations QR très révélatrices de rang
2. Décomposition interpolative (ID) et autres techniques randomisées.

Une factorisation approximative de la forme ci-dessus peut être convertie en une décomposition standard comme QR ou SVD en utilisant des techniques standard. Une bonne revue est disponible dans l'article de Halko, Martinsson et Tropp "Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions"

$\epsilon$

$k$

Si vous excluez l'approche du calcul de la SVD entière, les algorithmes de SVD partiels se réduisent à l'utilisation de méthodes itératives pour résoudre un problème de valeur propre hermitien connexe. Ainsi, une stratégie que vous pourriez prendre serait de coder manuellement ce genre de chose et de continuer à résoudre pour la plus grande valeur singulière non résolue jusqu'à ce que vous vouliez arrêter, en utilisant quelque chose comme une stratégie de décalage et d'inversion. Il peut y avoir des façons élégantes de faire ce genre de choses dans des packages sophistiqués comme SLEPc .

Une autre stratégie serait la suivante:

• $s_{1}$
• $\tau \cdot s_{1} \cdot f$$\tau$$0 < f \leq 1$
• Appelez la routine SVD clairsemée.

$k$