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

32

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×N

Haitao Du
fuente
1
Pruebe la simulación ...
kjetil b halvorsen
1
@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
66
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 2 - n . Para generar una matriz PD, entonces, ¡elige bien tus valores propios! (Para un trabajo rápido, creo matrices como covarianzas de datos normales multivariados).n2n
whuber
11
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 N , entonces N = L L T es simétrica y positiva definida con probabilidad 1.LNN=LLT
Acantilado AB

Respuestas:

41

Si sus matrices se extraen de las entradas iid estándar-normal, la probabilidad de ser definida positiva es de aproximadamente pN3N2/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 N2 , 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, 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 pN will likely be the same for essentially any "reasonable" random matrix, with iid entries that have finite mean and standard deviation.

Alex R.
fuente
5
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
5
@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 AA similar to what you suggested. I had the time of trying to manually put some numbers to a small matrix say 2×2 and hope it is a PD matrix.
Haitao Du