Wenn ich eine zufällige symmetrische Matrix generiere, wie hoch ist die Wahrscheinlichkeit, dass sie positiv ist?

32

Ich hatte eine seltsame Frage, als ich einige konvexe Optimierungen ausprobierte. Die Frage ist:

Angenommen, ich generiere zufällig (z. B. Standardnormalverteilung) eine Symmetriematrix (z. B. generiere ich eine obere Dreiecksmatrix und fülle die untere Hälfte aus, um sicherzustellen, dass sie symmetrisch ist) ? Gibt es sowieso die Wahrscheinlichkeit zu berechnen?N×N

Haitao Du
quelle
1
Versuchen Sie die Simulation ...
kjetil b halvorsen
1
@kjetilbhalvorsen danke, aber ich frage mich, wie hoch die Wahrscheinlichkeit ist, dass alle Eigenwerte größer als 0 sind. Oder können wir es sogar möglicherweise analytisch tun?
Haitao Du
6
Die Antwort hängt davon ab, wie Sie die Matrix generieren. Zum Beispiel erzeugt ein Weg reelle Eigenwerte gemäß einer gewissen Verteilung und konjugiert dann diese diagonale Matrix durch eine zufällige orthogonale Matrix. Das Ergebnis ist genau dann positiv, wenn alle diese Eigenwerte positiv sind. Wenn Sie Eigenwerte unabhängig nach einer um Null symmetrischen Verteilung erzeugen , dann beträgt diese Chance offensichtlich höchstens 2 - n . Um eine PD-Matrix zu generieren, wählen Sie Ihre Eigenwerte gut aus! (Für eine schnelle Arbeit erstelle ich Matrizen wie Kovarianzen multivariater normaler Daten.)n2n
whuber
11
Keine Antwort auf die gestellte Frage, aber beachten Sie, dass zuerst eine Matrix simuliert wird mit jedem Eintrag iid normal und den gleichen Dimensionen von N, N = L L T symmetrisch und positiv mit Wahrscheinlichkeit 1 bestimmt ist.LNN=LLT
Cliff AB

Antworten:

41

Wenn Ihre Matrizen aus normalnormalen iid-Einträgen gezogen werden, ist die Wahrscheinlichkeit, positiv eindeutig zu sein, ungefähr pN3N2/4 , so zum BeispielwennN=5 ,die Chance 1/1000 ist, und geht nach unten recht schnell danach. Eine ausführliche Diskussion dieser Frage finden Siehier .

Sie können diese Antwort leicht verstehen, indem Sie annehmen, dass die Eigenwertverteilung Ihrer Matrix ungefähr Wigner-Halbkreis ist , der symmetrisch zu Null ist. Wenn die Eigenwerte alle unabhängig waren, müßten Sie eine (1/2)N Chance positiven Definitheit von dieser Logik. In Wirklichkeit ergibt sich ein N2 -Verhalten, sowohl aufgrund von Korrelationen zwischen Eigenwerten als auch aufgrund der Gesetze, die große Abweichungen von Eigenwerten, insbesondere die kleinsten und größten, regeln. Insbesondere sind zufällige Eigenwerte sehr ähnlich zu geladenen Teilchen und mögen es nicht, nahe beieinander zu sein, daher stoßen sie sich gegenseitig ab (seltsamerweise mit demselben Potentialfeld wie geladene Teilchen, 1/r , wobeir der Abstand zwischen benachbarten Eigenwerten ist). Sie alle zu bitten, positiv zu sein, wäre daher eine sehr große Bitte.

Aufgrund der Universalitätsgesetze in der Zufallsmatrixtheorie vermute ich außerdem, dass die obige Wahrscheinlichkeit pN für im Wesentlichen jede "vernünftige" Zufallsmatrix mit iid-Einträgen, die einen endlichen Mittelwert und eine Standardabweichung aufweisen, wahrscheinlich gleich sein wird.

Alex R.
quelle
5
Es ist schön zu wissen, dass es sehr niedrig ist. Daher werde ich in Zukunft keine Rückweisungsabtastung verwenden, um eine SPD-Matrix zu erstellen.
Haitao Du
5
@ hxd1011: Wenn Sie versuchen, SPD-Matrizen abzutasten, schlage ich die in den obigen Kommentaren beschriebene Methode vor. Darüber hinaus kann es hilfreich sein , zu lesen , auf Cholesky Zersetzungen
Cliff AB
AA2×2