Iteracyjny „solver” dla

Nie mogę sobie wyobrazić, że pierwszy pomyślę o następującym problemie, więc będę zadowolony z referencji (ale zawsze doceniamy pełną, szczegółową odpowiedź):

Załóżmy, że masz symetryczny dodatni określony . jest uważane za bardzo duże, więc trzymanie w pamięci jest niemożliwe. Możesz jednak ocenić dla dowolnego . Biorąc pod uwagę trochę , chciałbyś znaleźć . $\Sigma \in \mathbb{R}^{n \times n}$ $n$ $\Sigma$ $\Sigma x$ $x \in \mathbb{R}^{n}$ $x \in \mathbb{R}^{n}$ $x^t\Sigma^{-1}x$

Pierwszym rozwiązaniem, które przychodzi na myśl, jest znalezienie przy użyciu (powiedzmy) gradientów sprzężonych. Wydaje się to jednak trochę marnotrawstwem - szukasz skalara, a podczas procesu znajdujesz gigantyczny wektor w . Wydaje się sensowniejsze wymyślić metodę bezpośredniego obliczania skalara (tj. Bez przechodzenia przez ). Szukam tego rodzaju metody. $\Sigma^{-1}x$ $\mathbb{R}^{n}$ $\Sigma^{-1}x$

linear-algebra numerical-analysis iterative-method

— Yair Daon
źródło

Czy macierz powstaje z dla jakiegoś prostokąta „krótkiego i szerokiego” ?

Σ = A^{T} A

$\Sigma = A^TA$

A

$A$

— GeoMatt22,

@ GeoMatt22 niestety nie. Ale powiedzmy, że tak - co byś zaproponował w takim przypadku?

— Yair Daon,

Yair, właśnie myślałem, czy jest jakaś mniejsza matryca do pracy ... nie jestem pewien, czy to by pomogło. Czy próbowałeś googlingu „matryca wolna odległość mahalanobis” lub podobny? Przepraszam, że nie pomogłem!

— GeoMatt22,

Dzięki @ GeoMatt22, nie mogłem znaleźć niczego online.

— Yair Daon,

Nie sądzę, że słyszałem o żadnej metodzie, która robi to, co chcesz bez rozwiązania . $y=\Sigma^{-1}x$

Jedyną alternatywą, jaką mogę zaoferować, jest wiedza o wektorach własnych i wartościach . Załóżmy, że wiesz, że są to , a następnie możesz reprezentować gdzie kolumny to , a to macierz diagonalna z wartościami własnymi na przekątnej. W rezultacie masz i otrzymujesz To oczywiście wymaga, aby zapisać wszystkie wartości własne, czyli pełnej macierzy . Ale jeśli zdarzyło Ci się wiedzieć, że tylko kilka wartości własnych $\Sigma$ $\lambda_i,v_i$ $\Sigma=V^T L V$ $V$ $v_i$ $L$ $\Sigma^{-1}=V^T L^{-1} V$

x^{T} Σ^{- 1} x = x^{T} V^{T} L^{- 1} V x = \sum_{i} λ_{i}^{- 1} (v_{i}^{T} x)^{2} .

$x^T \Sigma^{-1} x = x^T V^T L^{-1} V x = \sum_i \lambda_i^{-1} (v_i^T x)^2.$

V

$V$

Σ

$\Sigma$ są małe, powiedzmy pierwsze , a reszta jest tak duża, że możesz pominąć wszystkie wyrażenia za pomocą dla , a następnie możesz przybliżać To wymaga tylko przechowywania wektorów zamiast wszystkich wektorów własnych.

m

$m$

λ_{i}^{- 1}

$\lambda^{-1}_i$

i > m

$i>m$

x^{T} Σ^{- 1} x = \sum_{i = 1}^{n} λ_{i}^{- 1} (v_{i}^{T} x)^{2} \approx \sum_{i = 1}^{m} λ_{i}^{- 1} (v_{i}^{T} x)^{2} .

$x^T \Sigma^{-1} x = \sum_{i=1}^n \lambda_i^{-1} (v_i^T x)^2 \approx \sum_{i=1}^m \lambda_i^{-1} (v_i^T x)^2.$

m

$m$

n

$n$

Oczywiście w praktyce obliczanie wartości własnych i wektorów własnych jest często równie lub trudniejsze, niż proste rozwiązywanie wiele razy. $y=\Sigma^{-1}x$

— Wolfgang Bangerth
źródło

Ale wtedy jesteś w lewo z zadaniem znalezienia Najmniejsze wartości własnych macierzy, co nie jest łatwym zadaniem ...

m

$m$

— Yair Daon

Poprawny. Ale może być tego warte, jeśli musisz wielokrotnie oceniać .

x^{T} Σ^{- 1} x

$x^T\Sigma^{-1}x$

— Wolfgang Bangerth

Czy możesz więc zaproponować metodę?

— Yair Daon

Wokół jest wiele lub rzadkie solwery wartości własnych. ARPACK i SLEPc oparte na PETSc są prawdopodobnie najczęściej stosowanymi.

— Wolfgang Bangerth

Bangreth Dziękuję za referencje. Sprawdziłem SLEPc (choć niezbyt dokładnie) i wygląda na to, że sposób znajdowania par własnych jest przez (być może zmodyfikowaną) iterację Lanczosa. Jeśli ktoś ma najmniejsze eigenpairs, trzeba znaleźć i przechowywać wszystkie eigenpairs w pamięci. Zazwyczaj nie jest to możliwe w przypadku problemów z macierzą - zajmuje tyle pamięci, ile jest zapisywania macierzy . Jeśli ktoś chce zastosować odwrotną iterację - nie udziela się gwarancji na kolejność znalezionych par własnych. Czy coś brakuje?

m

$m$

n \times n

$n \times n$

— Yair Daon,