Un semplice algoritmo per la generazione di matrici semidefinite positive

Question

Desidero 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. generare matrice casuale
2. moltiplicarlo per essa la propria trasposizione
3. aver ottenuto una matrice semi-definita positiva.

Esempio di codice (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

Se è possibile generare una matrice casuale nella tua lingua, quindi utilizzando la proprietà che una matrice moltiplicata per la sua trasposizione è positiva semi-definte, è in grado di generare un matix casuale positiva semi-definita

In Matlab sarebbe semplice come

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

Answer 3

Hai bisogno di essere chiaro sulla tua definizione di "casuale". 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)

Ci sono un certo numero di modi per generare positiva semidefinita matrici M, tra cui:

1. Data una matrice arbitraria A, calcolare M = ^T A (costruire un Cholesky decomposition)
2. Dato un arbitrario matrice diagonale S con elementi diagonali non negativi, e una matrice ortonormale Q delle stesse dimensioni, calcolare M = QSQ ^T (costruendo un singular value decomposition)

Per ragioni numeriche probabilmente sceglierei il secondo approccio generando la matrice diagonale con le proprietà desiderate, quindi generando Q come la composizione di un numero di Householder reflections (genera un vettore casuale v, scala in unità di lunghezza, H = I - 2vv ^T); Sospetto che tu voglia usare K * N dove N è la dimensione della matrice M, e K è un numero compreso tra 1.5-3 (sto indovinando su questo) che assicura che abbia abbastanza gradi di libertà.

È anche possibile generare una matrice ortonormale Q utilizzando Givens rotations: selezionare 2 valori distinti da 1 a N e generare una rotazione Givens su quella coppia di assi, con un angolo uniformemente distribuito da 0 a 2 * pi. Poi prendere K * N di questi (stesso ragionamento precedente paragrafo) e la loro composizione produce D.

edit: avevo immagino (non sono sicuro) che, se si dispone di coefficienti che sono indipendentemente-generati e normalmente distribuiti, allora la matrice nel suo insieme sarebbe "normalmente distribuita" (qualunque cosa significhi). È vero per i vettori, almeno. (N variabili casuali gaussiane generate in modo indipendente, una per ciascun componente, fornisce un vettore casuale gaussiano) Questo non è vero per i componenti distribuiti uniformemente.

Answer 4

Le distribuzioni naturali su matrici semidefinite positive sono Wishart distributions.

Answer 5

A '* A darà una matrice di semidefite positiva iff e solo se A è di rango carente.Quindi le risposte di cui sopra e quelle copiate da wikipedia non sono generalmente vere. Per calcolare una matrice semidefinita positiva, basta prendere qualsiasi matrice m per matrice n (m < n) e moltiplicarla per la sua trasposizione. Cioè se B è una matrice per matrice, con m < n, allora B '* B è una matrice semidefinita. Spero che aiuti.