Jika saya menghasilkan matriks simetris acak, apa peluangnya pasti positif?

Saya mendapat pertanyaan aneh ketika saya bereksperimen dengan beberapa optimasi cembung. Pertanyaannya adalah:

Misalkan saya secara acak (mengatakan distribusi normal standar) menghasilkan matriks simetris, (misalnya, saya menghasilkan matriks segitiga atas, dan mengisi bagian bawah untuk memastikan itu adalah simetris), apa kesempatan itu adalah matriks definit positif ? Apakah ada cara untuk menghitung probabilitas? $N \times N$

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

Coba simulasi ...

kjetil b halvorsen

@kjetilbhalvorsen terima kasih, tapi saya ingin tahu apa peluang semua nilai eigen lebih besar dari 0. atau bahkan dapatkah kita melakukannya secara analitis.

Haitao Du

n

$n$

2^{- n}

$2^{-n}$

Not an answer to the question asked, but note that if first simulate a matrix

L

$L$ with each entry iid normal and the same dimensions of

N

$N$ , then

N = L L^{T}

$N = LL^T$ is symmetric and positive definite with probability 1.

Cliff AB

Jawaban:

If your matrices are drawn from standard-normal iid entries, the probability of being positive-definite is approximately $p_N\approx 3^{-N^2/4}$ , so for example if $N=5$ , the chance is 1/1000, and goes down quite fast after that. You can find an extended discussion of this question here.

You can somewhat intuit this answer by accepting that the eigenvalue distribution of your matrix will be approximately Wigner semicircle, which is symmetric about zero. If the eigenvalues were all independent, you'd have a $(1/2)^N$ chance of positive-definiteness by this logic. In reality you get $N^2$ behavior, both due to correlations between eigenvalues and the laws governing large deviations of eigenvalues, specifically the smallest and largest. Specifically, random eigenvalues are very much akin to charged particles, and do not like to be close to each other, hence they repel each-other (strangely enough with the same potential field as charged particles, $\propto 1/r$ , where $r$ is the distance between adjacent eigenvalues). Asking them to all be positive would therefore be a very tall request.

Also, because of universality laws in random matrix theory, I strongly suspect the above probability $p_N$ will likely be the same for essentially any "reasonable" random matrix, with iid entries that have finite mean and standard deviation.

Alex R.
sumber

It is nice to know it is very low. So I will not use rejection sampling to create SPD matrix in the future.

Haitao Du

@hxd1011: if you are trying to sample SPD matrices, I suggest the method I desribed in the comments above. In addition, it may be helpful to read up on Cholesky decompositions

Cliff AB

@CliffAB thanks. I usually generate SPD matrix form covariance matrix of some data or from

A^{'} A

$A'A$ similar to what you suggested. I had the time of trying to manually put some numbers to a small matrix say

2 \times 2

$2 \times 2$ and hope it is a PD matrix.

Haitao Du