Um algoritmo simples para a geração de matrizes positivas-semidefinite

Question

Eu quero gerar matrizes semi-definidas aleatórias positivas. Eu estou procurando um algoritmo ou mais preferivelmente uma simples implementação do algoritmo em C, Matlab, Java ou qualquer idioma.

Answer 1

1. gerar matriz aleatória
2. multiplicá-lo por si própria transposição
3. você tiver obtido uma matriz semi-definida positiva.

código Exemplo (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

Você precisa ser claro sobre a sua definição de "random". Quais são as suas restrições sobre a matriz resultante? Quer os coeficientes a serem uniformemente ou normalmente distribuídos? Você quer que os valores próprios de ter uma distribuição particular? (Etc.)

Há uma série de maneiras de gerar positiva matrizes semidefinite M, incluindo:

1. Dada uma matriz arbitrária A, computação M = A ^T A (construção de uma Cholesky decomposição )
2. Dado um arbitrária matriz diagonal S com n negativo diagonal entradas, e uma matriz Q ortonormal do mesmo tamanho, de computação M = QSQ ^T (construção de um singular valor decomposição )

Por razões numéricas eu provavelmente escolher a segunda abordagem por gerar a matriz diagonal com propriedades desejadas, em seguida, gerando Q como a composição de um número de Householder reflexões (v gerar um vector aleatório, escala de comprimento unitário, H = I - 2vv ^T ); Eu suspeito que você gostaria de usar K * N, onde N é o tamanho da matriz M, e K é um número entre 1,5-3 (estou adivinhando sobre isso) que garante que ele tem graus de liberdade suficientes.

É também poderia gerar uma matriz Q ortonormal usando Givens rotações : 2 escolher valores distintos de 1 para N e gerar uma rotao de Givens sobre o par de eixos, com um ângulo uniformemente distribuído entre 0 e 2 * pi. Em seguida, tomar K * N destes (o mesmo raciocínio como parágrafo acima) e a sua composição origina Q.

edit: eu acho (não tenho certeza) que se você tem coeficientes que são independentemente gerados e distribuídos normalmente, então a matriz como um todo seria "distribuída normalmente" (whatever that means ). É verdade para vetores, pelo menos. (N-gerado independentemente variáveis ??aleatórias gaussianas, um para cada componente, dá-lhe um vector aleatória gaussiana) Isto não é verdadeiro para os componentes uniformemente distribuídos.

Answer 3

Se você pode gerar uma matriz aleatória em seu idioma escolhido, em seguida, usando a propriedade que uma matriz multiplicada pela sua transposta é positiva semi-definte, você pode gerar um aleatória positiva semi-definida matix

Em Matlab seria tão simples como

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

Answer 4

distribuições naturais sobre matrizes semidefinite positivos são Wishart distribuições .

Answer 5

A '* Um vai dar uma sse matriz semidefite positiva e só se A é rank-deficiente. Assim, as respostas acima mencionados e que copiado da Wikipédia não são geralmente verdade. Para calcular uma matriz semidefinido positivo simplesmente tomar qualquer m rectangular por matriz n (m

Answer 6

Para esclarecer um pouco (eu espero). Seja A uma matriz aleatória (por exemplo, preenchido por variates normais aleatórios), m x n com m> = n. Então, se A é de classificação coluna completa, A'A será definida positiva. Se A é de classificação

Uma matriz aleatória normal com m> = n vai quase certamente ser posto completo; para gerar uma matriz de um posto deficiente pode acrescentar uma ou mais colunas que são combinações lineares de outras colunas.