Obliczanie współczynnika Cholesky'ego

11

Twierdzenie o rozkładzie Cholesky'ego stwierdza zatem, że każda prawdziwa symetryczna macierz dodatnio określona ma rozkład Choleskiego gdzie jest dolną macierzą trójkątną. $M$ $M= LL^\top$ $L$

Biorąc pod uwagę , wiemy już, że istnieją szybkie algorytmy do obliczania jego współczynnika Cholesky'ego . $M$ $L$

Załóżmy teraz, że otrzymałem prostokątną macierz , i wiedziałem, że jest pozytywnie określona. Czy istnieje sposób, aby obliczyć współczynnik Choleskiego z bez obliczania jawnie, a następnie zastosowanie algorytmów faktoryzacji Cholesky? $m\times n$ $A$ $A^\top A$ $L$ $A^\top A$ $A^\top A$

Jeśli jest bardzo dużą prostokątną matrycą wykonującą jawnie wydaje się bardzo droga i stąd pytanie. $A$ $A^\top A$

linear-algebra algorithms smilingbuddha
źródło

Więcej niż koszt tworzące matrycę przekrój produktów, podejście to także placów numer stan swojego . Jeśli twój jest prawie pozbawiony rangi, to z pewnością jest to kiepski sposób postępowania.

A

$\mathbf A$

A

$\mathbf A$

JM

To pytanie i to pytanie zadaje to samo na różne sposoby. Odpowiedzi w tych wątkach (i odpowiedzi poniżej) powinny ci się przydać.

Damien

8

Tak, można uzyskać współczynnik (do znaków wpisów) za pomocą rozkładu QR; zobacz tę odpowiedź . Zauważ, że jeśli wszystkim, co cię interesuje, jest rozwiązanie problemu najmniejszych kwadratów, który prowadzi do normalnych równań obejmujących , możesz bezpośrednio użyć rozkładu QR. $A^T A$

Christian Clason
źródło

7

Tak. Oblicz faktoryzację i weź ; przeskaluj rzędy jeśli to konieczne (zmieniając niektóre z ich znaków), aby znak przekątnej był nieujemny (ponieważ czynnik Choleskiego jest zdefiniowany jako mający nieujemną przekątną). $QR$ $L=R^T$ $R$

Aby poznać rzadkie faktoryzacje QR, patrz np. Http://dl.acm.org/citation.cfm?id=174408

Arnold Neumaier
źródło

Obliczanie współczynnika Cholesky'ego

Odpowiedzi: