Was sollten die Kriterien sein, um einzelne Werte zu akzeptieren / abzulehnen?

Ich löse ein System mit Singularwertzerlegung. Die Singularwerte (vor der Skalierung) sind:

1.82277e+29
1.95011e+27
1.15033e+23
1.45291e+21
4.79336e+17
7.48116e+15
8.31087e+12
1.71838e+11
5.63232e+08
2.17863e+08
9.02783e+07
1.72345e+07
1.73889e+05
8.09382e+02
2.16644e+00

Ich habe festgestellt, dass das Akzeptieren aller Singularwerte und des damit verbundenen Beitrags zu meinem Lösungsvektor zu schlechten Ergebnissen führt. Ich skaliere sie alle nach der größten Zahl und erhalte singuläre Werte von:

1.0
1.06986e-02
6.31091e-07
7.97089e-09
2.62971e-12
4.10428e-14
4.55948e-17
9.42732e-19
3.08998e-21
1.19523e-21
4.95281e-22
9.45510e-23
9.53980e-25
4.44040e-27
1.18854e-29

Die beste Lösung wird nur schlecht, wenn ich die letzten beiden einbeziehe, und wird erst um die $10^{-19}$ Amtszeit gut.

Wenn ich die letzten beiden Begriffe einbeziehe, sinkt die Genauigkeit stark. Warum ist das so? Was sind die Kriterien für das Einschließen / Nichteinschließen von Singularwerten?

$m \times n$ $m \gg n$ $A\cdot X = B$ $A$ $A^\top A X = A^\top X$

Ich beurteile die Antworten auf meine Lösungen daran, wie gut sie meinen verrauschten Daten entsprechen.

$-10$ $10$

linear-algebra regression svd drjrm3
quelle

Wenn Sie erwähnen, welche Tags Sie entweder im Beitrag oder in einem Kommentar erstellen möchten, kann sich jemand mit höheren Repräsentanten darum kümmern.

David Z

@ DavidKetcheson: Ich bin mir nicht ganz sicher, ob wir diese spezifischen Tags wirklich brauchen ... noch nicht. Vielleicht, wenn wir viele SVD-Fragen haben ... aber ich denke, lineare Algebra sollte vorerst ein ausreichender Tag sein.

Antworten:

$\max(m,n) \epsilon \|A\|_2$ $A$ $m \times n$ $\epsilon$ $\|A\|_2$ $A$

Wie JM erwähnte, ist es jedoch viel stabiler, die Bildung von zu vermeiden : $A^H A$

Zuerst müssen wir die Singularwertzerlegung dann können wir die Pseudoinverse durch wobei

[U, Σ, V] = s v d (A)

$[U,\Sigma,V] = \mathrm{svd}(A)$

A^{†} = V f (Σ) U^{H},

$A^\dagger = V\; f(\Sigma)\; U^H,$

f (σ) = {\begin{cases} 1 / σ, σ \geq max (m, n) ϵ ‖ A ‖_{2}, \\ 0, otherwise \end{cases}

$f(\sigma) = \begin{cases}1/\sigma,\quad\sigma \ge \max(m,n) \epsilon \|A\|_2,\\ 0,\quad\text{otherwise}\end{cases}$

Die Lösung kann dann berechnet werden als

X = A^{†} B .

$X = A^\dagger B.$

Jack Poulson
quelle

Ich denke, es ist besser, explizit zu sein und zu sagen, dass die Matrix-2-Norm genau der größte Singularwert ist ... außerdem muss nicht quadratisch sein, um das Schwellenwertkriterium anzuwenden (aber man ersetzt das mit für eine Matrix).

A

$\mathbf A$

n

$n$

max (m, n)

$\max(m,n)$

m \times n

$m\times n$

anstelle von A † = U f (Σ) * VH sollte es nicht A † = V f (Σ) * U 'sein?

drjrm3

Ja, danke euch beiden. Ich habe vor ein paar Tagen eine parallele pseudoinverse Routine für hermitische Matrizen geschrieben und anscheinend nicht genug über die Unterschiede zum allgemeinen Fall nachgedacht.

Jack Poulson

Pseudoinverse sind kein Allheilmittel für schlecht konditionierte Probleme, obwohl sie dazu neigen, zu helfen. Polynominterpolation höherer Ordnung ist notorisch schlecht konditioniert und wird am besten vermieden. Ich empfehle Ihnen, den Wiki-Artikel über das Phänomen von Runge zu lesen und dann für Ihre Interpolation auf eine andere Basis zu wechseln (z. B. stückweise Polynome oder Splines).

Jack Poulson

Diese Diskussion bezieht sich nicht mehr auf Ihre ursprüngliche Frage. Ob Ihre Implementierung einer fragwürdigen Näherung der kleinsten Quadrate konvergiert oder nicht, ist für Ihre ursprüngliche Frage nicht relevant. Ich schlage vor, Sie stellen eine weitere Frage, wenn Sie immer noch verwirrt sind.

Jack Poulson

Augh !! Nein, nein , tausendmal, nein !

Der Grund, warum Menschen SVD verwenden, besteht genau darin, zu vermeiden, dass die produktübergreifende Matrix , da die Bildung dieser Matrix ein gutes Rezept für die Bildung schlecht konditionierter linearer Systeme ist! Die Zerlegung soll direkt auf angewendet werden . (Siehe auch einige meiner vorherigen Antworten .) $\mathbf A^\top\mathbf A$ $\mathbf A$

Ich habe Ihnen bereits erwähnt, dass das übliche Kriterium für das Nullstellen von Singularwerten darin besteht, sie mit dem Produkt aus dem größten Singularwert und dem Maschinen-Epsilon zu vergleichen. Dies wird jedoch durch Ihre Bildung der Kreuzproduktmatrix in Frage gestellt. Bitte versuchen Sie erneut, die Zerlegung auszuführen, diesmal jedoch auf der Entwurfsmatrix selbst anstelle der produktübergreifenden Matrix. Jeder andere Weg ist ein offensichtlicher Missbrauch der Zersetzung.

JM
quelle

Ich kann das nicht genug bewerten ... dies ist der wichtigste Punkt bei der korrekten Verwendung von SVD-Techniken. Denken Sie daran, dass die Singularwerte von die Quadrate der Singularwerte von !

A^{T} A

$A^T A$

A

$A$

Khinsen

Genau. Das Quadrieren einer winzigen Zahl führt zu einer noch winzigeren Zahl. In Anbetracht der Tatsache, dass die 2-Norm-Bedingungszahl das Verhältnis des größten zum kleinsten Singularwert ist, ist dies eine Möglichkeit zu erkennen, warum der Ansatz der normalen Gleichungen für große Systeme eine schlechte Idee sein kann.

Ich denke, dass mehrere Leute hier wertvolle Tipps für Ihr Problem gegeben haben.

Zum späteren Nachschlagen könnte Ihre Frage, wie ein schlecht gestelltes lineares Problem der kleinsten Quadrate gelöst werden kann, durch einen Blick auf die immense Literatur zu diesem Problem beantwortet werden.

Insbesondere können Sie die TSVD (Truncated Singular Value Decomposition) als einfache Methode verwenden, um die Lösung zu erhalten: wobei der i-te Singularwert ist, und die i-te Spalte in den Matrizen sind und aus der Faktorisierung , ist die rechte Seite Ihres Problems, und die Notation bedeutet das komplexe Konjugat der Einträge und wird dann zu einer Zeile Vektor, so dass

x_{k} = \sum_{i = 1}^{k} \frac{u_{i}^{H} b}{σ_{i}} v_{i}

$\mathbf{x}_k = \sum_{i=1}^{k} \frac{\mathbf{u}_i^H \mathbf{b}}{\sigma_i}\mathbf{v}_i$

σ_{i}

$\sigma_i$

u_{i}

$\mathbf{u}_i$

v_{i}

$\mathbf{v}_i$

U

$U$

V

$V$

U S V^{H} = A

$USV^H=A$

b

$\mathbf{b}$

u^{H}

$\mathbf{u}^H$

u^{H} b

$\mathbf{u}^H \mathbf{b}$ ergibt einen Skalar (Punktprodukt). Ihre Lösung ist also der Vektor .

x_{k}

$\mathbf{x}_k$

Das Hauptproblem in dieser Einstellung ist, abgesehen davon, dass die SVD berechnet werden muss, was ziemlich teuer ist, die Auswahl der Anzahl der zu verwendenden Singularwerte, dh . Auch hier gibt es eine Reihe von Möglichkeiten, aber die beliebtesten sind das Diskrepanzprinzip, die generalisierte Kreuzvalidierungsmethode und die L-Kurve. $k$

All dies (und noch viel mehr) ist in Matlab in der hervorragenden Toolbox Regularization Tools implementiert, die von Prof. Per Christian Hansen verfasst wurde, der auch mehrere Artikel und einige Bücher zu inversen Problemen veröffentlicht hat. Die Toolbox ist einfach zu bedienen und sollte sich leicht in andere Programmiersprachen übersetzen lassen.

Während andere wichtige Erkenntnisse zu Ihrer Anwendung geliefert haben, die darauf hindeuten, dass andere Ansätze besser geeignet sind, ist das Obige eine kurze Zusammenfassung darüber, wie Sie das Problem lösen können, wenn Sie es noch benötigen.

OscarB
quelle

Danke, mir ist das meiste bewusst. Ich habe viele Ressourcen durchsucht - das Problem ist, dass meine Lösungen immer schlechter werden, wenn ich meinen verwendeten Basissatz vergrößere. Ich bin zu dem Schluss gekommen, dass dies daran liegt, dass die Anzahl der singulären Werte, die mit zunehmendem Basissatz abgelehnt werden, im Verhältnis zur Anzahl der verwendeten Basisfunktionen zunimmt. Das heißt, wenn ich n = 100 Basisfunktionen verwendet habe, muss ich 95 der Singularwerte wegwerfen, und dies ergibt ein schlechteres Ergebnis als wenn ich 10 Basissätze verwende und nur einen Singularwert rauswerfe.

drjrm3

Richtig - nun, wie andere vorgeschlagen haben, sollten Sie sich Ihre Basisfunktionen ansehen und vielleicht eine Basis finden, die Ihren Daten besser entspricht. Splines könnten eine Option sein. Dies könnte auch Kriging tun, obwohl dies ein völlig anderer Ansatz ist, der mir mehrfach gute Ergebnisse gebracht hat.

OscarB