Pengambilan sampel dari Multivariat Gaussian dengan Kovarian Graph Laplacian (terbalik)

Kita tahu dari misalnya Koutis-Miller-Peng (berdasarkan karya Spielman & Teng), bahwa kita dapat dengan cepat menyelesaikan sistem linear $A x = b$ untuk matriks $A$ yang merupakan grafik matriks Laplacian untuk beberapa grafik jarang dengan bobot tepi non-negatif .

Sekarang (pertanyaan pertama) pertimbangkan untuk menggunakan salah satu dari grafik ini Matriks Laplacian $A$ sebagai kovarians atau (pertanyaan kedua) matriks kovarians terbalik dari distribusi normal multivariat nol rata-rata , atau . Untuk masing-masing kasus ini, saya punya dua pertanyaan: $\mathcal{N}(\boldsymbol{0}, A)$ $\mathcal{N}(\boldsymbol{0}, A^{-1})$

A. Seberapa efisien kita dapat mengambil sampel dari distribusi ini? (Biasanya untuk menggambar sampel, kami menghitung dekomposisi Cholesky , menggambar standar normal , lalu menghitung sampel sebagai ). $A = LL^T$ $y \sim \mathcal{N}(\boldsymbol{0}, I)$ $x = L^{-1} y$

B. Seberapa efisienkah kita menghitung determinan ? $A$

Perhatikan bahwa kedua hal ini dapat diselesaikan dengan mudah karena dekomposisi Cholesky, tetapi saya tidak segera melihat cara mengekstrak lebih efisien daripada hanya dengan menggunakan algoritma Cholesky standar yang jarang, yang tidak akan menggunakan teknik yang disajikan dalam referensi yang disebutkan di atas. bekerja, dan yang akan memiliki kompleksitas kubik untuk grafik jarang tapi tinggi-treewidth. $L$

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

Saya pikir mungkin membantu untuk menjadi sedikit lebih spesifik pada apa yang Anda anggap "efisien" dalam kedua kasus. Apakah "efisien" sama dengan "tidak bergantung pada dekomposisi Cholesky"?

Suresh Venkat

Terima kasih untuk sarannya. Ada kemungkinan jawaban untuk semua pertanyaan adalah "Anda perlu menghitung dekomposisi Cholesky, dan tidak ada struktur yang dapat dimanfaatkan melampaui kerawanan matriks." Saya akan tertarik untuk mengetahui apakah ini benar (tapi saya harap itu tidak benar). Sehubungan dengan "efisien" pada paragraf terakhir, ya, maksud saya kebanyakan lebih efisien daripada algoritma Cholesky jarang standar. Meskipun jika ada cara untuk menggunakan teknik-teknik dari karya yang direferensikan di atas untuk menghitung Cholesky secepat yang dapat dilakukan melalui cara lain, itu juga akan menarik.

dan_x

Jika Anda ingin mengambil sampel dari , Anda dapat menggunakan , di mana adalah matriks kejadian dari grafik. Dengan demikian, Anda dapat mencicipi dari Gaussian standar pada ( adalah tepi) dan menerapkan transformasi linear . Saya tidak tahu bagaimana ini dibandingkan dengan saran di bawah ini, tetapi Anda tidak perlu menghitung dekomposisi 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

Ada dua masalah terpisah di sini.

Cara menggunakan pemecah yang efisien untuk untuk menerapkan . $Ax=b$ $A^{1/2}b$
Cara menghitung determinan.

Jawaban singkatnya adalah 1) menggunakan perkiraan fungsi matriks rasional, dan 2) Anda tidak, tetapi Anda tidak perlu lagi. Saya membahas kedua masalah ini di bawah.

Perkiraan akar kuadrat matriks

Idenya di sini adalah untuk mengubah pendekatan fungsi rasional untuk fungsi skalar menjadi pendekatan fungsi rasional untuk fungsi matriks.

Kita tahu bahwa ada fungsi rasional yang dapat memperkirakan fungsi akar kuadrat dengan sangat baik, untuk positif . Memang, untuk mendapatkan akurasi tinggi pada interval , Anda memerlukan istilah dalam seri. Untuk mendapatkan bobot yang sesuai ( ) dan kutub ( ), lihat saja perkiraan fungsi rasional secara online atau dalam buku.

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

Sekarang pertimbangkan untuk menerapkan fungsi rasional ini ke matriks Anda:

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

Karena simetri , kita memiliki di mana adalah dekomposisi nilai singular (SVD) dari . Jadi, kualitas aproksimasi matriks rasional setara dengan kualitas aproksimasi fungsi rasional di lokasi nilai eigen. $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$

Mendenotasikan nomor kondisi oleh , kita dapat menerapkan untuk toleransi yang diinginkan dengan melakukan positif menggeser grafik solusi Laplacian dari formulir, $A$ $\kappa$ $A^{1/2}b$ $O(\log \kappa)$

(A + b I) x = b .

$(A + bI)x=b.$

Solusi ini dapat dilakukan dengan solver grafik Laplacian favorit Anda — saya lebih suka teknik tipe multigrid, tetapi yang ada di makalah yang Anda kutip harus baik juga. ekstra hanya membantu konvergensi pemecah. $bI$

Untuk makalah yang sangat baik membahas hal ini, serta teknik analisis kompleks yang lebih umum yang berlaku untuk matriks nonsimetrik, lihat Komputasi , , dan fungsi matriks terkait oleh integral kontur $A^α$ $\log(A)$ , oleh Hale, Higham, dan Trefethen (2008 ).

"Perhitungan" determinan

Penentu lebih sulit untuk dihitung. Sejauh yang saya tahu, cara terbaik adalah untuk menghitung Schur dekomposisi menggunakan algoritma QR, kemudian membaca dari nilai eigen dari diagonal dari atas-matriks segitiga . Ini membutuhkan waktu , di mana adalah jumlah node dalam grafik. $A = Q U Q^*$ $U$ $O(n^3)$ $n$

Namun, menghitung faktor penentu adalah masalah yang pada dasarnya tidak dikondisikan, jadi jika Anda pernah membaca makalah yang mengandalkan komputasi faktor penentu dari matriks besar, Anda harus sangat skeptis terhadap metode ini.

Untungnya, Anda mungkin tidak benar-benar membutuhkan determinan. Sebagai contoh,

Untuk mengambil sampel dari satu distribusi Gaussian , konstanta normalisasi adalah sama di semua titik sehingga Anda tidak perlu menghitungnya. $N(0,A^{-1})$
Jika matriks Laplacian Anda mewakili kovarians terbalik dari pendekatan Gaussian lokal pada titik ke distribusi non-Gaussian, maka penentu memang berubah dari titik ke titik. Namun, dalam setiap skema pengambilan sampel yang efektif, saya tahu (termasuk rantai Markov, Monte Carlo, sampel penting, dll.) Yang Anda perlukan adalah rasio penentu , mana adalah titik saat ini, dan adalah contoh berikutnya yang diusulkan. $A = A_x$ $x$ $det (A_{x_{0}}^{- 1} A_{x_{p}}),$ $\det(A_{x_0}^{-1}A_{x_p}),$ $x_0$ $x_p$

Kita dapat melihat sebagai pembaruan peringkat rendah untuk identitas, mana numerik efektif peringkat, , dari pembaruan peringkat rendah adalah ukuran lokal tentang seberapa non-Gaussian distribusi sebenarnya; biasanya ini jauh lebih rendah daripada peringkat penuh dari matriks. Memang, jika besar, maka distribusi yang sebenarnya adalah lokal sehingga non-Gaussian sehingga orang harus mempertanyakan seluruh strategi mencoba sampel distribusi ini menggunakan perkiraan Gaussian lokal. $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$

Faktor peringkat rendah dan dapat ditemukan dengan SVD acak atau Lanczos dengan menerapkan matriks ke vektor yang berbeda, setiap aplikasi yang membutuhkan satu grafik Solusi Laplacian. Jadi pekerjaan keseluruhan untuk mendapatkan faktor-faktor peringkat rendah ini adalah . $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))$

Mengetahui , rasio penentu kemudian $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).$

Teknik perhitungan ransum penentu peringkat rendah ini dapat ditemukan dalam Metode MCMC Newton Stochastic untuk Masalah Pembalikan Statistik Skala Besar dengan Aplikasi untuk Seismic Inversion , oleh Martin, et al. (2012). Dalam makalah ini diterapkan untuk masalah kontinum, sehingga "grafik" adalah kotak dalam ruang 3D dan grafik Laplacian adalah matriks Laplacian yang sebenarnya. Namun, semua teknik berlaku untuk grafik umum Laplacians. Mungkin ada makalah lain yang menerapkan teknik ini untuk grafik umum sekarang (ekstensi itu sepele dan pada dasarnya apa yang baru saja saya tulis).

Nick Algeria
sumber

Pengambilan sampel dari Multivariat Gaussian dengan Kovarian Graph Laplacian (terbalik)

Jawaban:

Perkiraan akar kuadrat matriks

"Perhitungan" determinan