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?
linear-algebra
optimization
python
eigenvalues
Jarosław Bułatow
źródło
źródło
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+δt)
Metoda śledzenia podprzestrzeni jest najwyraźniej bardziej użyteczna (3) . Fragment (4) :
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.źródło
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.O ( N 3 ) O ( k N 2 ) N kt0 O(N3) O(kN2) 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)
źródło