Muestreo de gaussiana multivariante con covarianza laplaciana (inversa) gráfica

Sabemos, por ejemplo, por Koutis-Miller-Peng (basado en el trabajo de Spielman y Teng), que podemos resolver muy rápidamente los sistemas lineales $A x = b$ para las matrices $A$ que son la matriz de Laplacia de gráficos para algunos gráficos dispersos con pesos de borde no negativos .

Ahora (primera pregunta) considere utilizar una de estas matrices laplacianas gráfico $A$ como la matriz de covarianza o (segunda pregunta) de covarianza inversa de una distribución normal multivariada media cero $\mathcal{N}(\boldsymbol{0}, A)$ o $\mathcal{N}(\boldsymbol{0}, A^{-1})$ . Para cada uno de estos casos, tengo dos preguntas:

A. ¿Qué tan eficientemente podemos extraer una muestra de esta distribución? (Por lo general, para dibujar una muestra, calculamos la descomposición de Cholesky $A = LL^T$ , dibujamos una normal normal $y \sim \mathcal{N}(\boldsymbol{0}, I)$ , luego calculamos una muestra como $x = L^{-1} y$ ).

B. ¿Cuán eficientemente podemos calcular el determinante de $A$ ?

Tenga en cuenta que ambos podrían resolverse fácilmente dada una descomposición de Cholesky, pero no veo de inmediato cómo extraer $L$ más eficiente que simplemente usando un algoritmo de Cholesky disperso estándar, que no usaría las técnicas presentadas en las referencias anteriores funciona, y que tendría una complejidad cúbica para gráficos de ancho de árbol escaso pero alto.

ds.algorithms graph-theory linear-algebra pr.probability spectral-graph-theory dan_x
fuente

Creo que podría ser más específico en lo que consideraría "eficiente" en ambos casos. ¿Es "eficiente" lo mismo que "no depende de una descomposición de Cholesky"?

Suresh Venkat

Gracias por la sugerencia. Es posible que la respuesta a todas las preguntas sea "necesita calcular una descomposición de Cholesky, y no hay una estructura que pueda aprovecharse más allá de la escasez de la matriz". Me interesaría saber si esto fuera cierto (pero espero que no lo sea). Con respecto a "eficientemente" en el último párrafo, sí, quiero decir más eficientemente que los algoritmos estándar de Cholesky dispersos. Aunque si hubiera una manera de usar las técnicas del trabajo mencionado anteriormente para calcular un Cholesky de la misma manera tan rápida como se puede hacer por otros medios, eso también sería interesante.

dan_x

Si desea muestrear de

, puede usar

, donde

es la matriz de incidencia del gráfico. Por lo tanto, se puede degustar de una gaussiana estándar en

(

son los bordes) y aplicar la transformación lineal

. No sé cómo se compara esto con las sugerencias a continuación, pero no es necesario calcular la descomposición de Cholesky.

N (0, A)

$N(0,A)$

A = B^{T} B

$A = B^T B$

B

$B$

R^{E}

$\mathbb{R}^E$

E

$E$

B

$B$

Lorenzo Najt

Hay dos problemas separados aquí.

Cómo utilizar solucionadores eficientes para con el fin de aplicar . $Ax=b$ $A^{1/2}b$
Cómo calcular el determinante.

Las respuestas cortas son 1) usar aproximaciones de funciones de matriz racional, y 2) no, pero de todos modos no es necesario. Abordo ambos problemas a continuación.

Matriz aproximaciones de raíz cuadrada

La idea aquí es convertir una aproximación de función racional para funciones escalares en una aproximación de función racional para funciones de matriz.

Sabemos que existen funciones racionales que pueden aproximarse extremadamente bien a la función de raíz cuadrada,

\sqrt{x} \approx r (x) := \frac{a_{1}}{x + b_{1}} + \frac{a_{2}}{x + b_{2}} + \dots + \frac{a_{N}}{x + b_{N}},

$\sqrt{x} \approx r(x) := \frac{a_1}{x+b_1} + \frac{a_2}{x+b_2} + \dots + \frac{a_N}{x+b_N},$

b_{i}

$b_i$

[m, M]

$[m,M]$

O (\log \frac{M}{m})

$O(\log \frac{M}{m})$

a_{i}

$a_i$

- b_{i}

$-b_i$

r (A) = a_{1} (A + b_{1} I)^{- 1} + a_{2} (A + b_{2} I)^{- 1} + \dots + a_{N} (A + b_{N} I)^{- 1} .

$r(A) = a_1(A + b_1 I)^{-1} + a_2(A + b_2 I)^{-1} + \dots + a_N(A + b_N I)^{-1}.$

$A$

\begin{aligned} | | A^{1 / 2} - r (A) | |_{2} & = | | U (Σ^{1 / 2} - r (Σ)) U^{*} | |_{2}, \\ = max_{i} | \sqrt{σ_{i}} - r (σ_{i}) | \end{aligned}

$\begin{align} ||A^{1/2} - r(A)||_2 &= ||U\left(\Sigma^{1/2} - r(\Sigma)\right)U^*||_2, \\ &= \max_i |\sqrt{\sigma_i} - r(\sigma_i)| \end{align}$

A = U Σ U^{*}

$A = U \Sigma U^*$

A

$A$

Denotando el número de condición de por , podemos aplicar a cualquier tolerancia deseada mediante la realización de soluciones laplacianas gráficas desplazadas positivamente de la forma, $A$ $\kappa$ $A^{1/2}b$ $O(\log \kappa)$

(A + b I) x = b .

$(A + bI)x=b.$

Estas soluciones se pueden hacer con su solucionador laplaciano de gráficos favorito: prefiero las técnicas de tipo multigrid, pero la del documento que cita también debería estar bien. El adicional solo ayuda a la convergencia del solucionador. $bI$

Para un excelente artículo que discute esto, así como técnicas de análisis complejas más generales que se aplican a las matrices no simétricas, vea Computación , y funciones de matriz relacionadas por integrales de contorno $A^α$ $\log(A)$ , por Hale, Higham y Trefethen (2008 )

"Cálculo" determinante

El determinante es más difícil de calcular. Por lo que yo sé, la mejor manera es calcular la descomposición de Schur utilizando el algoritmo QR, a continuación, leer fuera de los valores propios de la diagonal de la matriz triangular superior . Esto toma tiempo, donde es el número de nodos en el gráfico. $A = Q U Q^*$ $U$ $O(n^3)$ $n$

Sin embargo, calcular los determinantes es un problema inherentemente mal condicionado, por lo que si alguna vez lee un documento que se basa en el cálculo de determinantes de una matriz grande, debe ser muy escéptico sobre el método.

Afortunadamente, probablemente no necesites el determinante. Por ejemplo,

Para extraer muestras de una única distribución gaussiana , la constante de normalización es la misma en todos los puntos, por lo que nunca es necesario calcularla. $N(0,A^{-1})$
Si su matriz laplaciana representa la covarianza inversa de una aproximación gaussiana local en el punto a una distribución no gaussiana, entonces el determinante cambia de punto a punto. Sin embargo, en cada esquema de muestreo efectivo que conozco (incluida la cadena de Markov Monte Carlo, muestreo de importancia, etc.) lo que realmente necesita es la relación determinante , donde es el punto actual, y es la siguiente muestra propuesta. $A = A_x$ $x$ $det (A_{x_{0}}^{- 1} A_{x_{p}}),$ $\det(A_{x_0}^{-1}A_{x_p}),$ $x_0$ $x_p$

Podemos ver como una actualización de bajo rango para la identidad, donde el número efectivo rango, , de la actualización de rango bajo es una medida local de cuán no gaussiana es la distribución verdadera; típicamente esto es mucho más bajo que el rango completo de la matriz. De hecho, si es grande, entonces la distribución verdadera es localmente tan no gaussiana que uno debería cuestionar toda la estrategia de tratar de muestrear esta distribución usando aproximaciones gaussianas locales. $A_{x_0}^{-1}A_{x_p}$

A_{x_{0}}^{- 1} A_{x_{p}} = I + Q D Q^{*},

$A_{x_0}^{-1}A_{x_p} = I + Q D Q^*,$

r

$r$

r

$r$

Los factores y rango bajo se pueden encontrar con SVD aleatorio o Lanczos aplicando la matriz a diferentes vectores, cada aplicación de los cuales requiere un gráfico Solución laplaciana. Por lo tanto, el trabajo general para obtener estos factores de bajo rango es . $Q$ $D$

A_{x_{0}}^{- 1} A_{x_{p}} - I

$A_{x_0}^{-1}A_{x_p} -I$

O (r)

$O(r)$

O (r max (n, E))

$O(r \max(n,E))$

Conociendo , la razón determinante es entonces $D = \text{diag}(d_1,d_2,\dots,d_r)$

det (A_{x_{0}}^{- 1} A_{x_{p}}) = det (I + Q D Q^{*}) = \exp (\sum_{i = 1}^{r} \log d_{i}) .

$\det(A_{x_0}^{-1}A_{x_p}) = \det(I + Q D Q^*) = \exp\left(\sum_{i=1}^r \log d_i\right).$

Estas técnicas de cálculo de racionamiento determinante bajo rango pueden ser encontrados en A estocástico Newton MCMC Método a gran escala estadístico problemas inversos con aplicación a Inversión sísmica , por Martin, et al. (2012) En este documento se aplica a problemas continuos, por lo que el "gráfico" es una cuadrícula en el espacio 3D y el gráfico Laplaciano es la matriz Laplaciana real. Sin embargo, todas las técnicas se aplican a los gráficos laplacianos generales. Probablemente ya haya otros documentos que apliquen esta técnica a gráficos generales (la extensión es trivial y básicamente lo que acabo de escribir).

Nick Alger
fuente

Muestreo de gaussiana multivariante con covarianza laplaciana (inversa) gráfica

Respuestas:

Matriz aproximaciones de raíz cuadrada

"Cálculo" determinante