Iteracyjny „solver” dla

9

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źć .ΣRn×nnΣΣxxRnxRnxtΣ1x

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.Σ1xRnΣ1x

Yair Daon
źródło
2
Czy macierz powstaje z dla jakiegoś prostokąta „krótkiego i szerokiego” ? Σ=ATAA
GeoMatt22,
@ GeoMatt22 niestety nie. Ale powiedzmy, że tak - co byś zaproponował w takim przypadku?
Yair Daon,
1
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,

Odpowiedzi:

2

Nie sądzę, że słyszałem o żadnej metodzie, która robi to, co chcesz bez rozwiązania .y=Σ1x

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Σλi,viΣ=VTLVVviLΣ1=VTL1V

xTΣ1x=xTVTL1Vx=iλi1(viTx)2.
VΣ 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λi1i>m
xTΣ1x=i=1nλi1(viTx)2i=1mλi1(viTx)2.
mn

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=Σ1x

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
Yair Daon
Poprawny. Ale może być tego warte, jeśli musisz wielokrotnie oceniać . xTΣ1x
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? mn×n
Yair Daon,