Gerar matriz definida positiva simétrica com um padrão de esparsidade pré-especificado

Eu estou tentando gerar uma matriz de correlação (psd simétrico) com uma estrutura de esparsidade pré-especificada (especificada por um gráfico nos nós ). Os nós conectados no gráfico têm correlação , resto todos são 0 e a diagonal é tudo 1. $p\times p$ $p$ $\rho \sim U(0,1)$

Eu tentei gerar essa matriz várias vezes, mas apenas raramente obtive uma matriz de correlação válida.

Existe uma maneira de garantir uma matriz de correlação whp? Note que eu só posso ter correlação positiva, então etc. não é uma opção. $\rho \sim U(-1,1)$

Qualquer ajuda é muito apreciada!

correlation matrix sparse correlation-matrix Blade Runner
fonte

Talvez a função nearPD do pacote Matrix em R possa ajudar.

Niandra82

Qual é a sua medida de escarsidade que é corrigida para você? Seus dados devem ser contínuos binários ou não negativos?

precisa saber é o seguinte

@ niandra82: nearPD não é bom, pois destruirá a esparsidade da matriz.

Blade Runner

Em geral, não existem distribuições matriciais como descritas nesta pergunta. Considere, por exemplo, o caso com três coeficientes . Se e , então se e somente se a matriz for positiva definida. Mas então você não pode ter ambos e .

3 \times 3

$3\times 3$

ρ, σ, τ

$\rho,\sigma,\tau$

τ = 0

$\tau=0$

ρ > 0, σ > 0

$\rho\gt 0, \sigma\gt 0$

ρ^{2} + σ^{2} < 1

$\rho^2+\sigma^2\lt 1$

ρ \sim U (0, 1)

$\rho\sim U(0,1)$

σ \sim U (0, 1)

$\sigma\sim U(0,1)$

whuber

Então por que não gerar a matriz de correlação primeiro. Em seguida, crie um índice simétrico para essa matriz em que você força os elementos indexados a 0. A escassez seria especificada pelo tamanho do índice e você poderá incorporar a aleatória através de uma função como amostra em r. Não importa quantas off elementos diagonais você forçar a 0, o matix ainda será pd

Zachary Blumenfeld

Respostas:

Perto, mas nenhum charuto para @Rodrigo de Azevedo.

A solução é usar a programação semidefinida para encontrar o valor máximo, , e o valor mínimo (sujeito a não-negativo), , de modo que a matriz de correlação com o padrão de esparsidade prescrito seja positiva semidefinido (psd). Todos os valores de tais que produzirão matrizes psd (exercício para o leitor) $\rho_{max}$ $\rho_{min}$ $\rho$ $\rho$ $\rho_{max}\le \rho \le \rho_{max}$

Portanto, você deve escolher uma distribuição de que só pode receber valores em ou deve usar aceitação / rejeição e rejeitar quaisquer valores gerados de que não produzam uma matriz psd. $\rho$ $[\rho_{max},\rho_{max}]$ $\rho$

Exemplo para uma matriz 4 por 4 usando YALMIP em MATLAB

sdpvar rho % declare rho to be a scalar variable
% find maximum value of rho (by minimizing -rho) subject to prescribed matrix being psd.
optimize([1 0 rho 0;0 1 rho 0;rho rho 1 rho;0 0 rho 1] >= 0,-rho) 
% find minimum value of rho subject to prescribed matrix being psd and rho being >= 0.
optimize([[1 0 rho 0;0 1 rho 0;rho rho 1 rho;0 0 rho 1] >= 0,rho >= 0],rho)

Resultados: rho máximo = 0,57735, rho mínimo = 0. É prontamente aparente que zero será o valor mínimo de rho sujeito a rho não ser negativo e a matriz prescrita ser psd, independentemente da dimensão ou padrão de escarsidade. Portanto, não é necessário executar a otimização semidefinida para encontrar o valor mínimo não negativo de . $\rho$

Mark L. Stone
fonte

Esta é uma interpretação interessante da questão: assume que todos os coeficientes fora da diagonal diferentes de zero são iguais (simplificando tremendamente o problema). Não está claro se essa foi a interpretação pretendida ou se todos os coeficientes fora da diagonal diferentes de zero devem ser realizações independentes de uma distribuição comum.

whuber

Essa é a interpretação que fiz. Agora que você mencionou, pude ver uma interpretação diferente sendo possível. Pelo menos minha interpretação tem a virtude de resultar em um problema bastante bem definido. Suponho que um problema possa ser formulado, cuja solução eu não pesquisei, para encontrar o valor máximo de ρ de modo que todos os elementos fora da diagonal diferentes de zero de um triângulo da matriz de correlação possam ser preenchidos com valores não negativos não necessariamente iguais. esse valor e necessariamente faça a matriz totalmente preenchida ser psd.

Mark L. Stone

Uma matriz de correlação é simétrica, semidefinida positiva e possui na diagonal principal. Pode-se encontrar uma matriz de correlação resolvendo o seguinte programa semidefinido (SDP) em que a função objetivo é arbitrária, por exemplo, a função zero $1$ $n \times n$

\begin{array}{ll} minimize & ⟨ O_{n}, X ⟩ \\ subject to & x_{11} = x_{22} = \dots = x_{n n} = 1 \\ X ⪰ O_{n} \end{array}

$\begin{array}{ll} \text{minimize} & \mathrm \langle \mathrm O_n, \mathrm X \rangle\\ \text{subject to} & x_{11} = x_{22} = \cdots = x_{nn} = 1\\ & \mathrm X \succeq \mathrm O_n\end{array}$

Se houver restrições adicionais, como restrições de esparsidade

x_{i j} = 0 for all (i, j) \in Z \subset [n] \times [n]

$x_{ij} = 0 \text{ for all } (i,j) \in \mathcal Z \subset [n] \times [n]$

e restrições de não negatividade, , em seguida, um resolve o seguinte SDP $\mathrm X \geq \mathrm O_n$

\begin{array}{ll} minimize & ⟨ O_{n}, X ⟩ \\ subject to & x_{11} = x_{22} = \dots = x_{n n} = 1 \\ x_{i j} = 0 for all (i, j) \in Z \subset [n] \times [n] \\ X \geq O_{n} \\ X ⪰ O_{n} \end{array}

$\begin{array}{ll} \text{minimize} & \mathrm \langle \mathrm O_n, \mathrm X \rangle\\ \text{subject to} & x_{11} = x_{22} = \cdots = x_{nn} = 1\\ & x_{ij} = 0 \text{ for all } (i,j) \in \mathcal Z \subset [n] \times [n]\\ & \mathrm X \geq \mathrm O_n\\ & \mathrm X \succeq \mathrm O_n\end{array}$

A exemplo $3 \times 3$

Suponha que queremos ter e . Aqui está um script MATLAB + CVX , $x_{13} = 0$ $x_{12}, x_{23} \geq 0$

cvx_begin sdp

    variable X(3,3) symmetric

    minimize( trace(zeros(3,3)*X) )
    subject to

        % put ones on the main diagonal
        X(1,1)==1
        X(2,2)==1
        X(3,3)==1

        % put a zero in the northeast and southwest corners
        X(1,3)==0

        % impose nonnegativity
        X(1,2)>=0
        X(2,3)>=0

        % impose positive semidefiniteness
        X >= 0

cvx_end

Executando o script,

Calling sedumi: 8 variables, 6 equality constraints
------------------------------------------------------------
SeDuMi 1.21 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
eqs m = 6, order n = 6, dim = 12, blocks = 2
nnz(A) = 8 + 0, nnz(ADA) = 36, nnz(L) = 21
 it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
  0 :            3.00E+000 0.000
  1 : -1.18E-001 6.45E-001 0.000 0.2150 0.9000 0.9000   1.86  1  1  1.2E+000
  2 : -6.89E-004 2.25E-002 0.000 0.0349 0.9900 0.9900   1.52  1  1  3.5E-001
  3 : -6.48E-009 9.72E-007 0.097 0.0000 1.0000 1.0000   1.01  1  1  3.8E-006
  4 : -3.05E-010 2.15E-009 0.000 0.0022 0.9990 0.9990   1.00  1  1  1.5E-007
  5 : -2.93E-016 5.06E-015 0.000 0.0000 1.0000 1.0000   1.00  1  1  3.2E-013

iter seconds digits       c*x               b*y
  5      0.3   5.8  0.0000000000e+000 -2.9302886987e-016
|Ax-b| =  1.7e-015, [Ay-c]_+ =  6.1E-016, |x|= 2.0e+000, |y|= 1.5e-015

Detailed timing (sec)
   Pre          IPM          Post
1.563E-001    2.500E-001    1.094E-001    
Max-norms: ||b||=1, ||c|| = 0,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 1.
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0

Vamos ver qual solução CVX encontrou,

>> X

X =

    1.0000    0.4143         0
    0.4143    1.0000    0.4143
         0    0.4143    1.0000

Essa matriz é positiva semidefinida? Positivo definitivo?

>> rank(X)

ans =

     3

>> eigs(X)

ans =

    1.5860
    1.0000
    0.4140

É definitivo positivo, como esperado. Podemos encontrar matrizes de correlação semidefinidas positivas escolhendo uma função objetiva diferente de zero (linear).

Rodrigo de Azevedo
fonte

Como neste site "gerar" seria entendido como "desenhar a partir de uma distribuição aleatória", você poderia explicar como seu código produz matrizes de correlação aleatória e indicar qual distribuição elas seguem?

whuber

@whuber O OP está pedindo o impossível. Você comentou isso em 1 de janeiro de 2015. Se você deseja gerar matrizes de correlação aleatórias, gere uma matriz quadrada aleatória e use-a na função objetivo no programa semidefinido acima. Ou gere realizações de uma variável aleatória que seja uniforme sobre o cubo coloque-as nas entradas fora da diagonal das matrizes (de correlação) com no diagonal principal e descartar as que não são positivas semidefinidas. Se houver restrições de não-negatividade, faça uma amostragem uniforme do cubo

[- 1, 1]^{(\binom{n}{2})}

$[-1,1]^{\binom{n}{2}}$

1

$1$

[0, 1]^{(\binom{n}{2})}

$[0,1]^{\binom{n}{2}}$

Rodrigo de Azevedo

@whuber Aqui está o elíptico 3D [png], que é mapeado para o conjunto de matrizes de correlação. O que o OP deseja é interceptar o elíptico com o octante não negativo e, em seguida, interceptá-lo com planos da forma . Se a matriz for , ela deverá estar no interior do elipse. Usando o SDP com funções objetivas diferentes de zero, pode-se amostrar a superfície do elíptico. Como o elíptico é convexo, combinações convexas de pontos de superfície também serão mapeadas para matrizes de correlação.

3 \times 3

$3 \times 3$

x_{i j} = 0

$x_{ij} = 0$

≻ 0

$\succ 0$

Rodrigo de Azevedo

Essa é uma excelente maneira de descrever a situação.

whuber

Você está correto sobre como os volumes relativos diminuem. É exatamente por isso que este é um problema difícil.

whuber