Przybliżone spektrum dużej matrycy

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.

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.)

Odpowiedź Arnolda Neumaiera została omówiona bardziej szczegółowo w sekcji 3.2 artykułu „Approximating Spectral Densities of Large Matrices” Lin Lin, Yousef Saad i Chao Yang (2016) .

Omówiono także niektóre inne metody, ale analiza numeryczna na końcu artykułu pokazuje, że metoda Lanczosa przewyższa te alternatywy.

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.

Oto jeszcze jeden sposób na scharakteryzowanie widma.

$\mathbf{A} v_k = \lambda_k v_k$$\mathbf{A}$

$$S(\omega) = \sum_k \frac{\pi^{-1}\sigma}{\sigma^2 + (\lambda_k - \omega)^2} = \frac{\sigma}{\pi} \mathop{\mathrm{Tr}} [\sigma^2 + (\omega - \mathbf{A})^2]^{-1}$$ $$S(\omega) = \frac{\sigma}{\pi}\langle z^T [\sigma^2 + (\omega - \mathbf{A})^2]^{-1} z \rangle$$ $z$$+1$$-1$$\sigma$$\omega$$[\sigma^2 + (\omega - \mathbf{A})^2]^{-1} z$$[\omega + i \sigma - \mathbf{A}]^{-1} [\omega - i \sigma - \mathbf{A}]^{-1}$aby zminimalizować wypełnianie. Umożliwia to oszacowanie$S(\omega)$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$\omega$, 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$\omega$. Zobacz http://theorie2.physik.uni-greifswald.de/downloads/publications/LNP_chapter19.pdf i odnośniki do nich.

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).

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.