Warum sind SPD-Matrizen so wichtig?

20

Ich kenne die Definition der symmetrischen positiv definierten (SPD) Matrix, möchte aber mehr verstehen.

Warum sind sie intuitiv so wichtig?

Hier ist was ich weiß. Was sonst?

Für gegebene Daten ist die Kovarianzmatrix SPD. Die Kovarianzmatrix ist eine wichtige Metrik. Eine intuitive Erklärung finden Sie in diesem hervorragenden Beitrag .
Die quadratische Form ist konvex, wenn SPD ist. Konvexität ist eine nette Eigenschaft für eine Funktion, die sicherstellen kann, dass die lokale Lösung eine globale Lösung ist. Bei konvexen Problemen gibt es viele gute Algorithmen zu lösen, nicht jedoch bei nicht-kovexen Problemen. $\frac 1 2 x^\top Ax-b^\top x +c$ $A$
Wenn SPD ist, sind die Optimierungslösung für die quadratische Form und die Lösung für das lineare System gleich. Wir können also Konvertierungen zwischen zwei klassischen Problemen durchführen. Dies ist wichtig, da es uns ermöglicht, Tricks, die in einer Domäne entdeckt wurden, in einer anderen zu verwenden. Zum Beispiel können wir die konjugierte Gradientenmethode verwenden, um ein lineares System zu lösen. $A$
$minimieren \frac{1}{2} x^{⊤} EIN x - b^{⊤} x + c$ $\text{minimize}~~~ \frac 1 2 x^\top Ax-b^\top x +c$ $EIN x = b$ $Ax=b$
Es gibt viele gute Algorithmen (schnell, numerisch stabil), die für eine SPD-Matrix besser funktionieren, z. B. die Cholesky-Zerlegung.

EDIT: Ich versuche nicht, die Identitäten nach der SPD-Matrix zu fragen, sondern die Intuition hinter der Eigenschaft, um die Wichtigkeit zu zeigen. Zum Beispiel, wie von @Matthew Drury erwähnt, wenn eine Matrix SPD ist, sind Eigenwerte alle positiven reellen Zahlen, aber warum alle positiven Angelegenheiten. @ Matthew Drury hatte eine großartige Antwort auf Flow und das ist, wonach ich gesucht habe.

mathematical-statistics optimization covariance-matrix intuition linear-algebra Haitao Du
quelle

7

Eigenwerte sind alle positiven reellen Zahlen. Diese Tatsache liegt vielen anderen zugrunde.

Matthew Drury

4

Um etwas weiter zu gehen als @Matthew: Wenn Sie eine geeignete Basis wählen, sind alle diese Matrizen gleich und entsprechen der Identitätsmatrix. Mit anderen Worten, es gibt in jeder Dimension genau eine positiv-definitive quadratische Form (für reelle Vektorräume) und diese entspricht der euklidischen Distanz.

Whuber

2

Sie werden eine gewisse Intuition in den vielen elementaren Möglichkeiten finden, wie die Eigenwerte einer reellen symmetrischen Matrix alle reell dargestellt werden können: mathoverflow.net/questions/118626/… Insbesondere die quadratische Form kommt natürlich im Rayleigh-Quotienten und vor Symmetrische Matrizen bieten eine natürliche Möglichkeit, eine große Familie von Matrizen zu präsentieren, deren Eigenwerte reell sind. Siehe den Courant-Minimax-Satz zum Beispiel: en.wikipedia.org/wiki/Courant_minimax_principle

x^{T} A x

$x^TAx$

Alex R.

4

Dies scheint zu weit gefasst zu sein: Wenn es nicht bereits drei Antworten gegeben hätte, hätte ich es wahrscheinlich auf dieser Grundlage geschlossen. Bitte mehr Orientierung bieten , was Sie genau wissen möchten (Intuition gefragt ist viel zu persönlich / Individuum für Menschen an , wie diese in einem Fall zu erraten)

Glen_b -Reinstate Monica

1

Es fällt mir schwer, eine Situation in der Statistik zu finden , die zu einer Matrix führen würde, die nicht psd ist (es sei denn, Sie haben die Berechnung einer Korrelationsmatrix verkorkst, z. B. indem Sie sie mit einer paarweisen Korrelation auffüllen, die für Daten mit fehlenden Werten berechnet wurde). . Jede quadratische symmetrische Matrix, die ich mir vorstellen kann, ist entweder eine Kovarianz, eine Information oder eine Projektionsmatrix. (An anderer Stelle in der angewandten Mathematik können die Nicht-PSD-Matrizen eine kulturelle Norm sein, z. B. die Finite-Elemente-Matrizen in PDE.)

StasK

15

Eine (reelle) symmetrische Matrix hat einen vollständigen Satz von orthogonalen Eigenvektoren, für die die entsprechenden Eigenwerte alle reelle Zahlen sind. Bei unsymmetrischen Matrizen kann dies fehlschlagen. Beispielsweise hat eine Drehung im zweidimensionalen Raum keinen Eigenvektor oder Eigenwerte in den reellen Zahlen. Sie müssen zu einem Vektorraum über die komplexen Zahlen gehen, um sie zu finden.

Wenn die Matrix zusätzlich positiv definit ist, dann sind diese Eigenwerte alle positive reelle Zahlen. Diese Tatsache ist viel einfacher als die erste, denn wenn ein Eigenvektor mit Einheitslänge und der entsprechende Eigenwert ist, dann $v$ $\lambda$

λ = λ v^{t} v = v^{t} A v > 0

$\lambda = \lambda v^t v = v^t A v > 0$

wo die letzte Gleichheit die Definition der positiven Bestimmtheit verwendet.

Für die Intuition ist es wichtig, dass die Eigenvektoren und Eigenwerte einer linearen Transformation das Koordinatensystem beschreiben, in dem die Transformation am einfachsten zu verstehen ist. Eine lineare Transformation kann auf einer "natürlichen" Basis wie dem Standardkoordinatensystem sehr schwer zu verstehen sein, jedoch wird jede mit einer "bevorzugten" Basis von Eigenvektoren geliefert, bei denen die Transformation als Skalierung in alle Richtungen wirkt. Dies erleichtert das Verständnis der Geometrie der Transformation.

Beispielsweise wird der Test der zweiten Ableitung für die lokalen Extrema einer Funktion häufig als eine Reihe mysteriöser Bedingungen angegeben, die einen Eintrag in die Matrix der zweiten Ableitung und einige Determinanten beinhalten. Tatsächlich kodieren diese Bedingungen einfach die folgende geometrische Beobachtung: $R^2 \rightarrow R$

Wenn die Matrix der zweiten Ableitungen eindeutig positiv ist, befinden Sie sich an einem lokalen Minimum.
Wenn die Matrix der zweiten Ableitungen eindeutig negativ ist, haben Sie ein lokales Maximum.
Ansonsten sind Sie weder an einem Sattelpunkt.

Sie können dies mit der obigen geometrischen Argumentation auf einer eigenen Basis verstehen. Die erste Ableitung an einem kritischen Punkt verschwindet, so dass die Änderungsraten der Funktion hier von der zweiten Ableitung gesteuert werden. Jetzt können wir geometrisch argumentieren

Im ersten Fall gibt es zwei Eigenrichtungen, und wenn Sie sich entlang einer bewegen, nimmt die Funktion zu.
In der zweiten, zwei Eigenrichtungen, und wenn Sie sich in eine der beiden Richtungen bewegen, nimmt die Funktion ab.
In der letzten gibt es zwei Eigenrichtungen, in der einen nimmt die Funktion zu und in der anderen ab.

Da die Eigenvektoren den gesamten Raum überspannen, ist jede andere Richtung eine Linearkombination von Eigenrichtungen, so dass die Änderungsraten in diesen Richtungen Linearkombinationen der Änderungsraten in den Eigenrichtungen sind. Tatsächlich gilt dies in alle Richtungen (dies bedeutet mehr oder weniger, dass eine Funktion, die in einem höherdimensionalen Raum definiert ist, differenzierbar ist). Wenn Sie nun ein kleines Bild in Ihrem Kopf zeichnen, ergibt dies viel Sinn für etwas, das in Anfängerkalkültexten ziemlich mysteriös ist.

Dies gilt direkt für einen Ihrer Aufzählungspunkte

Die quadratische Form ist konvex, wennSPD ist. Convex ist eine nette Eigenschaft, die sicherstellen kann, dass die lokale Lösung eine globale Lösung ist $\frac 1 2 x^\top Ax-b^\top x +c$ $A$

Die Matrix der zweiten Ableitungen ist überall , was symmetrisch positiv definit ist. Geometrisch bedeutet dies, dass sich die Funktion selbst über ihrer Tangentialebene verbiegt , wenn wir uns in eine beliebige Eigenrichtung (und damit in eine beliebige Richtung, da jede andere eine lineare Kombination von Eigenrichtungen ist) bewegen . Dies bedeutet, dass die gesamte Oberfläche konvex ist. $A$

Matthew Drury
quelle

5

Eine grafische Sichtweise: Wenn

SPD ist, sind die Konturen der zugehörigen quadratischen Form ellipsoidisch.

A

$\mathbf A$

JM ist kein Statistiker

7

Diese Charakterisierung durch @JM ist sehr einfühlsam. Falls sich jemand wundert, was an ellipsoiden Konturen besonders sein könnte, beachten Sie, dass es sich nur um perfekte, getarnte Kugeln handelt: Die Maßeinheiten können sich entlang ihrer Hauptachsen unterscheiden, und die Ellipsoide können in Bezug auf die Koordinaten, in denen die Daten beschrieben werden, gedreht werden Aber für viele Zwecke - insbesondere für konzeptionelle - sind diese Unterschiede unerheblich.

Whuber

Das hängt damit zusammen, wie ich Newtons Methode geometrisch verstehe. Am besten approximieren Sie die aktuelle Ebene mit einem Ellipsoid und nehmen Sie dann ein Koordinatensystem, in dem das Ellipsoid ein Kreis ist. Bewegen Sie sich orthogonal zum Kreis in diesem Koordinatensystem.

Matthew Drury

1

Wenn es (aktive) Bedingungen gibt, müssen Sie in das Jacobi der aktiven Bedingungen projizieren, bevor Sie das Eigenwert- und Eigendirektionsspiel ausführen. Wenn das Hessische psd ist, ist die (beliebige) Projektion psd, aber die Umkehrung ist nicht unbedingt wahr und ist es oft nicht. Siehe meine Antwort.

Mark L. Stone

10

Sie werden eine gewisse Intuition in den vielen elementaren Möglichkeiten finden, die Eigenwerte einer reellen symmetrischen Matrix so darzustellen, dass sie alle reell sind: /mathpro/118626/real-symmetric-matrix-has-real-eigenvalues-elementary- proof / 118640 # 118640

Insbesondere die quadratische Form kommt im Rayleigh-Quotienten auf natürliche Weise vor, und symmetrische Matrizen bieten die wohl natürlichste Möglichkeit, eine große Familie von Matrizen mit reellen Eigenwerten darzustellen. Siehe den Courant-Minimax-Satz zum Beispiel: https://en.wikipedia.org/wiki/Courant_minimax_principle $x^TAx$

$d(x,y)=\langle x,Ay\rangle=x^TAy$ $x,y$ $d(x,y)=d(y,x)$ $x,y$ $\|x\|^2=x^TAx>0$ $x\neq 0$

Diese letztgenannte Eigenschaft ist im Bereich der Support-Vektor-Maschinen, insbesondere der Kernel-Methoden und des Kernel-Tricks , bei denen der Kernel symmetrisch positiv sein muss, um das richtige innere Produkt zu induzieren, von entscheidender Bedeutung. In der Tat verallgemeinert der Satz von Mercer die intuitiven Eigenschaften symmetrischer Matrizen auf funktionale Räume.

Alex R.
quelle

9

$f(x + \Delta x)$

f (x + Δ x) \approx f (x) + Δ x^{T} \nabla f (x) + \frac{1}{2} Δ x^{T} \nabla^{2} f (x) Δ x

$f(x + \Delta x)\approx f(x) + \Delta x^T \nabla f(x)+ \frac{1}{2} \Delta x^T \nabla^2 f(x) \Delta x$

$\Delta x$

f^{'} (x + Δ x) \approx \nabla f (x) + \nabla^{2} f (x) Δ x

$f'(x + \Delta x)\approx \nabla f(x) + \nabla^2 f(x) \Delta x$

$\Delta x$

Δ x = - \nabla^{2} f (x)^{- 1} \nabla f (x)

$\Delta x = -\nabla^2 f(x)^{-1} \nabla f(x)$

$\nabla^2 f(x)$ $\Delta x$

\nabla f (x)^{T} Δ x = - \nabla f (x)^{T} \nabla^{2} f (x)^{- 1} \nabla f (x) < 0

$\nabla f(x)^T \Delta x = -\nabla f(x)^T \nabla^2 f(x)^{-1} \nabla f(x) < 0$

Bei Verwendung der Newton-Methode werden hessische Nicht-SPD-Matrizen typischerweise als SPD "angestupst". Es gibt einen netten Algorithmus namens modifiziertes Cholesky, der ein Nicht-SPD-Hessisch erkennt, es in die richtige Richtung "stupst" und das Ergebnis faktorisiert, und das alles zu (im Wesentlichen) den gleichen Kosten wie bei einer Cholesky-Faktorisierung. Quasi-Newton-Methoden vermeiden dieses Problem, indem sie den ungefähren Hessischen Wert auf SPD setzen.

Nebenbei bemerkt, erhalten symmetrische undefinierte Systeme heutzutage viel Aufmerksamkeit. Sie tauchen im Kontext von Innenpunktmethoden zur eingeschränkten Optimierung auf.

Bill Woessner
quelle

Vielen Dank für die tolle Antwort. Ich verstehe, dass anständige Richtung in der Liniensuchmethode wichtig ist. Bei Trust-Region-Methoden ist auch eine anständige Ausrichtung wichtig?

Haitao Du

1

Es ist immer noch wichtig für Trust-Region-Methoden. Trust-Region-Methoden funktionieren grundsätzlich, indem die Schrittgröße ZUERST begrenzt und dann nach der Schrittrichtung aufgelöst wird. Wenn der Schritt nicht die gewünschte Verringerung des Zielfunktionswerts erreicht, verringern Sie die Schranke für die Schrittgröße und beginnen von vorne. Stellen Sie sich vor, Ihr Algorithmus zur Generierung der Schrittrichtung garantiert nicht, dass die Schrittrichtung eine Abstiegsrichtung ist. Selbst wenn der Radius des Vertrauensbereichs auf 0 geht, können Sie möglicherweise nie einen akzeptablen Schritt generieren (auch wenn einer vorhanden ist), da keine Ihrer Schrittrichtungen Abstiegsrichtungen sind.

Bill Woessner

Zeilensuchmethoden zeigen grundsätzlich das gleiche Verhalten. Wenn Ihre Suchrichtung keine Abstiegsrichtung ist, wird der Zeilensuchalgorithmus möglicherweise nie eine akzeptable Schrittlänge finden - weil es keine gibt. :-)

Bill Woessner

Tolle Antwort, danke, dass du mir geholfen hast, die Teile zu verbinden.

Haitao Du

9

Geometrisch definiert eine positiv definierte Matrix eine Metrik , beispielsweise eine Riemannsche Metrik, sodass wir sofort geometrische Konzepte verwenden können.

$x$ $y$ $A$

d (x, y) = \sqrt{(x - y)^{T} EIN (x - y)}

$d(x,y) = \sqrt{(x-y)^T A (x-y)}$

$\mathbb{R}^n$

⟨ x, y ⟩ = x^{T} EIN y

$\langle x,y \rangle = x^T A y$

A

$A$

R^{n}

$\mathbb{R}^n$

kjetil b halvorsen
quelle

1

A = I

$\mathbf A=\mathbf I$

6

Es gibt bereits mehrere Antworten, die erklären, warum symmetrische positiv definierte Matrizen so wichtig sind. Deshalb werde ich eine Antwort geben, die erklärt, warum sie nicht so wichtig sind, wie manche Leute, einschließlich der Autoren einiger dieser Antworten, denken. Der Einfachheit halber beschränke ich mich auf symmetrische Matrizen und konzentriere mich auf Hessisch und Optimierung.

Wenn Gott die Welt konvex gemacht hätte, gäbe es keine konvexe Optimierung, sondern nur eine Optimierung. Ebenso gäbe es keine (symmetrischen) positiven bestimmten Matrizen, sondern nur (symmetrische) Matrizen. Aber das ist nicht der Fall, also kümmere dich darum.

Wenn ein quadratisches Programmierproblem konvex ist, kann es "leicht" gelöst werden. Wenn es nicht konvex ist, kann ein globales Optimum immer noch unter Verwendung von Verzweigungs- und gebundenen Methoden gefunden werden (aber es kann länger und mehr Speicher dauern).

Wenn eine Newton-Methode für die Optimierung verwendet wird und der Hessische Wert bei einigen Iterationen unbestimmt ist, ist es nicht erforderlich, ihn auf eine positive Bestimmtheit zu "finageln". Wenn eine Zeilensuche verwendet wird, können Richtungen negativer Krümmung gefunden und die Zeilensuche entlang dieser ausgeführt werden, und wenn ein Vertrauensbereich verwendet wird, gibt es einen ausreichend kleinen Vertrauensbereich, so dass die Lösung des Vertrauensbereichsproblems einen Abstieg erreicht.

Wie bei Quasi-Newton-Methoden behalten BFGS (gedämpft, wenn das Problem eingeschränkt ist) und DFP die positive Bestimmtheit der hessischen oder inversen hessischen Approximation bei. Andere Quasi-Newton-Methoden wie SR1 (Symmetric Rank One) weisen nicht unbedingt eine positive Bestimmtheit auf. Bevor Sie diesbezüglich außer Form geraten, ist dies ein guter Grund, sich für SR1 für viele Probleme zu entscheiden - wenn das Hessische auf dem Weg zum Optimum wirklich nicht positiv bestimmt ist, muss die Quasi-Newton-Näherung positiv bestimmt sein kann zu einer miesen quadratischen Annäherung an die Zielfunktion führen. Im Gegensatz dazu ist die SR1-Aktualisierungsmethode "locker wie eine Gans" und kann ihre Bestimmtheit im weiteren Verlauf verändern.

Bei nichtlinear eingeschränkten Optimierungsproblemen kommt es nicht auf das Hessische der Zielfunktion an, sondern auf das Hessische des Lagrange. Das Hessische des Lagrangischen mag auch im Optimum unbestimmt sein, und tatsächlich ist es nur die Projektion des Hessischen des Lagrangischen in den Nullraum des Jacobischen der aktiven (linearen und nichtlinearen) Bedingungen, die positiv sein müssen -definit am Optimum. Wenn Sie das Hessische des Lagrangischen über BFGS modellieren und es dadurch auf einen positiven Bestimmungswert beschränken, ist es möglicherweise überall schrecklich und funktioniert nicht gut. Im Gegensatz dazu kann SR1 seine Eigenwerte an das anpassen, was es tatsächlich "sieht".

Zu all dem kann ich noch viel mehr sagen, aber das ist genug, um Ihnen einen Vorgeschmack zu geben.

Edit : Was ich 2 Absätze geschrieben habe, ist richtig. Ich habe jedoch vergessen darauf hinzuweisen, dass dies auch für linear beschränkte Probleme gilt. Bei linear beschränkten Problemen ist das Hessische des Lagrangischen genau das Hessische der objektiven Funktion. Die Optimalitätsbedingung 2. Ordnung für ein lokales Minimum ist also, dass die Projektion des Hessischen der objektiven Funktion in den Nullraum des Jacobischen der aktiven Nebenbedingungen positiv semidefinit ist. Insbesondere muss das Hessische der Zielfunktion nicht (notwendigerweise) das Optimum sein und ist es auch bei linear beschränkten Problemen oft nicht.

Mark L. Stone
quelle

"Wer hat Angst vor nicht konvexen Verlustfunktionen?" ... nicht @ MarkL.Stone

GeoMatt22

@ GeoMatt22 Wetten, dass ich nicht @ $$ bin? Wenn Sie andererseits eine Verlustfunktion erstellen (auswählen), müssen Sie sie nicht nicht konvex machen, wenn sie keinem anderen Zweck als dem Showbootfahren dient. Diskretion ist der bessere Teil der Tapferkeit.

Mark L. Stone

@ Mark L. Stone: Das ist interessant! Können Sie auf Literatur verweisen, in der ich über solche Dinge lesen kann?

kjetil b halvorsen

@kjetil b halvorsen. Liniensuche mit Richtungen der negativen Krümmung folk.uib.no/ssu029/Pdf_file/Curvilinear/More79.pdf . Trust-Regionen sind in vielen Büchern und Papieren abgedeckt. Bekanntes Buch mit einer guten Einführung in Trust-Regionen ist amazon.com/… .. Das Monster-Buch ist etwas veraltet und heißt epubs.siam.org/doi/book/10.1137/1.9780898719857 . Bezüglich meines letzten Abschnitts über die Optimalitätsbedingungen lesen Sie die KKT-Bedingungen 2. Ordnung nach

Mark L. Stone,

@kjetil b halvorsen Ich habe mich nicht mit dem Finden des globalen Optimums eines nicht konvexen quadratischen Programms befasst. Weit verbreitete Software wie CPLEX kann dies tun, siehe ibm.com/support/knowledgecenter/SS9UKU_12.6.1/… . Natürlich ist es nicht immer schnell und benötigt möglicherweise etwas Speicher. Ich habe einige QP-Minimierungsprobleme mit Zehntausenden von Variablen gelöst, die mehrere hundert negative Eigenwerte von signifikanter Größe hatten.

Mark L. Stone

5

Sie haben bereits eine Reihe von Gründen genannt, warum SPD wichtig ist, aber Sie haben die Frage trotzdem gestellt. Daher scheint es mir, dass Sie diese Frage zuerst beantworten müssen: Warum sind positive Mengen wichtig?

Meine Antwort ist, dass einige Mengen positiv sein sollten, um mit unseren Erfahrungen oder Modellen in Einklang zu kommen. Zum Beispiel müssen die Abstände zwischen Gegenständen im Raum positiv sein. Die Koordinaten können negativ sein, aber die Abstände sind immer nicht negativ. Wenn Sie also einen Datensatz und einen Algorithmus haben, der ihn verarbeitet, können Sie einen finden, der beim Einspeisen eines negativen Abstands zusammenbricht. Sie sagen also, "mein Algorithmus erfordert zu jeder Zeit positive Abstandseingaben" und es würde sich nicht nach einer unzumutbaren Forderung anhören.

\sum_{ich} (x_{ich} - μ)^{2} / n

$\sum_i (x_i-\mu)^2/n$

x_{i}

$x_i$

Varianz-Kovarianz-Matrizen sind also in dieser Analogie positiv semidefinit, dh "nicht negativ". Das Beispiel eines Algorithmus, der diese Bedingung erfordert, ist die Cholesky-Zerlegung. Sie ist sehr praktisch. Es wird oft als "Quadratwurzel der Matrix" bezeichnet. So wie die Quadratwurzel einer reellen Zahl, die Nicht-Negativität erfordert, möchte Cholesky nicht-negative Matrizen. Wir finden das nicht einschränkend, wenn es um Kovarianzmatrizen geht, weil sie es immer sind.

Das ist meine utilitaristische Antwort. Mithilfe von Einschränkungen wie Nicht-Negativität oder SPD können wir effizientere Berechnungsalgorithmen oder praktische Modellierungswerkzeuge erstellen, die verfügbar sind, wenn Ihre Eingaben diese Einschränkungen erfüllen.

Aksakal
quelle

3

Hier sind zwei weitere Gründe, die nicht erwähnt wurden, warum positiv-semidefinite Matrizen wichtig sind:

Die graphische Laplace-Matrix ist diagonal dominant und damit PSD.
Positive Semidefinitität definiert eine Teilordnung auf der Menge der symmetrischen Matrizen (dies ist die Grundlage der semidefiniten Programmierung).

Thoth
quelle

Warum sind SPD-Matrizen so wichtig?

Antworten: