Szybkie ustalenie, czy gęsta matryca ma niską rangę

13

W projekcie oprogramowania, nad którym pracuję, niektóre obliczenia są znacznie łatwiejsze dla gęstych matryc niskiej rangi. Niektóre przypadki problemów dotyczą gęstych macierzy niskiej rangi, ale są one podane mi w całości, a nie jako czynniki, więc muszę sprawdzić pozycję i matrycę macierzy, jeśli chcę skorzystać z struktury niskiej rangi .

Omawiane macierze są zazwyczaj całkowicie lub prawie całkowicie gęste, przy czym n wynosi od stu do kilku tysięcy. Jeśli matryca ma niską rangę (powiedzmy mniej niż 5 do 10), to warto obliczyć SVD i użyć jej z faktoryzacji niskiej rangi. Jeśli jednak matryca nie ma niskiej rangi, wysiłek zostałby zmarnowany.

Dlatego chciałbym znaleźć szybki i racjonalnie niezawodny sposób ustalenia, czy ranga jest niska, przed zainwestowaniem wysiłku w pełną faktoryzację SVD. Jeśli w dowolnym momencie stanie się jasne, że ranga znajduje się powyżej granicy, proces może zostać natychmiast zatrzymany. Jeśli procedura błędnie stwierdza, że matryca ma niską rangę, gdy nie jest, nie jest to ogromny problem, ponieważ nadal robiłbym pełny SVD, aby potwierdzić niską rangę i znaleźć faktoryzację niskiej rangi.

Opcje, które rozważałem, obejmują rangę ujawniającą faktoryzację LU lub QR, a następnie pełną SVD jako czek. Czy są inne podejścia, które powinienem rozważyć?

— Brian Borchers
źródło

8

$k$

[\begin{matrix} R_{1} & R_{12} \\ 0 & R_{22} \end{matrix}],

$\begin{bmatrix} R_1 & R_{12}\\ 0 & R_{22} \end{bmatrix},$

R_{1}

$R_1$

k \times k

$k\times k$

R_{22}

$R_{22}$

k

$k$

‖ R_{22} ‖ \leq ε

$\|R_{22}\| \leq \varepsilon$

A

$A$

ε

$\varepsilon$ z macierzy rang ; w przeciwnym razie nie powinno tak być (z wyjątkiem błędów numerycznych).

\leq k

$\leq k$

Ta procedura kosztuje dla gęstej matrycy. $O(n^2k)$ $n\times n$

— Federico Poloni
źródło

Zasadniczo takie podejście opisałem w pytaniu. Myślę, że proponowana odpowiedź Wolfganga Bangertha może być lepsza niż .

O (n^{2} k)

$O(n^{2}k)$

— Brian Borchers,

7

Problem polega oczywiście na tym, że obliczenie prawdziwej rangi (np. Za pomocą rozkładu QR) nie jest tak naprawdę tańsze niż obliczenie macierzy niskiego rzędu.

Najlepsze, co prawdopodobnie możesz zrobić, to użyć losowego algorytmu, aby znaleźć przybliżenia niskiej rangi. Mogą one, przynajmniej teoretycznie, być znacznie szybsze niż praca na całej macierzy, ponieważ w istocie obliczają one dekompozycje tylko dla rzutów macierzy na przypadkowe podprzestrzenie.

Czy to jest warte matrycy o rozmiarze może być dobrym pytaniem, ale jeśli twoje problemy naprawdę stają się duże, podejrzewam, że to się opłaca. $100\times 100$

— Wolfgang Bangerth
źródło

Z tego, co wiem o tych algorytmach, tworzą one matrycę niskiego rzędu, która jest dość zbliżona normalnie do danej matrycy. Muszę wiedzieć, czy istnieje (na przykład) macierz rangi 10 lub mniejszej, która jest bardzo zbliżona do danej macierzy (powiedzmy błąd względny 1,0e-10 lub lepszy.)

— Brian Borchers

Tak, ale możesz także wykonać rozkład QR rzutowanej (niskowymiarowej) macierzy, a jeśli rozkład ten ujawni brak pełnej rangi, wówczas będziesz mieć również oryginalną macierz z niedoborem rang. Czy nie było to kryterium, które wymagało przeprowadzenia rozkładu QR na oryginalnej matrycy?

— Wolfgang Bangerth,

Widzę, że ranga rzutowanej macierzy jest mniejsza lub równa (liczba wierszy w macierzy losowej mnożę razy A) i ranga A. Jeśli ma rangę , to pierwotna macierz nie może być o randze lub niższej. Jeśli ma rangę mniejszą niż to mógłbym mieć po prostu pecha lub miał rangę mniejszą niż . Znalezienie rangi macierzy na można wykonać w czasie . Jeśli jednak macierz losowa, którą mnożę razy jest gęsta, mnożenie przyjmuje

k

$k$

k

$k$

k - 1

$k-1$

k

$k$

A

$A$

k

$k$

k

$k$

n

$n$

O (k^{2} n)

$O(k^{2}n)$

A

$A$

O (k n^{2})

$O(kn^{2})$ czas. Czy istnieją rzadkie macierze, które zachowują rangę z dużym prawdopodobieństwem?

— Brian Borchers,

Nie wiem Zgadzam się (i mam sugerować), że algorytm może powiedzieć tylko, jeśli macierz nie ma pełnej rangi. Nie może powiedzieć, czy macierz ma pełną rangę, chyba że weźmiesz wszystkie losowe kierunki . Mam nadzieję, że po prostu dostaniesz odpowiedź na wystarczająco małe gdzie .

k = n

$k=n$

k

$k$

k n^{2} ≪ n^{3}

$kn^2\ll n^3$

— Wolfgang Bangerth,

1

Innym podejściem, które warto wypróbować, jest zastosowanie adaptacyjnej aproksymacji krzyżowej (ACA). Jest to dość popularny algorytm, który ma wiele implementacji dostępnych online. Dla porównania możesz zobaczyć oryginalny papier:

SA Goreinov, EE Tyrtyshnikov, NL Zamarashkin, „Teoria przybliżeń pseudoszkieletu”, Algebra liniowa Appl. , vol. 261, nr 1–3, s. 1–21, sierpnia 1997 r.

ACA i jego odmiany (powiedzmy, ACA +, hybrydowe przybliżenie krzyżowe HCA) mogą być stosowane w różnych scenariuszach. Ty, mając już obliczoną całą gęstą macierz, jesteś jedną z korzystniejszych, ponieważ będziesz w stanie obliczyć resztki dokładnie w razie potrzeby.

Jeśli resztki heurystyczne (patrz algorytm) są wystarczające, uważam, że twoją złożonością będzie , gdzie to rozmiar macierzy kwadratowej, a to ranga. Zauważ, że ranga jest funkcją przepisanej tolerancji obcięcia . Dokładne i gwarantowane granice błędów będą wymagały . $\mathcal O(Nr)$ $N$ $r(\epsilon)$ $r$ $\epsilon$ $\mathcal O(N^2r)$

— Anton Menshov
źródło

0

W prostym przypadku, w którym macierz jest symetryczna z dodatnią wartością, oblicz jej powiedzmy 20 największych wartości własnych i sprawdź, czy są , lub porównaj normy. ARPACK jest do tego szybki; co ważniejsze, potrzebuje tylko funkcji . Tak więc dla ogólnego spójrz na wartości własne (jako LinOp, bez jego tworzenia). $A$ $\to 0$ $x \to A \, x$ $A$ $A^T A$

scipy.sparse.linalg.svds robi to: LinOp Arpack, dla dowolnego rozmiaru: $( A^T A ) \to$ $A$

from scipy.sparse.linalg import svds
sing = svds( A, k=20, tol=1e-4, return_singular_vectors=False )  # v0=random
# runtimes on random-normal n x n:
# n = 100, 1k, 2k
#       5, 130, 770 ms

— denis
źródło