Se eu gerar uma matriz simétrica aleatória, qual é a chance de ela ser definitiva positiva?

Eu tive uma pergunta estranha quando estava experimentando algumas otimizações convexas. A questão é:

Suponha que eu aleatoriamente (digamos distribuição normal padrão) gere uma matriz simétrica (por exemplo, eu gere matriz triangular superior e preencha a metade inferior para garantir que seja simétrica), qual é a chance de ser uma definição definitiva positiva matriz? Existe alguma maneira de calcular a probabilidade? $N \times N$

probability matrix random-generation eigenvalues random-matrix Haitao Du
fonte

Tente simulação ...

kjetil b halvorsen

@kjetilbhalvorsen obrigado, mas estou me perguntando qual é a chance de todos os autovalores serem maiores que 0. ou podemos, possivelmente, fazê-lo analiticamente.

Haitao Du

A resposta depende de como você gera a matriz. Por exemplo, uma maneira gera autovalores reais de acordo com alguma distribuição e depois conjuga essa matriz diagonal por uma matriz ortogonal aleatória. O resultado será positivo definitivo se e somente se todos esses autovalores forem positivos. Se você gerasse valores próprios independentemente, de acordo com uma distribuição simétrica em torno de zero , essa chance obviamente é no máximo

. Para gerar uma matriz PD, escolha bem seus valores próprios! (Para um trabalho rápido, eu criar tais matrizes como covariâncias de dados normal multivariada.)

n

$n$

2^{- n}

$2^{-n}$

whuber

Não é uma resposta para a pergunta, mas observe que se primeiro simular uma matriz

com cada entrada iid normal e as mesmas dimensões de

, então

é simétrica e positiva definida com probabilidade 1.

L

$L$

N

$N$

N = L L^{T}

$N = LL^T$

Cliff AB

Respostas:

Se as matrizes são desenhados a partir das entradas iid padrão normal, a probabilidade de ser definida positiva é de aproximadamente $p_N\approx 3^{-N^2/4}$ , por exemplo, se $N=5$ , a possibilidade é 1/1000, e desce bastante rápido depois disso. Você pode encontrar uma discussão extensa sobre esta questão aqui .

Você pode, de alguma maneira, intuir essa resposta aceitando que a distribuição de autovalor da sua matriz será aproximadamente semicírculo de Wigner , que é simétrico em relação a zero. Se os valores próprios estavam todos independentes, você teria um $(1/2)^N$ chance de positivo-definiteness por essa lógica. Na realidade, você obtém o comportamento de $N^2$ , devido a correlações entre valores próprios e as leis que regem grandes desvios de valores próprios, especificamente o menor e o maior. Especificamente, autovalores aleatórios são muito parecidos com partículas carregadas e não gostam de estar próximos um do outro, portanto, eles se repelem (estranhamente, com o mesmo campo potencial das partículas carregadas, $\propto 1/r$ , em que $r$ é a distância entre valores próprios adjacentes). Pedir a todos que sejam positivos seria, portanto, um pedido muito alto.

Além disso, por causa das leis de universalidade em teoria matriz aleatória, suspeito fortemente a probabilidade de cima $p_N$ , provavelmente, ser o mesmo para essencialmente qualquer matriz aleatória "razoável", com entradas iid que têm média e desvio padrão finito.

Alex R.
fonte

É bom saber que é muito baixo. Portanto, não usarei amostragem de rejeição para criar matriz SPD no futuro.

Haitao Du

@ hxd1011: se você estiver tentando amostrar matrizes SPD, sugiro o método descrito nos comentários acima. Além disso, pode ser útil ler sobre as decomposições de Cholesky

Cliff AB

A^{'} A

$A'A$

2 \times 2

$2 \times 2$