Si je génère une matrice symétrique aléatoire, quelle est la chance qu'elle soit positive définie?

32

J'ai eu une question étrange lorsque je testais des optimisations convexes. La question est:

Supposons que je génère aléatoirement (par exemple, une distribution normale standard) une matrice symétrique ((par exemple, je génère une matrice triangulaire supérieure et je remplis la moitié inférieure pour s'assurer qu'elle est symétrique), quelle est la probabilité qu'il s'agisse d'une définition positive matrice? Est-il possible de calculer la probabilité?N×N

probability matrix random-generation eigenvalues random-matrix Haitao Du
la source
1
Essayez la simulation ...
kjetil b halvorsen
1
@kjetilbhalvorsen merci, mais je me demande quelle est la probabilité que toutes les valeurs propres soient supérieures à 0. ou pouvons-nous même le faire de manière analytique.
Haitao Du
6
La réponse dépend de la façon dont vous générez la matrice. Par exemple, une méthode génère valeurs propres réelles en fonction de la distribution, puis conjugue cette matrice diagonale à une matrice orthogonale aléatoire. Le résultat sera positif défini si et seulement si toutes ces valeurs propres sont positives. Si vous deviez générer des valeurs propres indépendamment selon une distribution symétrique autour de zéro , alors cette probabilité est évidemment d'au plus . Pour générer une matrice de PD, choisissez bien vos valeurs propres! (Pour un travail rapide, je crée des matrices telles que les covariances de données normales multivariées.)n2−n
whuber
11
Pas une réponse à la question posée, mais notez que si simulons d'abord une matrice avec chaque entrée iid normale et les mêmes dimensions de , alors est symétrique et défini avec la probabilité 1.N N = L L TLNN=LLT
Cliff AB

Réponses:

41

Si vos matrices sont tirées d’entrées iid normales normales, la probabilité d’être positive-définie est d’environ , ainsi, par exemple, si , la probabilité est de 1/1000, et descend assez vite par la suite. Vous pouvez trouver une discussion prolongée de cette question ici .pN≈3−N2/4N=5

Vous pouvez comprendre cette réponse en acceptant que la distribution des valeurs propres de votre matrice sera approximativement du demi - cercle de Wigner , ce qui est symétrique par rapport à zéro. Si les valeurs propres étaient toutes indépendantes, vous auriez une chance de définition positive par cette logique. En réalité, vous obtenez un comportement , tous deux dus à des corrélations entre les valeurs propres et les lois régissant les grands écarts des valeurs propres, en particulier les plus petites et les plus grandes. Plus précisément, les valeurs propres aléatoires s'apparentent beaucoup à des particules chargées et n'aiment pas être proches les unes des autres. Elles se repoussent donc (étrangement avec le même champ potentiel que les particules chargées, , où(1/2)NN2∝1/rrest la distance entre les valeurs propres adjacentes). Leur demander d'être tous positifs serait donc une très grande demande.

De plus, en raison des lois d'universalité dans la théorie des matrices aléatoires, je soupçonne fortement que la probabilité ci-dessus, sera probablement la même pour pratiquement toute matrice aléatoire "raisonnable", avec des entrées iid ayant une moyenne finie et un écart-type.pN

Alex R.
la source
5
C'est bien de savoir que c'est très bas. Je n’utiliserai donc pas d’échantillonnage de rejet pour créer une matrice SPD à l’avenir.
Haitao Du
5
@ hxd1011: si vous essayez d'échantillonner des matrices SPD, je suggère la méthode que j'ai décrite dans les commentaires ci-dessus. En outre, il peut être utile de prendre connaissance des décompositions de Cholesky
Cliff AB
@ CliffAB merci. Je génère habituellement une matrice de covariance sous forme de matrice SPD à partir de certaines données ou de semblable à ce que vous avez suggéré. J'ai eu le temps d'essayer de mettre manuellement des nombres dans une petite matrice, par exemple , en espérant qu'il s'agisse d'une matrice de PD. 2 × 2A′A2×2
Haitao Du