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.Un semplice algoritmo per la generazione di matrici semidefinite positive
risposta
- generare matrice casuale
- moltiplicarlo per essa la propria trasposizione
- 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
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
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:
- Data una matrice arbitraria A, calcolare M = T A (costruire un Cholesky decomposition)
- 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.
Il metodo basato sulla scomposizione di Cholesky funziona solo per le matrici _dense_. Certo, una matrice casuale di Householder sarà in generale anche densa, quindi la stessa cosa potrebbe essere detta per il metodo basato su SVD. – ocramz
Le distribuzioni naturali su matrici semidefinite positive sono Wishart distributions.
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.
Se A ha rank completo, AA 'è ancora semidefinito positivo. Se A ha m righe e n colonne, AA 'ha rank * al massimo * m. –
Beh, la tua affermazione non è vera Alex. Gli eignevalues di A'A sono sempre gli stessi di quelli di AA '. Quindi se A è una matrice quadrata di rango completo, allora sia A'A che AA 'sono entrambi quadrati simmetrici e di rango completo. In parole semplici: se A ha un rank completo, AA 'NON PUO' essere semidefinito. Deve essere positivo-definito. –
Una matrice definita positiva è in particolare positiva semidefinita. –
Sei sicuro? Secondo Wikipedia, è possibile produrre una matrice definita positiva (non semi-definita, ma comunque) moltiplicando una matrice L per la sua trasposizione, dove L è una matrice triangolare inferiore che ha tutti gli elementi diagonali + ve. Questo suggerisce che una matrice casuale non funzionerà in generale. –
Da Wikipedia: "Per qualsiasi matrice A, la matrice A * A è semidefinita positiva," Link: http://en.wikipedia.org/wiki/Positive-definite_matrix#Negative-definite.2C_semidefinite_and_indefinite_matrices – chillysapien
Ah, sei abbastanza giusto, grazie per quel chillysapien. Devo aver interpretato i quantificatori errati. +1. –