Si genero una matriz simétrica aleatoria, ¿cuál es la probabilidad de que sea positiva definida?

Recibí una pregunta extraña cuando estaba experimentando algunas optimizaciones convexas. La pregunta es:

Supongamos que genero aleatoriamente (digamos distribución normal estándar) una matriz simétrica (por ejemplo, genero una matriz triangular superior y lleno la mitad inferior para asegurarme de que sea simétrica), ¿cuál es la probabilidad de que sea un definitivo positivo? ¿matriz? ¿Hay alguna forma de calcular la probabilidad? $N \times N$

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

Pruebe la simulación ...

kjetil b halvorsen

@kjetilbhalvorsen gracias, pero me pregunto cuál es la posibilidad de que todos los valores propios sean mayores que 0. o incluso podemos hacerlo analíticamente.

Haitao Du

La respuesta depende de cómo generes la matriz. Por ejemplo, una forma genera

valores propios reales de acuerdo con alguna distribución y luego conjuga esa matriz diagonal por una matriz ortogonal aleatoria. El resultado será positivo definitivo si y solo si todos esos valores propios son positivos. Si tuviera que generar valores propios de forma independiente de acuerdo con una distribución simétrica sobre cero , entonces esa probabilidad obviamente es como máximo

. Para generar una matriz PD, entonces, ¡elige bien tus valores propios! (Para un trabajo rápido, creo matrices como covarianzas de datos normales multivariados).

n

$n$

2^{- n}

$2^{-n}$

whuber

No es una respuesta a la pregunta formulada, pero tenga en cuenta que si primero simula una matriz

con cada entrada en normal y las mismas dimensiones de

, entonces

es simétrica y positiva definida con probabilidad 1.

L

$L$

N

$N$

N = L L^{T}

$N = LL^T$

Acantilado AB

Respuestas:

Si sus matrices se extraen de las entradas iid estándar-normal, la probabilidad de ser definida positiva es de aproximadamente $p_N\approx 3^{-N^2/4}$ , así que por ejemplo, si $N=5$ , la oportunidad es 1/1000, y baja bastante rápido después de eso. Puede encontrar una discusión extendida de esta pregunta aquí .

Puede intuir algo esta respuesta al aceptar que la distribución del valor propio de su matriz será aproximadamente el semicírculo de Wigner , que es simétrico respecto a cero. Si los valores propios son todos independientes, que tendría una $(1/2)^N$ posibilidad de positivos-definitud por esta lógica. En realidad, obtienes un comportamiento $N^2$ , tanto debido a las correlaciones entre los valores propios y las leyes que rigen las grandes desviaciones de los valores propios, específicamente el más pequeño y el más grande. Específicamente, los valores propios aleatorios son muy parecidos a las partículas cargadas, y no les gusta estar cerca el uno del otro, por lo tanto, se repelen entre sí (curiosamente con el mismo campo potencial que las partículas cargadas, $\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.
fuente

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