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ć?

linear-algebra matrix

— Benjamin Allévius
źródło

14

Faktoryzacja Choleskiego prowadzi do podobnej do Choleskiego faktoryzacji odwrotnej z górną trójkątną macierzą . $C=R^TR$ $C^{-1}=SS^T$ $S=R^{-1}$

W praktyce najlepiej odwrócić faktorowanie. Jeśli $R$ jest rzadki, zwykle lepiej jest zachować domniemanie $S$ , ponieważ produkty macierz-wektor $y=C^{-1}x$ można obliczyć, rozwiązując dwa układy trójkątne $R^Tz=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 = A^{T} A

$C = A^{T} A$

$A$ $C$ $A$ $A^{T}A$

A = Q R

$A = QR$

Ponieważ Q jest ortogonalny,

\begin{aligned} C & = (Q R)^{T} Q R \\ = R^{T} Q^{T} Q R \\ = R^{T} I R \\ = R^{T} R \end{aligned}

$\begin{align} C &= (QR)^{T} QR \\ &= R^T Q^T QR \\ &= R^T I R \\ &= R^{T} R \end{align}$

$R^{T}$ $Q$ $Q$ $Q$ $Q$ $Q$

$A^{T}A$

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

C^{- 1}

$C^{-1}$

⟨ x, C^{- 1} x ⟩ = ⟨ x, (R^{T} R)^{- 1} x ⟩ = ‖ R^{- T} x ‖^{2}

$\langle x,C^{-1}x\rangle = \langle x,(R^T R)^{-1}x\rangle = \|R^{-T}x\|^2$

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 = A A^\top$ $M$ $L$ $M = L L^\top$ $L$ $L^{-1}$ $M^{-1} = \left(L L^\top\right)^{-1} = L^{-\top}L^{-1}$

Zacząć od:

$M = A A^\top$ , gdzie jest znane i jest domyślnie symetryczne, a także dodatnio określone. $M$

Rozkład na czynniki chłodnicze:

$M \rightarrow L L^\top$ , gdzie jest kwadratowe i nieparzyste $L$

Podstawienie wsteczne:

$L \rightarrow L^{-1}$ , prawdopodobnie najszybszy sposób na odwrócenie (choć nie cytuję tego) $L$

Mnożenie:

$M^{-1} = \left(L L^\top\right)^{-1} = L^{-\top} L^{-1}$

Zastosowana notacja: dolne indeksy to wiersze, górne indeksy to kolumny, a to transpozycja $L^{-\top}$ $L^{-1}$

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

$L_i^j = \frac{M_i^j - M_i \cdot M_j}{M_i^i - M_i \cdot M_i}$

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)

$\left(L^{-1}\right)_i^j = \left\{\begin{array}{11} 1 / {L_i^i} & \mbox{if } i = j\\ \left(-L_i \cdot \left(L^{-T}\right)_j\right) / L_i^i & \mbox{otherwise} \end{array}\right.$

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 ... $L^{-T}$

— 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