Wektory własne małej korekty normy

Mam zestaw danych, który powoli się zmienia i muszę śledzić wektory własne / wartości własne macierzy kowariancji.

Używałem scipy.linalg.eigh, ale jest zbyt drogi i nie korzysta z faktu, że mam już rozkład, który jest tylko nieznacznie niepoprawny.

Czy ktoś może zaproponować lepsze podejście do rozwiązania tego problemu?

— Jarosław Bułatow
źródło

Jak duże są twoje dane? Potrzebujesz kompletnego systemu eigens, czy tylko jednych z największych wartości własnych? Czy potrzebujesz ich dokładnie, czy może wystarczyłoby przybliżenie?

— por.

Potrzebuję kompletnego systemu eigens. Znalazłem algorytm aktualizowania odwrotności macierzy po małej aktualizacji normy za pomocą interpretacji regresji odwrotności macierzy kowariancji, więc założyłem, że coś podobnego powinno istnieć dla wektorów własnych.

— Yaroslav Bulatov

Co robisz z tym pełnym składem eigend? Może być lepszy skrót, który nie przechodzi przez to ... I powtarzam pytanie cfh: „jak duże”?

— Federico Poloni

Mam 8k funkcji i miliony punktów danych, więc kowariancja jest przybliżona. Ma to na celu wdrożenie tego algorytmu. Gradient zmiana zależy od wartości własnych pewnej macierzy kowariancji, a ta macierz kowariancji zmienia na każdym kroku

— Jarosław Bulatov

Odpowiedzi:

Naiwnym podejściem jest użycie rozwiązania wartości własnej macierzy jako początkowego przypuszczenia iteracyjnego eigensolver dla macierzy . Możesz użyć QR, jeśli potrzebujesz pełnego spektrum lub w inny sposób metody zasilania. Nie jest to jednak całkowicie niezawodne podejście, ponieważ wartości własne macierzy niekoniecznie są bliskie prawie sąsiedniej macierzy (1) , zwłaszcza jeśli jest ona słabo uwarunkowana (2) . $A(t)$ $A(t + \delta t)$

Metoda śledzenia podprzestrzeni jest najwyraźniej bardziej użyteczna (3) . Fragment (4) :

Obliczenia iteracyjne ekstremalnej (maksymalnej lub minimalnej) pary własnych (wartość własna i wektor własny) mogą pochodzić z 1966 r. [72]. W 1980 r. Thompson zaproponował algorytm adaptacyjny typu LMS do szacowania wektora własnego, który odpowiada najmniejszej wartości własnej macierzy kowariancji próbki, i dostarczył algorytm adaptacyjnego śledzenia algorytmu czesania kąt / częstotliwość za pomocą estymatora harmonicznego Pisarenko [14]. Sarkar i in. [73] zastosował algorytm sprzężonego gradientu do śledzenia wariancji ekstremalnego wektora własnego, który odpowiada najmniejszej wartości własnej macierzy kowariancji wolno zmieniającego się sygnału i udowodnił swoją znacznie większą zbieżność niż algorytm Thompsona typu LMS. Metody te zastosowano jedynie do śledzenia pojedynczej wartości ekstremalnej i wektora własnego o ograniczonym zastosowaniu, ale później zostały rozszerzone o metody śledzenia i aktualizacji podprzestrzeni własnej. W 1990 r. Comon i Golub [6] zaproponowali metodę Lanczosa do śledzenia ekstremalnej liczby pojedynczej i wektora osobliwego, która jest powszechną metodą opracowaną pierwotnie w celu określenia dużego i rzadkiego symetrycznego problemu własnego $Ax = kx$ [74].

[6]: Comon, P., i Golub, GH (1990). Śledzenie kilku ekstremalnych pojedynczych wartości i wektorów w przetwarzaniu sygnału. W przetwarzaniu IEEE (str. 1327–1343).

[14]: Thompson, PA (1980). Adaptacyjna technika analizy widmowej dla częstotliwości obiektywnej

[72]: Bradbury, WW i Fletcher, R. (1966). Nowe metody iteracyjne dla rozwiązania problemu własnego. Matematyka numeryczna, 9 (9), 259–266.

[73]: Sarkar, TK, Dianat, SA, Chen, H. i Brule, JD (1986). Adaptacyjne oszacowanie spektralne metodą gradientu sprzężonego. Transakcje IEEE dotyczące przetwarzania akustycznego, mowy i sygnałów, 34 (2), 272–284.

[74]: Golub, GH i Van Load, CF (1989). Obliczenia macierzowe (wydanie 2). Baltimore: The John Hopkins University Press.

Powinienem również wspomnieć, że rozwiązania macierzy symetrycznych, takie jak to, co musisz rozwiązać, biorąc pod uwagę użycie scipy.linalg.eigh, są nieco tanie. Jeśli interesuje Cię tylko kilka wartości własnych, możesz również znaleźć poprawę prędkości w swojej metodzie. W takich sytuacjach często stosuje się metodę Arnoldiego.

— Spencer Bryngelson
źródło

dzięki za wskaźnik, algorytm QR wydaje się dobrym punktem wyjścia

— Jarosław Bułatow

Nie sądzę, aby wielkość zaburzeń w wartościach własnych była związana z liczbą warunków. Jest tak, ponieważ ma takie same wartości własne jak , ale inny numer warunku.

A

$A$

A + λ I

$A+\lambda I$

— Federico Poloni

ps: linalg.eigh na matrycy 4k na 4k zajmuje około 20 sekund (z jakiegoś powodu używa tylko jednego rdzenia). Potrzebuję około 0,25 sekundy na aktualizację

— Jarosław Bułatow

Istnieją specjalne techniki aktualizowania rozkładu własnego zależnych od czasu macierzy kowariancji. Biorąc pod uwagę „wcześniejszy” rozkład wartości własnych (powiedzmy w pewnym momencie początkowym ), te rekurencyjne algorytmy obniżają złożoność aktualizacji widma z (zasadniczo koszt nowego składu eigend) do gdzie jest rozmiarem twojej matrycy, a jest stopniem twojej aktualizacji. $t^0$ $\mathcal{O}(N^3)$ $\mathcal{O}(k N^2)$ $N$ $k$

Oto kilka istotnych odniesień:

Adaptacyjne składowe składowe macierzy kowariancji danych na podstawie perturbacji pierwszego rzędu (szampan, IEEE TSP 42 (10) 1994)

Rekurencyjne aktualizowanie rozkładu wartości własnej macierzy kowariancji (Yu, IEEE TSP, 39 (5) 1991)

Analiza głównych składników online w dużym wymiarze: jaki algorytm wybrać? (Cardot i Degras)

Stabilny i szybki algorytm aktualizujący rozkład wartości osobliwych (Gu i Eisenstadt, 1994)

— GoHokies
źródło

niestety nie mam małych aktualizacji rang, mam małe aktualizacje norm rangi

— Jarosław Bułatow

@YaroslavBulatov Nie znam wydajnego algorytmu, który poradziłby sobie z aktualizacjami pełnej rangi według małych norm - najlepsze, co mogłem znaleźć, to odniesienie , ale nie wygląda bardzo obiecująco. Istnieje oczywiście obszerna literatura na temat perturbacji wartości własnych, na którą warto spojrzeć (patrz druga odpowiedź).

— GoHokies