Radzenie sobie z odwrotnością dodatniej określonej macierzy symetrycznej (kowariancji)?

27

W statystyce i jej różnych zastosowaniach często obliczamy macierz kowariancji , która jest pozytywnie określona (w rozważanych przypadkach) i symetryczna, dla różnych zastosowań. Czasami potrzebujemy odwrotności tej macierzy do różnych obliczeń (na przykład formy kwadratowe z odwrotnością jako (jedyną) macierzą środkową). Biorąc pod uwagę cechy tej matrycy i zamierzone zastosowania, zastanawiam się:

Jaka jest najlepsza, pod względem stabilności numerycznej, metoda obliczania lub stosowania (powiedzmy w przypadku form kwadratowych lub ogólnie mnożenia macierzy-wektora) tej odwrotności? Jakaś faktoryzacja, która może się przydać?

Benjamin Allévius
źródło

Odpowiedzi:

14

Faktoryzacja Choleskiego prowadzi do podobnej do Choleskiego faktoryzacji odwrotnej C - 1 = S S T z górną trójkątną macierzą S = R - 1 .C=RTRC1=SSTS=R1

W praktyce najlepiej odwrócić faktorowanie. Jeśli R jest rzadki, zwykle lepiej jest zachować domniemanie S , ponieważ produkty macierz-wektor y=C1x można obliczyć, rozwiązując dwa układy trójkątne RTz=x i Ry=z .

Arnold Neumaier
źródło
25

Faktoryzacja Cholesky'ego ma największy sens dla najlepszej stabilności i prędkości podczas pracy z macierzą kowariancji, ponieważ macierz kowariancji będzie dodatnią półokreśloną macierzą symetryczną. Cholesky jest tu naturalny. ALE...

JEŚLI zamierzasz obliczyć rozkład na czynniki choleskie, zanim jeszcze obliczysz macierz kowariancji, zrób sobie przysługę. Spraw, aby problem był maksymalnie stabilny, obliczając faktoryzację QR macierzy. (QR też jest szybki.) To znaczy, gdybyś obliczył macierz kowariancji jako

C=ATA

ACAATA

A=QR

Ponieważ Q jest ortogonalny,

C=(QR)TQR=RTQTQR=RTIR=RTR

RTQQQQQ

ATA

Wreszcie, jak wskazuje kolejna odpowiedź, nie musisz nawet obliczać i przechowywać odwrotności, ale używaj jej pośrednio w postaci odwrotnych rozwiązań w układach trójkątnych.

pentavalentcarbon
źródło
5
C1x,C1x=x,(RTR)1x=RTx2
3

Zrobiłem to po raz pierwszy niedawno, korzystając z sugestii z matematyki.

Myślę, że SVD było zalecane przez większość, ale zdecydowałem się na prostotę Cholesky:

Jeśli macierz , to rozkładam na trójkątną macierz za pomocą Cholesky'ego, tak że . Następnie używam podstawienia w tył lub w przód (w zależności od tego, czy wybiorę L, aby był trójkątem górnym czy dolnym), aby odwrócić , tak że mam . Na tej podstawie mogę szybko obliczyć . M L M =M=AAMLM=LLLL1M1=(LL)1=LL1


Zacząć od:

M=AA , gdzie jest znane i jest domyślnie symetryczne, a także dodatnio określone.M

Rozkład na czynniki chłodnicze:

MLL , gdzie jest kwadratowe i nieparzysteL

Podstawienie wsteczne:

LL1 , prawdopodobnie najszybszy sposób na odwrócenie (choć nie cytuję tego)L

Mnożenie:

M1=(LL)1=LL1

Zastosowana notacja: dolne indeksy to wiersze, górne indeksy to kolumny, a to transpozycjaLL1


Mój algorytm Cholesky'ego (prawdopodobnie z przepisów numerycznych lub Wikipedii)

Lij=MijMiMjMiiMiMi

Można to prawie zrobić na miejscu (potrzebujesz tylko tymczasowego przechowywania elementów ukośnych, akumulatora i niektórych iteratorów liczb całkowitych).


Mój algorytm zastępowania wstecznego (z Numerycznych przepisów sprawdź ich wersję, ponieważ mogłem pomylić się ze znacznikiem LaTeX)

(L1)ij={1/Liiif i=j(Li(LT)j)/Liiotherwise

Ponieważ w wyrażeniu pojawia się , kolejność iteracji po macierzy jest ważna (niektóre części macierzy wynikowej zależą od innych jej części, które należy wcześniej obliczyć). Sprawdź kod Przepisy numeryczne, aby znaleźć pełny przykład w kodzie. [Edytuj]: W rzeczywistości po prostu sprawdź przykład Przepisy numeryczne. Za bardzo uprościłem, używając produktów kropkowych, do tego stopnia, że ​​powyższe równanie ma cykliczną zależność bez względu na to, w jakiej kolejności iterujesz ...LT

Mark K Cowan
źródło
2

Jeśli wiesz, że macierz ma odwrotność (tj. Jeśli rzeczywiście jest dodatnia) i jeśli nie jest zbyt duża, to rozkład Choleskiego daje odpowiednie środki do scharakteryzowania odwrotności macierzy.

Wolfgang Bangerth
źródło