Un algorithme simple pour générer des matrices positives semi-finies

Question

Je souhaite générer des matrices semi-définies aléatoires positives. Je recherche un algorithme ou plus préférablement une implémentation simple de l’algorithme en C, matlab, java ou n’importe quel langage.

Answer 1

1. générer une matrice aléatoire
2. multipliez-le par sa propre transposition
3. vous avez obtenu une matrice semi-définie positive.

Exemple de code (Python):

from scipy import random, linalg
matrixSize = 10 
A = random.rand(matrixSize,matrixSize)
B = numpy.dot(A,A.transpose())
print 'random positive semi-define matrix for today is', B

Answer 2

Vous devez préciser votre définition de & "random &". Quelles sont vos contraintes sur la matrice résultante? Voulez-vous que les coefficients soient uniformément ou normalement distribués? Voulez-vous que les valeurs propres aient une distribution particulière? (etc.)

Il existe plusieurs façons de générer des matrices semi-finies positives M, notamment:

1. Étant donné une matrice A arbitraire, calculez M = A ^T A (construction d'un Décomposition de Cholesky )
2. Étant donné une matrice S diagonale arbitraire avec des entrées diagonales non négatives et une matrice Q orthonormée de la même taille, calculez M = QSQ ^T (construction d'un décomposition en valeurs singulières )

Pour des raisons numériques, je choisirais probablement la deuxième approche en générant la matrice diagonale avec les propriétés souhaitées, puis en générant Q comme composition d'un nombre de Réflexions sur les propriétaires (générer un vecteur aléatoire v, de l'échelle à l'unité, H = I - 2vv ^T ); J'imagine que vous voudriez utiliser K * N, où N est la taille de la matrice M et K un nombre compris entre 1,5 et 3 (je suppose que c'est le cas), ce qui garantit qu'il a suffisamment de degrés de liberté.

Vous pouvez également générer une matrice orthonormée Q en utilisant les Rotations de Givens : choisissez 2 valeurs distinctes parmi 1 à N et à générer une rotation de Givens autour de cette paire d’axes, avec un angle uniformément réparti de 0 à 2 * pi. Ensuite, prenons K * N (même raisonnement que le paragraphe précédent) et leur composition donne Q.

modifier: devinerais (incertain) que si vous avez des coefficients générés indépendamment et distribués normalement, la matrice dans son ensemble serait & "normalement distribuée" !> quot; (peu importe ce que cela signifie). C'est vrai pour les vecteurs, au moins. (N variables aléatoires gaussiennes générées indépendamment, une pour chaque composant, vous donnent un vecteur aléatoire gaussien). Cela n’est pas vrai pour les composants uniformément répartis.

Answer 3

Si vous pouvez générer une matrice aléatoire dans la langue de votre choix, alors en utilisant la propriété qu'une matrice multipliée par sa transposée est positive semi-definte, vous pouvez générer un matix semi-défini positif aléatoire

Sous Matlab, ce serait aussi simple que

% Generate a random 3x3 matrix
    A = rand(3,3) 
% Multiply by its tranpose
    PosSemDef = A'*A 

Answer 4

Les distributions naturelles sur les matrices semi-finies positives sont les distributions Wishart .

Answer 5

A '* A donnera une matrice semidéfite positive ssi et seulement si A est déficient en rang. Les réponses ci-dessus et celles de wikipedia ne sont donc généralement pas vraies. Pour calculer une matrice semi-définie positive, il suffit de multiplier une matrice rectangulaire m par n (m & Lt; n) et de la multiplier par sa transposée. C'est à dire. si B est une matrice de m sur n, avec m < n, alors B '* B est une matrice semi-définie. J'espère que cela aide.

Answer 6

Pour clarifier un peu (j'espère). Soit A une matrice aléatoire (par exemple, peuplée de variables normales aléatoires), m x n avec m & Gt; = n. Ensuite, si A est de rang de colonne complet, A'A sera défini comme positif. Si A est de rang & Lt; n alors A'A sera positif semi-défini (mais pas positive définie).

Une matrice normale aléatoire avec m > = n aura presque sûrement le rang complet; Pour générer une matrice avec un rang déficient, vous pouvez ajouter une ou plusieurs colonnes qui sont des combinaisons linéaires d’autres colonnes.