Bedingungsnummer der A'A- und AA'-Formulierungen

9

Es wird gezeigt (Yousef Saad, Iterative Methoden für spärliche lineare Systeme , S. 260), dass $cond(A'A) \approx cond(A)^2$

Gilt das auch für ? $AA'$

Im Fall ist mit , beachten , dass I $A$ $N\times M$ $N \ll M$ $cond(A'A) \gg cond(AA')$

Bedeutet das, dass in diesem Fall eine Formulierung in Bezug auf vorzuziehen ist? $AA'$

linear-algebra condition-number Alexander
quelle

2

Sie vergleichen die Bedingungsnummern von zwei Matrizen mit sehr unterschiedlichen Größen. Ohne eine Erklärung, warum, scheint dieser Vergleich wahrscheinlich nicht aussagekräftig zu sein. Wenn Sie mit der viel kleineren Matrix das erreichen können, was Sie brauchen, sollten Sie dies natürlich tun (auch wenn die Konditionierung ähnlich wäre).

David Ketcheson

1

Die neue Antwort von Stefano M unten ist richtig. Bitte lesen Sie es und stimmen Sie ab.

David Ketcheson

6

Wenn mit , dann ist so dass nicht den vollen Rang haben kann, dh es ist singulär. $A\in\mathbb{R}^{N\times M}$ $N<M$

r a n k (A^{T} A) = r a n k (A A^{T}) = r a n k (A) \leq N < M

$\mathop{\mathrm{rank}}(A^TA) = \mathop{\mathrm{rank}}(AA^T) = \mathop{\mathrm{rank}}(A) \leq N < M$

A^{T} A \in R^{M \times M}

$A^TA \in \mathbb{R}^{M\times M}$

Dementsprechend ist die Bedingungsnummer . Aufgrund der endlichen Präzisionsarithmetik erhalten Sie beim Berechnen in Matlab eine große Zahl, nicht . $\kappa_2(A^TA)=\infty$ cond(A'A)Inf

Stefano M.
quelle

@OscarB: Die Singularwerte von sind nur , es gibt keinen ten Singularwert! Ihre Ableitung ist korrekt, aber bitte beachten Sie, dass wenn , die sv von , , während mit nachgestellten Nullen.

A

$A$

N

$N$

M

$M$

σ_{i}

$\sigma_i$

i = 1 \dots N

$i=1\dots N$

A

$A$

S S^{T} = d i a g (σ_{1}^{2}, \dots, σ_{n}^{2})

$SS^T=\mathop{\mathrm{diag}}(\sigma_1^2,\dots,\sigma_n^2)$

S^{T} S = d i a g (σ_{1}^{2}, \dots, σ_{n}^{2}, 0, \dots, 0)

$S^TS = \mathop{\mathrm{diag}}(\sigma_1^2,\dots,\sigma_n^2, 0, \dots, 0)$

M - N

$M-N$

Stefano M

8

Schauen wir uns an, warum ungefähr die quadratische Bedingungszahl von . Unter Verwendung der SVD-Zerlegung von mit , , können wir als ausdrücken $A^TA$ $A$ $A=USV^T$ $U \in \mathbb{R}^{N \times N}$ $S \in \mathbb{R}^{N \times M}$ $V \in \mathbb{R}^{M \times M}$ $A^T A$

$A^T A=(USV^T)^T USV^T=VS^T U^T U S V^T=V S^T S V^T$

Was wir erreichen mit der Feststellung , dass orthonormal ist, so dass . Ferner Wir bemerken , daß eine diagonale Matrix ist, so dass die endgültige Zersetzung von kann ausgedrückt werden , wobei bedeutet , eine Diagonalmatrix mit dem ersten N singuläre Werte ergeben aus quadratisch in der Diagonale. Dies bedeutet, dass, da die Bedingungsnummer das Verhältnis des ersten und des letzten Singularwerts ist, für , $U$ $U^T U=I$ $S$ $A^TA$ $V S^2 V^T$ $S^2$ $S^T S$ $S$ $cond(A)=\frac{s_1}{s_N}$ $A \in \mathbb{R}^{N \times M}$

$cond(A^T A)=\frac{s_1^2}{s_M^2}=(\frac{s_1}{s_M})^2=cond(A)^2$

Jetzt können wir dieselbe Übung mit : $AA^T$

$AA^T=USV^T (USV^T)^T=USV^T V S^T U^T=U S^2 U^T$

Dies bedeutet, dass wir das Ergebnis , da hier , ein subtiler Unterschied zur obigen Notation. $cond(AA^T)=\frac{s_1^2}{s_N^2}$ $S^2$ $SS^T$

Aber beachten Sie diesen subtilen Unterschied! Für hat die Bedingungsnummer den M'ten Singularwert im Nenner, während den N'ten Singularwert hat. Dies erklärt, warum Sie signifikante Unterschiede in der Bedingungsnummer sehen - wird tatsächlich „besser konditioniert“ als . $A^TA$ $AA^T$ $AA^T$ $A^TA$

Trotzdem hatte David Ketcheson Recht - Sie vergleichen die Bedingungsnummern zwischen zwei sehr unterschiedlichen Matrizen. Insbesondere ist das, was Sie mit können, nicht dasselbe wie das, was Sie mit . $A^TA$ $AA^T$

OscarB
quelle

Das ist eine gute Erklärung! Ich sehe den Unterschied jetzt deutlich. Matrix A wird verwendet, um normale Gleichungen zu erstellen, und mit geringfügigen Änderungen können Sie sie auch als formulieren , nicht als klassisches . Können Sie auch sagen, ob es vorteilhaft ist, einen Löser wie LSQR zu verwenden, anstatt normale Gleichungen zu lösen? Da LSQR dieses Produkt überhaupt nicht erstellen muss.

A A^{'}

$AA'$

A^{'} A

$A'A$

Alexander

Ich bin froh, dass es Sinn machte. Im Allgemeinen müssen Sie die Konditionierung des Problems berücksichtigen. Wenn dies jedoch kein Problem darstellt, können Sie je nach Größe des Problems (unter anderem) entweder normale Gleichungen / QR-Faktorisierung (von A) / LSQR verwenden. Wenn Ihr Problem nicht groß oder schlecht konditioniert ist, würde ich wahrscheinlich die QR-Faktorisierung anwenden, aber ohne mehr Wissen über das Problem, das Sie zu lösen versuchen, ist es schwer zu sagen. Ich bin sicher, dass andere mit mehr Erfahrung detailliertere Ratschläge geben könnten.

OscarB

Das A selbst ist schlecht konditioniert (mit einer Bedingungsnummer von ), dicht und groß. QR ist keine Option. Da es schlecht konditioniert ist, muss ich sowieso eine Regularisierung hinzufügen. Jetzt scheint eine einfache Tikhonov-Regularisierung genug zu sein. Der Punkt ist, dass wenn (für meinen Fall mit ), die Verwendung von LSQR immer vorzuziehen scheint, da Sie bei kein Produkt bilden müssen alle. Die Frage ist, ob mit normalen Gleichungen und LSQR erhaltene Lösungen identisch sind.

\approx 10^{7}

$\approx 10^7$

c o n d (A) < c o n d (A A^{T}) < c o n d (A^{T} A)

$cond(A) < cond(AA^T) < cond(A^T A)$

N < M

$N < M$

Alexander

Nun, so wie ich es verstehe, wird LSQR nach "unendlich vielen" Iterationen mit exakter Genauigkeit eine identische Lösung für normale Gleichungen liefern. Bei schlecht gestellten Problemen ist die normale Gleichungslösung jedoch nicht die gewünschte. Stattdessen möchten Sie LSQR verwenden, um zu iterieren, bis eine Halbkonvergenz erreicht ist. Die Steuerung iterativer Algorithmen bei schlecht gestellten Problemen ist jedoch ein ganz anderes Ballspiel. Abhängig von den Kosten Ihres Matrix-Vektor-Produkts und der Anzahl der benötigten Iterationen (und damit Matveken) ist eine direkte Tikhonov-Lösung mit Bidiagonalisierung möglicherweise besser.

OscarB

Tolle Erklärung. +1 für Sie, Sir!

Meawoppl

2

Die Behauptung, dass (für quadratische Matrizen) ~~in der Frage und~~ [Bearbeiten: Ich habe falsch gelesen] in Artans Antwort Unsinn ist. Gegenbeispiel $\DeclareMathOperator{\cond}{cond} \cond A^2 \approx \cond A^T A$

A = (\begin{matrix} ϵ & 1 \\ 0 & ϵ \end{matrix}), ϵ ≪ 1

$\newcommand\bigO{\mathcal{O}}A = \begin{pmatrix} \epsilon & 1 \\ 0 & \epsilon \end{pmatrix}, \quad \epsilon \ll 1$

für die Sie leicht überprüfen können, ob während . $\cond A^T A = \bigO(\epsilon^{-4})$ $\cond A^2 = \bigO(\epsilon^{-2})$

Jed Brown
quelle

Ok, um zu betonen, dass und im Allgemeinen sehr unterschiedlich sind, was Eigs, Svds, Cond-Nummer betrifft: aber meiner Meinung nach geht es in der Behauptung der Frage um .

A^{2}

$A^2$

A^{T} A

$A^T A$

[c o n d (A)]^{2}

$[\mathrm{cond}(A)]^2$

Stefano M

@StefanoM Danke, es scheint, dass ich falsch verstanden habe, obwohl aus der Diskussion nicht der einzige.

Jed Brown

1

In exakter arithmetischer Bedingung (A ^ 2) = Bedingung (A'A) = Bedingung (AA '), siehe z. Golub und van Loan, 3. Aufl., S. 70. Dies gilt nicht für die Gleitkomma-Arithmetik, wenn A fast einen Rangmangel aufweist. Der beste Rat ist, die oben genannten Buchrezepte zu befolgen, wenn Sie Probleme mit den kleinsten Quadraten lösen. Am sichersten ist der SVD-Ansatz, S. 257. Verwenden Sie stattdessen \ varepsilon-rank, wenn Sie SVD berechnen, wobei \ varepsilon die Auflösung Ihrer Matrixdaten ist.

Artan
quelle

Es tut mir leid, ich habe mir Golub und Van Loan angesehen. 70 und konnte nichts finden, was die Aussage cond (A ^ 2) = cond (A ^ TA) = cond (AA ^ T) stützt. Könnten Sie mit Ihrer Referenz genauer sein?

OscarB

Es gibt dort keine Aussage, aber Sie können aus Satz 2.5.2 und der Pseudoinverse, Abschnitt 5.5.4, ableiten, dass cond (AA ') = cond (A'A). Der Grund, warum ich Pseudoinverse nehme, ist, dass dies für das Problem der kleinsten Quadrate in der Hand wichtig ist. Die Gleichheit nach cond (A ^ 2) sollte \ approx sein, entschuldigen Sie den Tippfehler.

Artan

Nein, diese Antwort ist völlig falsch. Siehe mein Gegenbeispiel.

Jed Brown

Saad muss einen solchen Punkt in einem bestimmten Kontext gemacht haben. Relevant für die vorliegende Frage ist das vorgehende Argument.

Artan

Bedingungsnummer der A'A- und AA'-Formulierungen

Antworten: