Amostragem a partir de gaussiana multivariada com covariância gráfica inversa

Sabemos, por exemplo, de Koutis-Miller-Peng (baseado no trabalho de Spielman & Teng), que podemos resolver muito rapidamente sistemas lineares $A x = b$ para matrizes $A$ que são o gráfico da matriz laplaciana para algum gráfico esparso com pesos de borda não negativos .

Agora (primeira pergunta) considere o uso de uma dessas matrizes do gráfico Laplaciano $A$ como matriz de covariância ou (segunda questão) covariância de uma distribuição normal multivariada com média zero ou . Para cada um desses casos, tenho duas perguntas: $\mathcal{N}(\boldsymbol{0}, A)$ $\mathcal{N}(\boldsymbol{0}, A^{-1})$

A. Com que eficiência podemos extrair uma amostra dessa distribuição? (Normalmente, para desenhar uma amostra, calculamos a decomposição de Cholesky , desenhamos um normal e depois calculamos uma amostra como ). $A = LL^T$ $y \sim \mathcal{N}(\boldsymbol{0}, I)$ $x = L^{-1} y$

B. Com que eficiência podemos calcular o determinante de ? $A$

Observe que ambos podem ser resolvidos facilmente com uma decomposição de Cholesky, mas não vejo imediatamente como extrair mais eficiência do que simplesmente usando um algoritmo esparso padrão de Cholesky, que não usaria as técnicas apresentadas nas referências acima. obras e que teriam complexidade cúbica para gráficos de largura de árvore esparsa, mas alta. $L$

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

Eu acho que pode ajudar a ser um pouco mais específico sobre o que você consideraria "eficiente" nos dois casos. "Eficiente" é o mesmo que "não depende de uma decomposição de Cholesky"?

Suresh Venkat

Obrigado pela sugestão. É possível que a resposta para todas as perguntas seja "você precisa calcular uma decomposição de Cholesky, e não existe uma estrutura que possa ser aproveitada além da escassez da matriz". Eu estaria interessado em saber se isso era verdade (mas espero que não seja). Com relação a "eficientemente" no último parágrafo, sim, quero dizer mais eficientemente do que os algoritmos esparsos padrão de Cholesky. Embora se houvesse uma maneira de usar as técnicas do trabalho acima mencionado para calcular um Cholesky da maneira mais rápida possível, por outros meios, isso também seria interessante.

dan_x

Se você quiser amostrar a partir de , use , onde é a matriz de incidência do gráfico. Assim, é possível provar a partir de uma Gaussiana padrão em ( são as arestas) e aplicam-se a transformação linear . Não sei como isso se compara às sugestões abaixo, mas você não precisa calcular a decomposição 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 11/11/19

Existem duas questões separadas aqui.

Como usar solucionadores eficientes para para aplicar . $Ax=b$ $A^{1/2}b$
Como calcular o determinante.

As respostas curtas são: 1) use aproximações racionais da função da matriz; e 2) você não usa, mas não precisa. Abordo esses dois problemas abaixo.

Aproximações de raiz quadrada de matriz

A idéia aqui é converter uma aproximação de função racional para funções escalares em uma aproximação de função racional para funções de matriz.

Sabemos que existem funções racionais que podem aproximar extremamente bem a função da raiz quadrada, para positivo . De fato, para obter alta precisão no intervalo , você precisa dos termos da série. Para obter os pesos apropriados ( ) e polos ( ), basta procurar a aproximação da função racional online ou em um livro.

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

Agora considere aplicar esta função racional à sua matriz:

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

Devido à simetria de , temos onde é a decomposição do valor singular (SVD) de . Portanto, a qualidade da aproximação da matriz racional é equivalente à qualidade da aproximação da função racional no local dos valores próprios. $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 o número de condição de por , podemos aplicar a qualquer tolerância desejada executando gráfico com deslocamento positivo Soluções Laplacianas da forma, $A$ $\kappa$ $A^{1/2}b$ $O(\log \kappa)$

(A + b I) x = b .

$(A + bI)x=b.$

Essas soluções podem ser feitas com o seu solucionador gráfico Laplaciano favorito - prefiro técnicas do tipo multigrid, mas a que você mencionou no artigo também deve ser boa. O extra ajuda apenas a convergência do solucionador. $bI$

Para um excelente artigo discutindo isso, bem como técnicas gerais de análise complexa que se aplicam a matrizes não simétricas, consulte Computação , e funções de matriz relacionadas por integrais de contorno $A^α$ $\log(A)$ , de Hale, Higham e Trefethen (2008). )

Determinação "computação"

O determinante é mais difícil de calcular. Tanto quanto eu sei, a melhor maneira é calcular a Schur decomposição usando o algoritmo QR, em seguida, ler fora dos valores próprios da diagonal da matriz triangular superior . Isso leva tempo , onde é o número de nós no gráfico. $A = Q U Q^*$ $U$ $O(n^3)$ $n$

Entretanto, calcular determinantes é um problema inerentemente mal condicionado, portanto, se você ler um artigo que se baseia em determinantes computacionais de uma matriz grande, deve ser muito cético em relação ao método.

Felizmente, você provavelmente não precisa do determinante. Por exemplo,

Para extrair amostras de uma única distribuição gaussiana , a constante de normalização é a mesma em todos os pontos, para que você nunca precise calculá-la. $N(0,A^{-1})$
Se sua matriz laplaciana representa a covariância inversa de uma aproximação gaussiana local no ponto a uma distribuição não gaussiana, o determinante realmente muda de ponto a ponto. No entanto, em todo esquema de amostragem eficaz que eu conheço (incluindo Monte Carlo da cadeia de Markov, amostragem de importância etc.) o que você realmente precisa é a razão determinante , onde é o ponto atual e é a próxima amostra proposta. $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 visualizar como uma atualização de baixa classificação para a identidade, onde o número numérico efetivo rank, , da atualização de rank baixo é uma medida local de quão não gaussiana é a verdadeira distribuição; Normalmente, isso é muito menor do que a classificação completa da matriz. De fato, se é grande, então a distribuição verdadeira é localmente tão não-gaussiana que é preciso questionar toda a estratégia de tentar amostrar essa distribuição usando aproximações gaussianas locais. $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$

Os fatores de baixo escalão e podem ser encontrados com SVD ou Lanczos aleatórios aplicando a matriz a vetores diferentes, cada aplicação requer um gráfico Solução Laplaciana. Portanto, o trabalho geral para obter esses fatores de classificação baixa é . $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))$

Conhecendo , a taxa determinante é então $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).$

Essas técnicas de cálculo de ração determinante de baixo escalão podem ser encontradas em Um método estocástico de Newton MCMC para problemas estatísticos inversos de larga escala com aplicação à inversão sísmica , por Martin, et al. (2012). Neste artigo, ele é aplicado a problemas de continuum, de modo que o "gráfico" é uma grade no espaço 3D e o gráfico Laplaciano é a matriz laplaciana real. No entanto, todas as técnicas se aplicam aos laplacianos gerais do gráfico. Provavelmente já existem outros trabalhos que aplicam essa técnica a gráficos gerais (a extensão é trivial e basicamente o que acabei de escrever).

Nick Alger
fonte

Amostragem a partir de gaussiana multivariada com covariância gráfica inversa

Respostas:

Aproximações de raiz quadrada de matriz

Determinação "computação"