Un semplice algoritmo per la generazione di matrici semidefinite positive

Question

Voglio generare matrici semi-definite casuali positive. Sto cercando un algoritmo o più preferibilmente una semplice implementazione dell'algoritmo in C, matlab, java o in qualsiasi lingua.

Answer 1

1. genera una matrice casuale
2. moltiplicalo per la sua trasposizione
3. hai ottenuto una matrice semi-definita positiva.

Codice di esempio (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

Devi essere chiaro sulla tua definizione di " random " ;. Quali sono i tuoi vincoli sulla matrice risultante? Vuoi che i coefficienti siano distribuiti uniformemente o normalmente? Vuoi che gli autovalori abbiano una distribuzione particolare? (Ecc.)

Esistono diversi modi per generare matrici semidefinite positive M, tra cui:

1. Data una matrice arbitraria A, calcola M = A ^T A (costruendo un Decomposizione cholesky )
2. Data una matrice diagonale arbitraria S con voci diagonali non negative e una matrice ortogonale Q della stessa dimensione, calcola M = QSQ ^T (costruendo un decomposizione del valore singolare )

Per motivi numerici sceglierei probabilmente il secondo approccio generando la matrice diagonale con le proprietà desiderate, quindi generando Q come composizione di un numero di Riflessioni dei nuclei familiari (genera un vettore casuale v, scala alla lunghezza dell'unità, H = I - 2vv ^T ); Ho il sospetto che vorresti usare K * N dove N è la dimensione della matrice M e K è un numero compreso tra 1,5-3 (immagino su questo) che garantisce che abbia abbastanza gradi di libertà.

Puoi anche generare una matrice ortogonale Q usando Rotazioni dei dati : scegli 2 valori distinti da 1 su N e genera una rotazione di Givens attorno a quella coppia di assi, con un angolo uniformemente distribuito da 0 a 2 * pi. Quindi prendi K * N di questi (stesso ragionamento del paragrafo precedente) e la loro composizione produce Q.

modifica: indovino (non sono sicuro) che se si hanno coefficienti generati in modo indipendente e distribuiti normalmente, la matrice nel suo insieme sarebbe " normalmente distribuita < !> quot; (Qualsiasi cosa significhi). È vero almeno per i vettori. (N variabili casuali gaussiane generate in modo indipendente, una per ogni componente, ti danno un vettore casuale gaussiano) Questo non è vero per i componenti distribuiti uniformemente.

Answer 3

Se puoi generare una matrice casuale nella lingua che hai scelto, allora usando la proprietà che una matrice moltiplicata per la sua trasposizione è semi-definita positiva, puoi generare un matix semi-definito positivo casuale

In Matlab sarebbe semplice come

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

Answer 4

Le distribuzioni naturali su matrici semidefinite positive sono Distribuzioni Wishart .

Answer 5

A '* A darà una matrice semidefita positiva iff e solo se A è carente di rango. Quindi le risposte sopra riportate e quelle copiate da Wikipedia non sono generalmente vere. Per calcolare una matrice semidefinita positiva è sufficiente prendere qualsiasi matrice rettangolare m per n (m & Lt; n) e moltiplicarla per la sua trasposizione. Cioè se B è una matrice m per n, con m < n, allora B '* B è una matrice semidefinita. Spero che questo aiuti.

Answer 6

Per chiarire un po '(spero). Sia A una matrice casuale (ad esempio, popolata da variate normali casuali), m x n con m & Gt; = n. Quindi se A è di rango di colonna completo, A'A sarà definito positivo. Se A è di rango & Lt; n allora A'A sarà semidefinito positivo (ma non positivo definito).

Una matrice normale casuale con m > = n sarà quasi sicuramente di rango massimo; per generare una matrice carente al rango si possono aggiungere una o più colonne che sono combinazioni lineari di altre colonne.