Abtastung aus multivariaten Gaußschen mit graphischer Laplace-Kovarianz (invers)

Wir wissen beispielsweise aus Koutis-Miller-Peng (basierend auf der Arbeit von Spielman & Teng), dass wir lineare Systeme sehr schnell $A x = b$ für Matrizen lösen können $A$ , die die Laplace-Matrix für einige spärliche Graphen mit nicht negativen Kantengewichten sind .

Betrachten Sie nun (erste Frage) die Verwendung einer dieser Laplace-Matrizen $A$ als Kovarianz oder (zweite Frage) inverse Kovarianzmatrix einer multivariaten Normalverteilung mit einem Mittelwert von Null oder . Für jeden dieser Fälle habe ich zwei Fragen: $\mathcal{N}(\boldsymbol{0}, A)$ $\mathcal{N}(\boldsymbol{0}, A^{-1})$

A. Wie effizient können wir aus dieser Verteilung eine Stichprobe ziehen? (Um eine Stichprobe zu zeichnen, berechnen wir normalerweise die Cholesky-Zerlegung , zeichnen eine normale Norm und berechnen dann eine Stichprobe als ). $A = LL^T$ $y \sim \mathcal{N}(\boldsymbol{0}, I)$ $x = L^{-1} y$

B. Wie effizient können wir die Determinante von berechnen $A$ ?

Beachten Sie, dass beide Probleme bei einer Cholesky-Zerlegung leicht gelöst werden können, aber ich sehe nicht sofort, wie $L$ effizienter extrahiert werden kann, als nur mit einem spärlichen Standard-Cholesky-Algorithmus, der die in den oben genannten Techniken nicht beschriebenen Techniken verwendet funktioniert, und die kubische Komplexität für Graphen mit geringer, aber hoher Baumbreite hätte.

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

Ich denke, es könnte hilfreich sein, etwas genauer zu sagen, was Sie in beiden Fällen als "effizient" betrachten würden. Ist "effizient" dasselbe wie "nicht abhängig von einer Cholesky-Zersetzung"?

Suresh Venkat

Danke für den Vorschlag. Es ist möglich, dass die Antwort auf alle Fragen lautet: "Sie müssen eine Cholesky-Zerlegung berechnen, und es gibt keine Struktur, die über die Kargheit der Matrix hinaus genutzt werden kann." Es würde mich interessieren, ob dies wahr ist (aber ich hoffe, dass es nicht wahr ist). In Bezug auf "effizient" im letzten Absatz meine ich meistens effizienter als Standard-Cholesky-Algorithmen mit geringer Dichte. Wenn es eine Möglichkeit gäbe, die Techniken der oben genannten Arbeit zu verwenden, um einen Cholesky so schnell zu berechnen, wie dies mit anderen Mitteln möglich ist, wäre dies ebenfalls interessant.

dan_x

Wenn Sie eine Stichprobe aus erstellen möchten , können Sie , wobei die Inzidenzmatrix des Diagramms ist. Sie können also aus einem Standard-Gaußschen Wert auf ( sind die Kanten) abtasten und die lineare Transformation anwenden . Ich weiß nicht, wie dies mit den folgenden Vorschlägen verglichen wird, aber Sie müssen die Cholesky-Zerlegung nicht berechnen.

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

Hier gibt es zwei verschiedene Probleme.

Verwendung effizienter Löser für , um anzuwenden . $Ax=b$ $A^{1/2}b$
Wie berechnet man die Determinante?

Die kurzen Antworten lauten: 1) Verwenden Sie Näherungen für rationale Matrixfunktionen und 2) Sie tun dies nicht, müssen es aber trotzdem nicht. Ich gehe auf diese beiden Probleme weiter unten ein.

Matrix Quadratwurzel Approximationen

Die Idee hier ist, eine rationale Funktionsnäherung für Skalarfunktionen in eine rationale Funktionsnäherung für Matrixfunktionen umzuwandeln.

Wir wissen, dass es rationale Funktionen gibt, die sich der Quadratwurzelfunktion sehr gut annähern können: für positives . Um eine hohe Genauigkeit für das Intervall erzielen, benötigen Sie Terme in der Reihe. Um die entsprechenden Gewichte ( ) und Pole ( ) zu erhalten, suchen Sie einfach online oder in einem Buch nach der Näherung rationaler Funktionen.

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

Wenden Sie nun diese rationale Funktion auf Ihre Matrix an:

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

Aufgrund der Symmetrie von haben wir wobei die Singularwertzerlegung (SVD) von . Die Qualität der rationalen Matrixnäherung entspricht also der Qualität der rationalen Funktionsnäherung am Ort der Eigenwerte. $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$

Indem wir die Bedingungsnummer von mit , können wir auf jede gewünschte Toleranz anwenden, indem wir positiv verschobene Laplace-Lösungen der Form $A$ $\kappa$ $A^{1/2}b$ $O(\log \kappa)$

(A + b I) x = b .

$(A + bI)x=b.$

Diese Lösungen können mit Ihrem bevorzugten Laplace-Löser durchgeführt werden. Ich bevorzuge Techniken vom Typ Multigrid, aber die in dem von Ihnen zitierten Artikel sollte auch in Ordnung sein. Das zusätzliche hilft nur bei der Konvergenz des Lösers. $bI$

Eine ausgezeichnete Arbeit, die dies diskutiert, sowie allgemeinere komplexe Analysetechniken, die für unsymmetrische Matrizen gelten, finden Sie unter Berechnen von , und verwandten $A^α$ $\log(A)$ Matrixfunktionen durch Konturintegrale von Hale, Higham und Trefethen (2008) ).

Determinante "Berechnung"

Die Determinante ist schwerer zu berechnen. Soweit ich weiß, besteht der beste Weg darin, die Schur-Zerlegung mit dem QR-Algorithmus zu berechnen und dann die Eigenwerte aus der Diagonale der oberen Dreiecksmatrix abzulesen . Dies dauert , wobei die Anzahl der Knoten im Diagramm ist. $A = Q U Q^*$ $U$ $O(n^3)$ $n$

Die Berechnung von Determinanten ist jedoch ein inhärent schlecht konditioniertes Problem. Wenn Sie also jemals eine Arbeit lesen, die sich auf die Berechnung von Determinanten einer großen Matrix stützt, sollten Sie der Methode sehr skeptisch gegenüberstehen.

Zum Glück brauchen Sie die Determinante wahrscheinlich nicht wirklich. Beispielsweise,

Um Stichproben aus einer einzelnen Gaußschen Verteilung , ist die Normalisierungskonstante an allen Punkten gleich, sodass Sie sie niemals berechnen müssen. $N(0,A^{-1})$
Wenn Ihre Laplace-Matrix die inverse Kovarianz einer lokalen Gaußschen Näherung am Punkt zu einer nicht-Gaußschen Verteilung darstellt, ändert sich die Determinante tatsächlich von Punkt zu Punkt. Doch in jeder effektiven Stichprobenplan die ich kenne (einschließlich Markov - Kette Monte Carlo, Importance Sampling, etc.) , was Sie wirklich brauchen , ist die Determinante Verhältnis , wo ist der aktuelle Punkt und ist das vorgeschlagene nächste Beispiel. $A = A_x$ $x$ $det (A_{x_{0}}^{- 1} A_{x_{p}}),$ $\det(A_{x_0}^{-1}A_{x_p}),$ $x_0$ $x_p$

Wir können als eine niedrigrangige Aktualisierung der Identität , wobei die effektive Der Rang der Aktualisierung mit niedrigem Rang ist ein lokales Maß dafür, wie nicht-Gauß die wahre Verteilung ist. Typischerweise ist dies viel niedriger als der volle Rang der Matrix. Wenn groß ist, ist die wahre Verteilung lokal so nicht-Gaußsch, dass man die gesamte Strategie in Frage stellen sollte, diese Verteilung unter Verwendung lokaler Gaußscher Näherungen abzutasten. $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$

Die niedrigrangigen Faktoren und können mit randomisierter SVD oder Lanczos gefunden werden, indem die Matrix auf verschiedene Vektoren , für deren Anwendung jeweils ein Graph erforderlich ist Laplace-Lösung. Somit ist die Gesamtarbeit zum Erhalten dieser Faktoren mit niedrigem Rang . $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))$

Wenn man , ist das Determinantenverhältnis dann $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).$

Diese Berechnungsverfahren für die Determinantenration mit niedrigem Rang finden sich in einer stochastischen Newton-MCMC-Methode für großräumige statistische inverse Probleme bei der Anwendung auf die seismische Inversion von Martin et al. (2012). In diesem Artikel wird es auf Kontinuumsprobleme angewendet, sodass der "Graph" ein Gitter im 3D-Raum ist und der Graph Laplace die tatsächliche Laplace-Matrix ist. Alle Techniken gelten jedoch für allgemeine Graph-Laplace-Werte. Es gibt wahrscheinlich andere Artikel, die diese Technik inzwischen auf allgemeine Grafiken anwenden (die Erweiterung ist trivial und im Grunde das, was ich gerade geschrieben habe).

Nick Alger
quelle

Abtastung aus multivariaten Gaußschen mit graphischer Laplace-Kovarianz (invers)

Antworten:

Matrix Quadratwurzel Approximationen

Determinante "Berechnung"