Un algoritmo simple para generar matrices semidefinidas positivas

Question

Quiero generar matrices semi-definidas aleatorias positivas. Estoy buscando un algoritmo o más preferiblemente una implementación simple del algoritmo en C, matlab, java o cualquier lenguaje.

Answer 1

1. generar matriz aleatoria
2. multiplíquelo por su propia transposición
3. ha obtenido una matriz semi-definida positiva.

Código de ejemplo (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

Debe ser claro en su definición de " random " ;. ¿Cuáles son sus limitaciones en la matriz resultante? ¿Desea que los coeficientes se distribuyan de manera uniforme o normal? ¿Desea que los valores propios tengan una distribución particular? (etc.)

Hay varias formas de generar matrices semidefinidas positivas M, que incluyen:

1. Dada una matriz arbitraria A, calcule M = A ^T A (construyendo un Descomposición de Cholesky )
2. Dada una matriz diagonal arbitraria S con entradas diagonales no negativas, y una matriz ortonormal Q del mismo tamaño, calcule M = QSQ ^T (construyendo a descomposición de valores singulares )

Por razones numéricas, probablemente elegiría el segundo enfoque generando la matriz diagonal con las propiedades deseadas, y luego generando Q como la composición de un número de Reflexiones del jefe de hogar (generar un vector aleatorio v, escala a la longitud de la unidad, H = I - 2vv ^T ); Sospecho que querrías usar K * N donde N es el tamaño de la matriz M, y K es un número entre 1.5-3 (supongo que sobre esto) que asegura que tenga suficientes grados de libertad.

También podría generar una matriz ortonormal Q usando Proporciona rotaciones : seleccione 2 valores distintos de 1 a N y generar una rotación de Givens sobre ese par de ejes, con un ángulo distribuido uniformemente de 0 a 2 * pi. Luego tome K * N de estos (el mismo razonamiento que el párrafo anterior) y su composición produce Q.

editar: adivinaría (no estoy seguro) que si tiene coeficientes que se generan de forma independiente y se distribuyen normalmente, entonces la matriz en su conjunto sería " normalmente distribuida < !> quot; (Lo que sea que eso signifique). Es cierto para los vectores, al menos. (N variables aleatorias gaussianas generadas independientemente, una para cada componente, le dan un vector aleatorio gaussiano) Esto no es cierto para componentes distribuidos uniformemente.

Answer 3

Si puede generar una matriz aleatoria en el idioma elegido, entonces al usar la propiedad de que una matriz multiplicada por su transposición es positiva y definida, puede generar una matriz aleatoria positiva semi-definida

En Matlab sería tan simple como

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

Answer 4

Las distribuciones naturales en matrices semidefinidas positivas son distribuciones Wishart .

Answer 5

A '* A dará una matriz semidefite positiva iff y solo si A es deficiente en rango. Por lo tanto, las respuestas indicadas anteriormente y las copiadas de wikipedia generalmente no son ciertas. Para calcular una matriz semidefinida positiva, simplemente tome cualquier matriz rectangular m por n (m & Lt; n) y multiplíquela por su transposición. Es decir. si B es una matriz m por n, con m < n, entonces B '* B es una matriz semidefinida. Espero que esto ayude.

Answer 6

Para aclarar un poco (espero). Sea A una matriz aleatoria (por ejemplo, poblada por variables normales aleatorias), m x n con m & Gt; = n. Entonces, si A tiene el rango de columna completo, A'A será definitivo positivo. Si A es de rango & Lt; n entonces A'A será positivo semidefinido (pero no positivo definido).

Una matriz normal aleatoria con m > = n seguramente será de rango completo; Para generar una matriz deficiente de rango, se pueden agregar una o más columnas que son combinaciones lineales de otras columnas.