Szybkie obliczanie / szacowanie niskiego rzędu systemu liniowego

10

Liniowe układy równań są wszechobecne w statystyce obliczeniowej. Jednym specjalnym systemem, z którym się zetknąłem (np. W analizie czynnikowej) jest system

Ax=b

gdzie Tutaj D jest macierzą diagonalną n × n ze ściśle dodatnią przekątną, Ω jest m × m (z m n ) symetryczną dodatnią półokreśloną macierzą, a B jest arbitralną n × macierz m . Jesteśmy proszeni o rozwiązanie ukośnego układu liniowego (łatwego), który został zakłócony przez matrycę niskiej rangi. Naiwnym sposobem rozwiązania powyższego problemu jest odwrócenie A za pomocą wzoru Woodbury'ego

A=D+BΩBT
Dn×nΩm×mmnBn×mA. Nie wydaje się to jednak właściwe, ponieważ faktoryzacje Cholesky'ego i QR zwykle mogą znacznie przyspieszyć rozwiązanie układów liniowych (i równań normalnych). Niedawno wpadłem na następujący artykuł , który wydaje się przyjmować podejście Choleskiego, i wspomina o niestabilności numerycznej inwersji Woodbury'ego. Artykuł wydaje się jednak w formie szkicu i nie mogłem znaleźć eksperymentów numerycznych ani badań wspierających. Jaki jest stan techniki w rozwiązaniu opisanego przeze mnie problemu?
niezadowolony
źródło
1
Ω1+BD1BTΩ1m<<nA
ϵ
B¯=D1/2B(I+B¯ΩB¯T)x=b¯b¯=D1/2bΣ=B¯ΩB¯TΣmmnmx=Q(I+Λ)1QTb¯Σ=QΛQTΣ
(I+B¯ΩB¯T)D1/2x=b¯x=D1/2Q(I+Λ)1QTD1/2bD1/2xw obu przypadkach.) Zauważ, że wszystkie odwrotności mają matryce diagonalne, a zatem są trywialne.
kardynał
Ω1+BTD1B

Odpowiedzi:

2

„Obliczenia macierzy” Goluba i van Loana szczegółowo omówiono w rozdziale 12.5.1 na temat aktualizacji faktoryzacji QR i Cholesky'ego po aktualizacjach rangi p.

Fabian Pedregosa
źródło
Wiem, a odpowiednie funkcje lapack są wymienione zarówno w dokumencie, do którego linkowałem, jak i w książce. Zastanawiam się jednak, jaka jest najlepsza praktyka dla danego problemu, a nie dla ogólnego problemu aktualizacji.
gappy