Generar matriz definida positiva simétrica con un patrón de dispersión preespecificado

Estoy tratando de generar una matriz de correlación (psd simétrica) con una estructura de dispersión preespecificada (especificada por un gráfico en nodos). Los nodos que están conectados en el gráfico tienen correlación , el resto todos son 0 y la diagonal es 1. $p\times p$ $p$ $\rho \sim U(0,1)$

He intentado generar esta matriz varias veces, pero solo rara vez obtengo una matriz de correlación válida.

¿Hay alguna manera de asegurar una matriz de correlación whp? Tenga en cuenta que solo puedo tener una correlación positiva, por lo que etc., no es una opción. $\rho \sim U(-1,1)$

¡Cualquier ayuda es muy apreciada!

correlation matrix sparse correlation-matrix Cazarecompensas
fuente

Tal vez la función nearPD del paquete Matrix en R pueda ayudar.

niandra82

¿Cuál es su medida de escasez que es fija para usted? ¿Deben sus datos ser binarios o continuos no negativos?

ttnphns 01 de

@ niandra82: nearPD no es bueno ya que destruirá la escasez de la matriz.

Blade Runner el

En general, no existen distribuciones matriciales como las descritas en esta pregunta. Considere, por ejemplo, el caso con tres coeficientes . Si y , entonces si y solo si la matriz es positiva definida. Pero entonces no puede tener tanto como .

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

Entonces, ¿por qué no generar primero la matriz de correlación? Luego, cree un índice simétrico para esa matriz donde fuerce los elementos indexados a 0. La amplitud se especificará por el tamaño del índice y puede incorporar al azar a través de una función como muestra en r. No importa cuántos elementos fuera de la diagonal forces a 0, el matix seguirá siendo pd

Zachary Blumenfeld

Respuestas:

Cerca pero sin cigarros para @Rodrigo de Azevedo.

La solución es utilizar la programación semidefinida para encontrar el valor máximo, , y el valor mínimo (sujeto a no ser negativo), , de modo que la matriz de correlación con el patrón de dispersión prescrito sea positivo semidefinito (psd). Todos los valores de tales que , producirán matrices psd (ejercicio para el lector) $\rho_{max}$ $\rho_{min}$ $\rho$ $\rho$ $\rho_{max}\le \rho \le \rho_{max}$

Por lo tanto, debe elegir una distribución de que solo puede tomar valores en , o debe usar la aceptación / rechazo y rechazar cualquier valor generado de que no produzca Una matriz psd. $\rho$ $[\rho_{max},\rho_{max}]$ $\rho$

Ejemplo para una matriz de 4 por 4 usando YALMIP bajo 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. Es evidente que cero será el valor mínimo de rho sujeto a que rho no sea negativo y la matriz prescrita sea psd, independientemente de la dimensión o el patrón de dispersión. Por lo tanto, no es necesario ejecutar la optimización semidefinida para encontrar el valor mínimo no negativo de . $\rho$

Mark L. Stone
fuente

Esta es una interpretación interesante de la pregunta: se supone que todos los coeficientes no diagonales distintos de cero son iguales (lo que simplifica enormemente el problema). No está claro si esa fue la interpretación prevista, o si se supone que todos los coeficientes fuera de diagonal no nulos son realizaciones independientes de una distribución común.

whuber

Esa es la interpretación que hice. Ahora que lo mencionas, pude ver que una interpretación diferente es posible. Al menos mi interpretación tiene la virtud de resultar en un problema bastante bien definido. Supongo que se puede formular un problema, cuya solución no he investigado, para encontrar el valor máximo de ρ de manera que todos los elementos no diagonales fuera de cero de un triángulo de la matriz de correlación puedan rellenarse con valores no negativos no necesariamente iguales ≤ ese valor, y necesariamente hacen que la matriz completamente poblada sea psd.

Mark L. Stone

Una matriz de correlación es simétrica, semidefinida positiva y tiene en su diagonal principal. Se puede encontrar una matriz de correlación resolviendo el siguiente programa semidefinido (SDP) donde la función objetivo es arbitraria, digamos, la función cero $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 uno tiene restricciones adicionales, como restricciones de dispersión

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

y restricciones de no negatividad, , luego se resuelve el siguiente 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}$

Un ejemplo de $3 \times 3$

Supongamos que queremos tener y . Aquí hay un 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

Ejecutando el 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

Veamos qué solución encontró CVX,

>> X

X =

    1.0000    0.4143         0
    0.4143    1.0000    0.4143
         0    0.4143    1.0000

¿Es esta matriz positiva semidefinida? ¿Positivo definitivo?

>> rank(X)

ans =

     3

>> eigs(X)

ans =

    1.5860
    1.0000
    0.4140

Es positivo definitivo, como se esperaba. Podemos encontrar matrices de correlación semidefinidas positivas eligiendo una función objetivo distinta de cero (lineal).

Rodrigo de Azevedo
fuente

Dado que en este sitio se entendería que "generar" significa "extraer de una distribución aleatoria", ¿podría explicar cómo su código produce matrices de correlación aleatorias e indicar qué distribución siguen?

whuber

@whuber El OP está pidiendo lo imposible. Comentó sobre eso el 1 de enero de 2015. Si desea generar matrices de correlación aleatorias, genere una matriz cuadrada aleatoria y úsela en la función objetivo en el programa semidefinido anterior. O bien, genere realizaciones de una variable aleatoria que sea uniforme sobre el cubo colóquelas en las entradas fuera de la diagonal de las matrices (de correlación) con 's en el diagonal principal, y descarte las que no sean semidefinidas positivas. Si hay restricciones de no negatividad, muestree uniformemente el 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 Aquí está el elliptope 3D [png], que se asigna al conjunto de matrices de correlación . Lo que quiere el OP es intersectar el eliptograma con el octante no negativo, luego intersecarlo con planos de la forma . Si la matriz es , entonces debe estar en el interior del eliptograma. Usando SDP con funciones objetivas distintas de cero, se puede muestrear la superficie del eliptograma. Como el eliptograma es convexo, las combinaciones convexas de puntos de superficie también se asignarán a matrices de correlación.

3 \times 3

$3 \times 3$

x_{i j} = 0

$x_{ij} = 0$

≻ 0

$\succ 0$

Rodrigo de Azevedo

Esa es una excelente manera de describir la situación.

whuber

Tiene razón acerca de cómo se reducen los volúmenes relativos. Esa es precisamente la razón por la cual este es un problema difícil.

whuber