Échantillonnage à partir de la gaussienne multivariée avec covariance du laplacien graphique (inverse)

Nous savons par exemple de Koutis-Miller-Peng (basé sur les travaux de Spielman & Teng), que nous pouvons résoudre très rapidement des systèmes linéaires pour les matrices qui sont la matrice de graphes laplaciens pour certains graphes clairsemés avec des poids de bord non négatifs . $A x = b$ $A$

Maintenant (première question), envisagez d'utiliser l'une de ces matrices de graphes laplaciens comme covariance ou (deuxième question) matrice de covariance inverse d'une distribution normale multivariée à moyenne nulle , ou . Pour chacun de ces cas, j'ai deux questions: $A$ $\mathcal{N}(\boldsymbol{0}, A)$ $\mathcal{N}(\boldsymbol{0}, A^{-1})$

A. Avec quelle efficacité pouvons-nous tirer un échantillon de cette distribution? (Typiquement pour dessiner un échantillon, nous calculons la décomposition de Cholesky $A = LL^T$ , dessinons une normale normale $y \sim \mathcal{N}(\boldsymbol{0}, I)$ , puis calculons un échantillon comme $x = L^{-1} y$ ).

B. Avec quelle efficacité pouvons-nous calculer le déterminant de $A$ ?

Notez que ces deux pourraient être résolus facilement étant donné une décomposition Cholesky, mais je ne vois pas immédiatement comment extraire $L$ plus efficacement qu'en utilisant simplement un algorithme Cholesky clairsemé standard, qui n'utiliserait pas les techniques présentées dans le référencé ci-dessus fonctionne, et qui aurait une complexité cubique pour les graphiques à largeur d'arbre clairsemée mais élevée.

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

Je pense qu'il pourrait être utile d'être un peu plus précis sur ce que vous considéreriez comme «efficace» dans les deux cas. Est-ce que «efficace» équivaut à «ne dépend pas d'une décomposition de Cholesky»?

Suresh Venkat

Merci pour la suggestion. Il est possible que la réponse à toutes les questions soit «vous devez calculer une décomposition de Cholesky, et aucune structure ne peut être mise à profit au-delà de la rareté de la matrice». Je serais intéressé de savoir si cela était vrai (mais j'espère que ce n'est pas le cas). En ce qui concerne "efficacement" dans le dernier paragraphe, oui, je veux dire surtout plus efficacement que les algorithmes Cholesky clairsemés standard. Bien qu'il y ait un moyen d'utiliser les techniques du travail référencé ci-dessus pour calculer un Cholesky aussi rapidement que possible par d'autres moyens, ce serait également intéressant.

dan_x

Si vous voulez échantillonner à partir de , vous pouvez utiliser , où est la matrice d'incidence du graphique. Ainsi, vous pourrez déguster à partir d' une gaussienne standard sur ( sont les bords) et appliquer la transformation linéaire . Je ne sais pas comment cela se compare aux suggestions ci-dessous, mais vous n'avez pas besoin de calculer la décomposition 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

Il y a deux problèmes distincts ici.

Comment utiliser des solveurs efficaces pour afin d'appliquer . $Ax=b$ $A^{1/2}b$
Comment calculer le déterminant.

Les réponses courtes sont 1) utiliser des approximations de fonctions matricielles rationnelles, et 2) vous n'en avez pas, mais vous n'en avez pas besoin de toute façon. J'aborde ces deux problèmes ci-dessous.

Approximations de la racine carrée de la matrice

L'idée ici est de convertir une approximation de fonction rationnelle pour les fonctions scalaires en une approximation de fonction rationnelle pour les fonctions matricielles.

Nous savons qu'il existe des fonctions rationnelles qui peuvent très bien approcher la fonction racine carrée, pour positif . En effet, pour obtenir une grande précision sur l'intervalle , vous avez besoin de termes dans la série. Pour obtenir les poids appropriés ( ) et les pôles ( ), il suffit de rechercher l'approximation des fonctions rationnelles en ligne ou dans un livre.

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

Envisagez maintenant d'appliquer cette fonction rationnelle à votre matrice:

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

En raison de la symétrie de , nous avons où est la décomposition en valeurs singulières (SVD) de . Ainsi, la qualité de l'approximation de la matrice rationnelle est équivalente à la qualité de l'approximation de la fonction rationnelle à l'emplacement des valeurs propres. $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$

En dénotant le nombre de conditions de par , nous pouvons appliquer à n'importe quelle tolérance souhaitée en effectuant des solutions laplaciennes à graphique positivement décalé de la forme, $A$ $\kappa$ $A^{1/2}b$ $O(\log \kappa)$

(A + b I) x = b .

$(A + bI)x=b.$

Ces solutions peuvent être faites avec votre solveur laplacien graphique préféré - je préfère les techniques de type multigrille, mais celle du document que vous citez devrait également convenir. Le supplémentaire ne fait la convergence du solveur. $bI$

Pour un excellent article discutant de cela, ainsi que des techniques d'analyse complexes plus générales qui s'appliquent aux matrices non symétriques, voir Computing , , and related matrix functions by contour integrals $A^α$ $\log(A)$ , par Hale, Higham et Trefethen (2008 ).

"Calcul" déterminant

Le déterminant est plus difficile à calculer. Pour autant que je sache, la meilleure façon est de calculer la décomposition Schur en utilisant l'algorithme QR, alors lisez les valeurs propres au large de la diagonale de la matrice triangulaire supérieure . Cela prend du temps , où est le nombre de nœuds dans le graphique. $A = Q U Q^*$ $U$ $O(n^3)$ $n$

Cependant, le calcul des déterminants est un problème intrinsèquement mal conditionné, donc si vous lisez un article qui repose sur le calcul des déterminants d'une grande matrice, vous devriez être très sceptique quant à la méthode.

Heureusement, vous n'avez probablement pas réellement besoin du déterminant. Par exemple,

Pour tirer des échantillons d'une seule distribution gaussienne , la constante de normalisation est la même en tous points, vous n'avez donc pas besoin de la calculer. $N(0,A^{-1})$
Si votre matrice laplacienne représente la covariance inverse d'une approximation gaussienne locale au point vers une distribution non gaussienne, alors le déterminant change en effet de point en point. Cependant, dans tous les schémas d'échantillonnage efficaces que je connais (y compris la chaîne de Markov Monte Carlo, l'échantillonnage d'importance, etc.), ce dont vous avez vraiment besoin est le rapport déterminant , où est le point actuel et est le prochain échantillon proposé. $A = A_x$ $x$ $det (A_{x_{0}}^{- 1} A_{x_{p}}),$ $\det(A_{x_0}^{-1}A_{x_p}),$ $x_0$ $x_p$

Nous pouvons voir comme une mise à jour de bas niveau de l'identité, où la valeur numérique effective le rang, , de la mise à jour de bas rang est une mesure locale de la non-gaussienne de la distribution réelle; généralement, il est bien inférieur au rang complet de la matrice. En effet, si est grand, alors la vraie distribution est localement si non gaussienne que l'on devrait remettre en question toute la stratégie d'essayer d'échantillonner cette distribution en utilisant des approximations gaussiennes 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$

Les facteurs de bas rang et peuvent être trouvés avec SVD randomisé ou Lanczos en appliquant la matrice à différents vecteurs, dont chaque application nécessite un graphique Solution laplacienne. Ainsi, le travail global pour obtenir ces facteurs de rang bas est . $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))$

Connaissant , le rapport déterminant est alors $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).$

Ces techniques de calcul de la ration des déterminants de bas rang peuvent être trouvées dans A Stochastic Newton MCMC Method for Large-Scale Statistical Inverse Problems with Application to Seismic Inversion , par Martin, et al. (2012). Dans cet article, il est appliqué à des problèmes de continuum, donc le "graphe" est une grille dans l'espace 3D et le graphe laplacien est la matrice laplacienne réelle. Cependant, toutes les techniques s'appliquent aux Laplaciens graphes généraux. Il y a probablement d'autres articles appliquant cette technique aux graphiques généraux maintenant (l'extension est triviale et fondamentalement ce que je viens d'écrire).

Nick Alger
la source

Échantillonnage à partir de la gaussienne multivariée avec covariance du laplacien graphique (inverse)

Réponses:

Approximations de la racine carrée de la matrice

"Calcul" déterminant