Przybliżone spektrum dużej matrycy

14

Chcę obliczyć widmo ( wszystkie wartości własne) dużej rzadkiej macierzy (setki tysięcy wierszy). To jest trudne.

Jestem gotów zadowolić się przybliżeniem. Czy istnieją do tego metody przybliżenia?

Chociaż mam nadzieję na ogólną odpowiedź na to pytanie, byłbym również zadowolony z odpowiedzi w następującym konkretnym przypadku. Moja matryca jest znormalizowanym Laplacianem dużego wykresu. Wartości własne wynoszą od 0 do 2, a duża ich liczba skupiona jest wokół 1.

MRocklin
źródło
Czy matryca jest rzadka czy gęsta?
Aron Ahmadia,
Matryca jest rzadka. Zredagowałem pytanie, aby to odzwierciedlić.
MRocklin
Dlaczego chcesz wszystkich wartości własnych? Jest to prawie zła rzecz do zrobienia, gdy masz rzadką lub ustrukturyzowaną matrycę, dlatego ważne jest, aby wiedzieć, jak planujesz jej używać.
Jed Brown
Spektrum wykresu Laplaciana zawiera pewne ważne informacje, które chciałbym sprawdzić. Nie potrzebuję ich wszystkich, muszę tylko z grubsza wiedzieć, gdzie oni są.
MRocklin

Odpowiedzi:

15

Jeśli twój wykres nie jest przekierowany (jak podejrzewam), macierz jest symetryczna i nie możesz zrobić nic lepszego niż algorytm Lanczsosa (z selektywną reortogonalizacją, jeśli to konieczne dla stabilności). Ponieważ pełne spektrum składa się ze 100 000 liczb, domyślam się, że interesuje Cię głównie gęstość widmowa.

Aby uzyskać przybliżoną gęstość widmową, weź widmo wiodącej podprzestrzeni Kryłowa o wymiarze około 100 i zamień jej dyskretną gęstość na wygładzoną wersję.

Wiodące spektrum Kryłowa prawie rozwiąże dobrze izolowane wartości własne (jeśli takie istnieją), aproksymuje wartości własne na końcu widma nieizolowanego i jest nieco losowe pomiędzy, z rozkładem, którego skumulowana funkcja rozkładu przypomina rozkład rzeczywistego widma . Jeśli wymiar rośnie, zbiega się w nim z dokładną arytmetyką. (Gdyby twój operator był nieskończenie wymiarowy, nadal tak by było, a całkę prawdziwej funkcji gęstości widmowej uzyskałbyś na widmie ciągłym.)

Arnold Neumaier
źródło
Czy spektrum wiodącej podprzestrzeni Kryłowa nie będzie po prostu 100 największymi wartościami własnymi? Interesuje mnie również rozkład umiarkowanych i najmniejszych wartości własnych.
MRocklin
1
@MRocklin: Nie. Ulepszyłem swoją odpowiedź, aby podać więcej szczegółów.
Arnold Neumaier
4

Jeśli nie masz nic przeciwko myśleniu o rzeczach, które nie są wartościami własnymi, ale funkcjami, które w pewnym sensie wciąż mówią ci coś o spektrum, to myślę, że powinieneś sprawdzić niektóre prace Mark Embree z Rice University.

Wolfgang Bangerth
źródło
2

Oto jeszcze jeden sposób na scharakteryzowanie widma.

ZAvk=λkvkZA

S.(ω)=kπ-1σσ2)+(λk-ω)2)=σπT.r[σ2)+(ω-ZA)2)]-1
S.(ω)=σπzT.[σ2)+(ω-ZA)2)]-1z
z+1-1σω[σ2)+(ω-ZA)2)]-1z[ω+jaσ-ZA]-1[ω-jaσ-ZA]-1aby zminimalizować wypełnianie. Umożliwia to oszacowanieS.(ω)także dla dużych matryc. W praktyce wydaje się, że rozwiązanie CG nie musi być bardzo dokładne i nie ma też wielu wektorów potrzebnych do obliczenia średniej. Może to zależeć od problemu.

Powyższe wydaje się ważyć części widma bardziej równomiernie niż podobnie rozmazana gęstość widmowa Kryłowa --- spróbuj diag (linspace (0, 1, 150000)) --- chociaż może istnieje sposób, aby to naprawić? Jest to nieco podobne do podejścia pseudospektralnego, ale wynik wskazuje (rozmazaną) liczbę wartości własnych w pobliżu punktuω, a nie odwrotna odległość do najbliższej wartości własnej.

EDYCJA : Bardziej wydajną alternatywą dla obliczania powyższej ilości jest obliczenie momentów Czebyszewa (poprzez podobną ocenę stochastyczną jak powyżej), a następnie odtworzenie z nich gęstości widmowej. Nie wymaga to odwracania macierzy ani osobnych obliczeń dla każdego z nichω. Zobacz http://theorie2.physik.uni-greifswald.de/downloads/publications/LNP_chapter19.pdf i odnośniki do nich.

pv.
źródło
0

Zobacz artykuł „O przybliżonym rozkładzie spektralnym opartym na próbkowaniu” Sanjiva Kumara, Mehryara Mohri i Ameeta Talwalkara (ICML 2009.). Wykorzystuje próbkowanie kolumn macierzy.

Ponieważ macierz jest symetryczna, wykonaj następujące czynności:

Niech A będzie Twoją n * n macierzą. Chcesz zredukować obliczanie wartości własnych macierzy n * n do obliczeń wartości własnych macierzy k * k. Najpierw wybierz swoją wartość k. Załóżmy, że wybierasz k = 500, ponieważ możesz łatwo obliczyć wartości własne macierzy 500 * 500. Następnie losowo wybierz k kolumn macierzy A. Skomponuj macierz B, która przechowuje tylko te kolumny i odpowiadające im wiersze.

B = A (x, x) dla losowego zestawu k indeksów x

B jest teraz macierzą ak * k. Oblicz wartości własne B i pomnóż je przez (n / k). Masz teraz wartości k, które są w przybliżeniu rozłożone, podobnie jak n wartości własne A. Zauważ, że otrzymujesz tylko wartości k, a nie n, ale ich rozkład będzie poprawny (do tego stopnia, że ​​są przybliżeniem).

Jérôme Kunegis
źródło
-1

Zawsze możesz użyć granic Twierdzenia Gershgorina do przybliżenia wartości własnych.

Jeśli warunki poza przekątną są małe, sama przekątna jest dobrym przybliżeniem widma. W przeciwnym razie, jeśli skończysz z przybliżeniem przestrzeni własnej (innymi metodami), możesz spróbować wyrazić przekątne wpisy w tym systemie. Doprowadzi to do powstania matrycy o mniejszych wartościach poza przekątną, a nowa przekątna będzie lepszym przybliżeniem widma.

FKaria
źródło
Gerschgoring nie podaje żadnych przybliżeń, ale granice błędów, więc nie ma tu znaczenia. Co więcej, użycie metody na rzadkiej macierzy wymagałoby gęstej macierzy wektorów własnych, której nie można zapisać dla problemu OP.
Arnold Neumaier
Jak już powiedziałem, przekątna sama w sobie jest przybliżeniem widma z granicami błędu podanymi przez twierdzenie o okręgu Gershgorina, oczywiście granice błędu Gershgorina nie są przybliżeniami. Przekątna będzie dobrym przybliżeniem, jeśli pojęcia poza przekątną są małe, co moim zdaniem ma miejsce, ponieważ OP powiedział, że macierz jest rzadka.
FKaria
5
Większość macierzy rzadkich powstających w praktyce ma pewne znaczące elementy nie przekątne w każdym rzędzie i kolumnie, co sprawia, że ​​przekątna jest bardzo słabym przybliżeniem (np. Dla Laplaciana regularnego wykresu przekątna jest stała), a błąd graniczy bezużyteczny.
Arnold Neumaier