obliczanie skróconego SVD, pojedynczej wartości pojedynczej / wektora na raz

Czy istnieje skrócony algorytm SVD, który oblicza wartości osobliwe pojedynczo?

Mój problem: chciałbym obliczyć pierwsze wartości pojedynczych (i wektorów pojedynczych) dużej gęstej macierzy , ale nie wiem, jaka byłaby odpowiednia wartość . jest duży, więc ze względu na wydajność wolałbym nie oceniać pełnego SVD tylko po to, aby później obciąć najmniejsze SV.M k $k$$M$$k$$M$

Idealnie byłoby sposób na obliczenie wartości pojedynczych szeregowo, od największej ( ) do najmniejszej ( ). W ten sposób mógłbym po prostu zatrzymać obliczenia po obliczeniu tej liczby pojedynczej, jeśli spadnie poniżej pewnego progu.σ 1 σ n k σ k / σ $\sigma_1, \sigma_2,\ldots$$\sigma_1$$\sigma_n$$k$$\sigma_k/\sigma_1$

Czy taki algorytm istnieje (najlepiej z implementacją Pythona)? W mojej wyszukiwarce znalazłem tylko okrojone funkcje SVD, które przyjmują k jako parametr, co zmusza cię do odgadnięcia go z góry.

Dostępnych jest kilka opcji, jeśli chcesz uzyskać przybliżone współczynniki podziału na rangę.

1. Silnie odsłaniające rankingi QR
2. Rozkład interpolacyjny (ID) i inne techniki randomizowane.

Ogólnie rzecz biorąc, zapewniają one faktoryzację w postaci

Przybliżoną faktoryzację powyższej postaci można przekształcić w standardowy rozkład, taki jak QR lub SVD, przy użyciu standardowych technik. Dobry przegląd jest dostępny w artykule Halko, Martinsson i Tropp „Znalezienie struktury z przypadkowością: probabilistyczne algorytmy do konstruowania przybliżonych rozkładów macierzy”

Pod względem oprogramowania interfejs do algorytmów ID jest dostępny w scipy (scipy.linalg.interpolative) http://docs.scipy.org/doc/scipy-dev/reference/linalg.interpolative.html, który pozwala użytkownikowi określić .$\epsilon$

$k$

Jeśli wykluczysz podejście do obliczania całego SVD, częściowe algorytmy SVD ograniczają się do stosowania metod iteracyjnych w celu rozwiązania powiązanego problemu wartości własnej Hermitian. Tak więc jedną ze strategii, którą możesz zastosować, jest ręczne kodowanie tego rodzaju rzeczy i rozwiązywanie największej pozostałej nierozwiązanej pojedynczej wartości, dopóki nie będziesz chciał przestać, używając czegoś w rodzaju strategii zmiany i odwrócenia. Mogą istnieć eleganckie sposoby robienia tego rodzaju rzeczy w wyrafinowanych pakietach, takich jak SLEPc .

Inna strategia byłaby następująca:

• $s_{1}$
• $\tau \cdot s_{1} \cdot f$$\tau$$0 < f \leq 1$
• Zadzwoń do rzadkiej procedury SVD.

$k$