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

11

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. $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. $\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.

linear-algebra algorithms svd

— SuperElectric
źródło

Czy Twój M jest kwadratowy czy prostokątny? Jeśli jest prostokątny, czy potrzebujesz długich czy krótkich pojedynczych wektorów? To znaczy, jeśli M jest (mxn) z m> n, czy chcesz (mxk) czy (kxn)?

— Max Hutchinson

M jest prostokątny, z większą ilością rzędów niż kolumn. Chcę krótkich wektorów pojedynczych (tj. V, w M = U S V ^ T).

— SuperElectric

6

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

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

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

‖ A - M N^{T} ‖ \leq factor \times σ_{k + 1} (A) := ϵ

$\begin{equation}\| A - MN^T\| \leq \text{factor}\times \sigma_{k+1}(A) := \epsilon \end{equation}$

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$

— użytkownik2457602
źródło

2

$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$

— Geoff Oxberry
źródło

Jeśli nie określisz „k” w scipy.sparse.linalg.svds, domyślnie będzie to k = 6, niezależnie od parametru „tol”. Nie jest jasne, czy jest to błąd, czy „tol” ma odnosić się do dokładności obliczonych wartości pojedynczych (a nie ich wielkości)

— Nick Alger