Frage:
Computing $(X^TX)^{-1}X^Ty$ in OLS
NPE
2011-04-14 10:58:16 UTC
view on stackexchange narkive permalink

Sei $ A \ in \ mathbb {R} ^ {n \ times n} $ eine dichte symmetrische positiv-definitive Matrix (das $ X ^ TX $ von hier) und $ b $ ein Vektor in $ \ mathbb {R} ^ n $.

Ich muss $ A ^ {- 1} b $ berechnen.

Zwei Fragen:

  1. Könnten Sie einen effizienten und numerisch stabilen Algorithmus zur Berechnung von $ A ^ {- 1} b $ für $ n \ ca. 1000 $ empfehlen?

  2. Let $ \ tilde {A_i} $ bezeichnet die aus $ A $ erhaltene Matrix, indem die $ i $ -te Zeile und die $ i $ -te Spalte entfernt werden. Gibt es einen Algorithmus, mit dem ich, nachdem ich $ A $ auf irgendeine Weise vorverarbeiten durfte, $ \ tilde {A_i} ^ {- 1} \ tilde b $ für jedes $ i \ in \ {1 schnell berechnen kann? , 2, \ ldots, n \} $ und alle $ \ tilde b \ in \ mathbb {R} ^ {n-1} $?

  3. ol>
Drei antworten:
#1
+6
mpiktas
2011-04-14 15:57:10 UTC
view on stackexchange narkive permalink

Um die Antwort von @ onestop zu ergänzen, besteht eine weitere effiziente Möglichkeit darin, die QR-Zerlegung zu verwenden. Der zusätzliche Vorteil besteht darin, dass die QR-Zerlegung direkt auf $ X $ und nicht auf $ X ^ TX $ angewendet werden kann.

Ich denke, die QR-Zerlegung kann für Ihre zweite Frage verwendet werden. Sie ist definitiv unkompliziert für das Entfernen von Spalten.

Die Frage ist jedoch, warum Sie sie benötigen. Es gibt leicht verfügbare Bibliotheken, die diese Operationen sehr effizient ausführen. Möchten Sie sie erneut implementieren? Soweit ich weiß, gibt es eine Menge nicht trivialer Feinabstimmungen von Code, selbst wenn der Algorithmus im Grunde genommen der beste für den Job ist. Daher sind die Chancen ziemlich hoch, dass Sie möglicherweise nicht den vollen Nutzen aus der Implementierung eines Algorithmus ziehen, der angeblich theoretisch überlegen ist

Hier ist der Link zu dem Kapitel in einem Buch, in dem Änderungen erläutert werden, die zur Lösung der zweiten Frage im Falle einer QR-Zerlegung erforderlich sind. Obwohl es besagt, dass die Methoden für Probleme der kleinsten Quadrate gelten, können sie für das System linearer Gleichungen angewendet werden.

Ich bin mir ziemlich sicher, dass dies ein Standardproblem sein sollte. Vielleicht gibt jemand eine passendere Referenz.

@mpiktas: Danke dafür. Nur zur Klarstellung, ich habe kein $ X $. Ich habe nur $ X ^ TX $ - siehe http://stats.stackexchange.com/questions/9341/regularized-fit-from-summarized-data
@aix, QR-Zerlegung kann weiterhin angewendet werden, obwohl Cholesky möglicherweise besser geeignet ist.
@mpiktas: Um Ihren zweiten Punkt anzusprechen, sage ich nicht, dass ich meine eigene SVD / QR / Cholesky / was auch immer codieren werde (es sei denn, ich muss es wirklich tun).
@aix, Ich weiß, dass du nicht sagst, deshalb habe ich gefragt :)
@aix, Ich habe die Antwort mit dem Link zum Buch aktualisiert, was Sie vielleicht interessant finden. Da Ihr Problem ziemlich spezifisch ist, vermute ich, dass Sie früher oder später gezwungen sein werden, ein Buch über numerische Methoden für Probleme mit kleinsten Quadraten zu lesen. Warum also nicht früher anfangen :)
@mpiktas: Sie würden es nicht glauben, aber ich habe heute Morgen genau dieses Buch bestellt!
@aix, "große Köpfe denken gleich" :) Ich weiß nicht, wo ich das gehört oder gelesen habe (der Kontext war humorvoll), aber ich denke, es gilt hier: D.
Neben Björck ist das (klassische) Buch [Lawson / Hanson] (http://books.google.com/books?id=ROw4hU85nz8C&pg=PA174) die andere gute Referenz für die Lösung von Problemen mit kleinsten Quadraten.
@J. M., danke! Dies war das erste Buch, das ich zu diesem Thema gelesen habe, aber ich habe die Autoren und den genauen Titel vergessen. Sehr gutes Buch. Es hat auch Fortran-Codebeispiele, was auch für mich sehr nützlich war.
#2
+5
onestop
2011-04-14 15:32:32 UTC
view on stackexchange narkive permalink

Die Standardantwort auf Ihre erste Frage lautet Cholesky-Zerlegung . Um den Wikipedia-Artikel zu zitieren:

Wenn $ A $ symmetrisch und positiv definit ist, können wir zuerst $ Ax = b $ [für $ x $] lösen Berechnen der Cholesky-Zerlegung $ A = LL ^ \ mathrm {T} $, dann Lösen von $ Ly = b $ für $ y $ und schließlich Lösen von $ L ^ \ mathrm {T} x = y $ für $ x $.

Ich bin mir nicht ganz sicher, wonach Sie in Ihrer zweiten Frage suchen. Bietet eine Lösung für die erste Frage nicht auch eine Lösung für die zweite? Sicherlich ist es nicht schwierig, eine Zeile und eine Spalte rechnerisch aus einer Matrix zu entfernen, und das ist sicherlich alles, was für die Vorverarbeitung erforderlich ist?

#3
+5
Hans Engler
2011-04-14 19:34:06 UTC
view on stackexchange narkive permalink

In Bezug auf Ihre zweite Frage finden Sie hier eine Möglichkeit, dies für $ n = i $ zu tun, um die Notation zu vereinfachen. Sei $ \ alpha = A_ {nn}, \, a = (A_ {1n}, \ dots, A_ {n-1, n}) ^ T $ und daher $$ A = \ begin {pmatrix} \ tilde A & a \\ a ^ T & \ alpha \ end {pmatrix} $$ Lassen Sie auch $ A ^ {- 1} $ auf die gleiche Weise partitionieren, $$ A ^ {- 1} = \ begin {pmatrix} \ tilde C. & c \\ c ^ T & \ gamma \ end {pmatrix} $$ Ich verstehe, Sie möchten $ \ tilde A ^ {- 1} $ und haben bereits $ A ^ {- 1} $ berechnet. Setze $ d = \ tilde A ^ {- 1} a $ und $ \ delta = c ^ Ta $. Diese Mengen erscheinen bereits in $ A ^ {- 1} $, da $$ A ^ {- 1} = \ begin {pmatrix} \ tilde A ^ {- 1} + \ frac {1} {\ alpha - \ delta} dd ^ T & - \ frac {1} {\ alpha - \ delta} d \\ - \ frac {1} {\ alpha - \ delta} d ^ T & \ frac {1} {\ alpha - \ delta} \ end {pmatrix} $$ wie eine direkte Berechnung zeigt. Daher ist $$ \ tilde A ^ {- 1} = \ tilde C - \ frac {1} {\ alpha - \ delta} dd ^ T = \ tilde C - \ frac {1} {\ gamma} cc ^ T $ $ ist ein $ O (n ^ 2) $ -Update von $ A ^ {- 1} $.

Als Faustregel gilt jedoch, dass Downdates anfälliger für numerische Instabilität sind als Aktualisierungen.


Diese Fragen und Antworten wurden automatisch aus der englischen Sprache übersetzt.Der ursprüngliche Inhalt ist auf stackexchange verfügbar. Wir danken ihm für die cc by-sa 3.0-Lizenz, unter der er vertrieben wird.
Loading...