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

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 \times N$

probability matrix random-generation eigenvalues random-matrix Haitao Du
quelle

Versuchen Sie die Simulation ...

kjetil b halvorsen

@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

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

. 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.)

n

$n$

2^{- n}

$2^{-n}$

whuber

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

symmetrisch und positiv mit Wahrscheinlichkeit 1 bestimmt ist.

L

$L$

N

$N$

N = L L^{T}

$N = LL^T$

Cliff AB

Antworten:

Wenn Ihre Matrizen aus normalnormalen iid-Einträgen gezogen werden, ist die Wahrscheinlichkeit, positiv eindeutig zu sein, ungefähr $p_N\approx 3^{-N^2/4}$ , so zum Beispielwenn $N=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 $N^2$ -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, $\propto 1/r$ , wobei $r$ 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 $p_N$ 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

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

@ 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

A^{'} A

$A'A$

2 \times 2

$2 \times 2$