Générer une matrice définie positive symétrique avec un modèle de densité prédéfini

J'essaie de générer une matrice de corrélation (psd symétrique) avec une structure de densité prédéfinie (spécifiée par un graphique sur nœuds). Les nœuds qui sont connectés dans le graphique ont une corrélation , les autres sont tous 0 et la diagonale est 1. $p\times p$ $p$ $\rho \sim U(0,1)$

J'ai essayé de générer cette matrice à plusieurs reprises mais n'obtiens que rarement une matrice de corrélation valide.

Existe-t-il un moyen de garantir une matrice de corrélation whp? Notez que je ne peux avoir qu'une corrélation positive, donc etc. n'est pas une option. $\rho \sim U(-1,1)$

Toute aide est grandement appréciée!

correlation matrix sparse correlation-matrix Blade Runner
la source

Peut-être que la fonction nearPD du package Matrix dans R peut vous aider.

niandra82

Quelle est votre mesure de rareté qui est fixée pour vous? Vos données doivent-elles être binaires ou non négatives en continu?

ttnphns

@ niandra82: nearPD n'est pas bon car il détruira la rareté de la matrice.

Blade Runner

En général, il n'y a pas de distributions matricielles telles que décrites dans cette question. Considérons, par exemple, le cas avec trois coefficients . Si et , alors si et seulement si la matrice est définie positive. Mais alors vous ne pouvez pas avoir à la fois et .

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

Alors pourquoi ne pas générer d'abord la matrice de corrélation. Créez ensuite un index symétrique pour cette matrice où vous forcez les éléments indexés à 0. La rareté serait spécifiée par la taille de l'index et vous pouvez incorporer randommess via une fonction comme sample dans r. Peu importe le nombre d'éléments hors diagonale que vous forcez à 0, le matix sera toujours pd

Zachary Blumenfeld

Réponses:

Fermer mais pas de cigare pour @Rodrigo de Azevedo.

La solution consiste à utiliser une programmation semi-définie pour trouver la valeur maximale, , et la valeur minimale (sous réserve d'être non négative), , de telle sorte que la matrice de corrélation avec le modèle de rareté prescrit soit positive semi-défini (psd). Toutes les valeurs de telles que , produiront des matrices psd (exercice pour le lecteur) $\rho_{max}$ $\rho_{min}$ $\rho$ $\rho$ $\rho_{max}\le \rho \le \rho_{max}$

Par conséquent, vous devez soit choisir une distribution de qui ne peut prendre que des valeurs dans , ou vous devez utiliser l'acceptation / le rejet et rejeter toutes les valeurs générées de qui ne produisent pas une matrice psd. $\rho$ $[\rho_{max},\rho_{max}]$ $\rho$

Exemple pour une matrice 4 x 4 utilisant YALMIP sous 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)

Résultats: rho maximum = 0,57735, rho minimum = 0. Il est évident que zéro sera la valeur minimale de rho sous réserve que rho soit non négatif et que la matrice prescrite soit psd, indépendamment de la dimension ou du modèle de rareté. Par conséquent, il n'est pas nécessaire d'exécuter l'optimisation semi-définie pour trouver la valeur non négative minimale de . $\rho$

Mark L. Stone
la source

Il s'agit d'une interprétation intéressante de la question: elle suppose que tous les coefficients hors diagonale non nuls sont égaux (ce qui simplifie énormément le problème). Il n'est pas clair si c'était l'interprétation voulue, ou si tous les coefficients hors diagonale non nuls sont censés être des réalisations indépendantes d'une distribution commune.

whuber

C'est l'interprétation que j'ai faite. Maintenant que vous le mentionnez, je pouvais voir une interprétation différente possible. Au moins, mon interprétation a le mérite d'entraîner un problème assez bien défini. Je suppose qu'un problème peut être formulé, dont je n'ai pas recherché la solution, pour trouver la valeur maximale de ρ telle que tous les éléments hors diagonale non nuls d'un triangle de la matrice de corrélation puissent être remplis avec des valeurs non négatives pas nécessairement égales ≤ cette valeur, et nécessairement rendre la matrice entièrement peuplée être psd.

Mark L. Stone

$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}$

Si l'on a des contraintes supplémentaires, telles que des contraintes de rareté

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]$

$\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}$

$3 \times 3$

$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

Exécution du 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

Voyons quelle solution CVX a trouvé,

>> X

X =

    1.0000    0.4143         0
    0.4143    1.0000    0.4143
         0    0.4143    1.0000

Cette matrice est-elle semi-définie positive? Définie positive?

>> rank(X)

ans =

     3

>> eigs(X)

ans =

    1.5860
    1.0000
    0.4140

Il est définitivement défini, comme prévu. Nous pouvons trouver des matrices de corrélation semi-définies positives en choisissant une fonction objective non nulle (linéaire).

Rodrigo de Azevedo
la source

Parce que sur ce site, «générer» serait compris comme «tirer d'une distribution aléatoire», pourriez-vous expliquer comment votre code produit des matrices de corrélation aléatoire et indiquer quelle distribution ils suivent?

whuber

@whuber L'OP demande l'impossible. Vous avez commenté cela le 1er janvier 2015. Si vous souhaitez générer des matrices de corrélation aléatoires, générez une matrice carrée aléatoire et utilisez-la dans la fonction objectif du programme semi-défini ci-dessus. Ou, générez des réalisations d'une variable aléatoire qui est uniforme sur le cube mettez-les dans les entrées hors diagonale des matrices (de corrélation) avec sur le diagonale principale, et jetez ceux qui ne sont pas semi-définis positifs. S'il y a des contraintes de non négativité, alors échantillonnez uniformément le cube

[- 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 Voici l' elliptope 3D [png], qui correspond à l'ensemble de matrices de corrélation. Ce que l'OP veut, c'est couper l'elliptope avec l'octant non négatif, puis le couper avec des plans de la forme . Si la matrice est , alors elle doit être à l' intérieur de l'elliptope. En utilisant SDP avec des fonctions d'objectif non nulles, on peut échantillonner la surface de l'elliptope. L'elliptope étant convexe, les combinaisons convexes de points de surface seront également mappées aux matrices de corrélation.

3 \times 3

$3 \times 3$

x_{i j} = 0

$x_{ij} = 0$

≻ 0

$\succ 0$

Rodrigo de Azevedo

C'est une excellente façon de décrire la situation.

whuber

Vous avez raison sur la façon dont les volumes relatifs diminuent. C'est précisément pourquoi c'est un problème difficile.

whuber