Perkiraan spektrum matriks besar

14

Saya ingin menghitung spektrum ( semua nilai eigen) dari matriks jarang besar (ratusan ribu baris). Ini sulit.

Saya bersedia menerima perkiraan. Apakah ada metode perkiraan untuk melakukan ini?

Sementara saya berharap jawaban umum untuk pertanyaan ini, saya juga akan puas dengan jawaban dalam kasus khusus berikut. Matriks saya adalah Laplacian yang dinormalisasi dari grafik besar. Nilai eigen akan berada di antara 0 dan 2 dengan jumlah besar dikelompokkan sekitar 1.

linear-algebra eigensystem graph-theory approximation MRocklin
sumber

Apakah matriksnya jarang atau padat?

Aron Ahmadia

Matriksnya jarang. Saya telah mengedit pertanyaan untuk mencerminkan hal ini.

MRocklin

Mengapa Anda menginginkan semua nilai eigen? Ini hampir secara universal merupakan hal yang buruk untuk dilakukan ketika Anda memiliki matriks yang jarang atau terstruktur, sehingga penting untuk mengetahui bagaimana Anda berencana untuk menggunakannya.

Jed Brown

Spektrum laplacian grafik membawa beberapa informasi penting yang ingin saya periksa. Saya tidak membutuhkan semuanya, saya hanya perlu tahu secara kasar di mana mereka berada.

MRocklin

15

Jika grafik Anda tidak diarahkan (seperti yang saya duga), matriksnya simetris, dan Anda tidak dapat melakukan apa pun lebih baik daripada algoritma Lanczsos (dengan reorthogonalization selektif jika perlu untuk stabilitas). Karena spektrum penuh terdiri dari 100000 angka, saya kira Anda terutama tertarik pada kepadatan spektral.

Untuk mendapatkan kerapatan spektral perkiraan, ambil spektrum subruang Krylov terkemuka dengan dimensi 100 atau lebih, dan ganti kepadatan diskritnya dengan versi yang dihaluskan.

Spektrum Krylov terkemuka akan hampir menyelesaikan nilai-nilai eigen yang terisolasi dengan baik (jika ada), mendekati nilai eigen pada akhir spektrum non-isolasi, dan agak acak di antaranya, dengan distribusi yang fungsi distribusi kumulatifnya menyerupai spektrum sebenarnya. . Itu akan menyatu dalam aritmatika yang tepat jika dimensi tumbuh. (Jika operator Anda berdimensi tak terbatas, ini masih akan terjadi, dan Anda akan mendapatkan integral dari fungsi kepadatan spektral sejati pada spektrum kontinu.)

Arnold Neumaier
sumber

Bukankah spektrum subruang Krylov yang terkemuka hanya akan menjadi 100 nilai eigen terbesar? Saya juga tertarik dengan distribusi nilai eigen moderat dan terkecil.

MRocklin

1

@MRocklin: Tidak. Saya menambah jawaban saya untuk memberikan lebih banyak detail.

Arnold Neumaier

6

Jawaban Arnold Neumaier dibahas secara lebih rinci dalam bagian 3.2 dari makalah "Approxating Spectral Densities of Large Matrices" oleh Lin Lin, Yousef Saad dan Chao Yang (2016) .

Beberapa metode lain juga dibahas tetapi analisis numerik pada akhir makalah ini menunjukkan bahwa metode Lanczos mengungguli alternatif ini.

A. Van Werde
sumber

4

Jika Anda setuju dengan hal-hal yang bukan merupakan nilai eigen tetapi berfungsi yang dalam beberapa hal masih memberi tahu Anda sesuatu tentang spektrum, maka saya pikir Anda harus memeriksa beberapa karya oleh Mark Embree di Rice University.

Wolfgang Bangerth
sumber

2

Inilah cara lain untuk mengkarakterisasi spektrum.

Diberikan masalah nilai eigen (asumsikan simetris nyata dan nilai eigen yang terpisah; meskipun yang terakhir mungkin tidak diperlukan), mari kita coba untuk memperkirakan kepadatan spektral yang dioleskan $\mathbf{A} v_k = \lambda_k v_k$ $\mathbf{A}$ Setelah memukul misalnyahttp://dx.doi.org/10.1016/0377-0427 00018-0dalam pencarian literatur, kita tahu bahwa tidak bias Estimator Monte Carlo untuk penelusuran adalah

S (ω) = \sum_{k} \frac{π^{- 1} σ}{σ^{2} + (λ_{k} - ω)^{2}} = \frac{σ}{π} T r [σ^{2} + (ω - SEBUAH)^{2}]^{- 1}

$S(\omega) = \sum_k \frac{\pi^{-1}\sigma}{\sigma^2 + (\lambda_k - \omega)^2} = \frac{\sigma}{\pi} \mathop{\mathrm{Tr}} [\sigma^2 + (\omega - \mathbf{A})^2]^{-1}$

di mana setiap entri dari vektor acak

mengandung baik

atau

dengan probabilitas 0,5 untuk setiap. Untuk diberikan

dan

, produk terbalik

S (ω) = \frac{σ}{π} ⟨ z^{T} [σ^{2} + (ω - SEBUAH)^{2}]^{- 1} z ⟩

$S(\omega) = \frac{\sigma}{\pi}\langle z^T [\sigma^2 + (\omega - \mathbf{A})^2]^{-1} z \rangle$

z

$z$

+ 1

$+1$

- 1

$-1$

σ

$\sigma$

ω

$\omega$

[σ^{2} + (ω - A)^{2}]^{- 1} z

$[\sigma^2 + (\omega - \mathbf{A})^2]^{-1} z$ dapat dihitung misalnya dengan metode gradien konjugat, atau LU jarang pada

untuk meminimalkan pengisian. Ini memungkinkan estimasi

juga untuk matriks besar. Dalam praktiknya, tampaknya solusi CG tidak harus sangat akurat, dan tidak ada banyak vektor yang diperlukan dalam menghitung rata-rata. Ini mungkin tergantung pada masalahnya.

[ω + i σ - A]^{- 1} [ω - i σ - A]^{- 1}

$[\omega + i \sigma - \mathbf{A}]^{-1} [\omega - i \sigma - \mathbf{A}]^{-1}$

S (ω)

$S(\omega)$

$\omega$

pv.
sumber

0

Lihat kertas "On Decomposition Spectral Decomposition berbasis-sampling" oleh Sanjiv Kumar, Mehryar Mohri & Ameet Talwalkar (ICML 2009.). Ini menggunakan pengambilan sampel kolom dari matriks Anda.

Karena matriks Anda simetris, Anda harus melakukan hal berikut:

Biarkan A menjadi matriks n * n Anda. Anda ingin mengurangi perhitungan nilai eigen dari matriks n * n menjadi perhitungan nilai eigen dari matriks k * k. Pertama-tama pilih nilai k. Katakanlah Anda memilih k = 500, karena Anda dapat dengan mudah menghitung nilai eigen dari matriks 500 * 500. Kemudian, pilih secara acak k kolom dari matriks A. Buatlah matriks B yang hanya menyimpan kolom-kolom ini, dan baris yang sesuai.

B = A (x, x) untuk satu set indeks k acak x

B sekarang adalah ak * k matrix. Hitung nilai eigen B, dan kalikan dengan (n / k). Anda sekarang memiliki nilai k yang kira-kira terdistribusi seperti n nilai eigen A. Perhatikan bahwa Anda hanya mendapatkan nilai k, bukan n, tetapi distribusinya akan benar (sampai faktanya nilai tersebut merupakan perkiraan).

Jérôme Kunegis
sumber

-1

Anda selalu dapat menggunakan Teorema lingkaran Gershgorin batas untuk memperkirakan nilai eigen.

Jika istilah off-diagonal kecil, diagonal itu sendiri adalah perkiraan yang baik dari spektrum. Kalau tidak, jika Anda berakhir dengan perkiraan eigenspace (dengan metode lain) Anda bisa mencoba untuk mengekspresikan entri diagonal dalam sistem ini. Ini akan mengarah ke matriks dengan istilah off-diagonal yang lebih kecil dan diagonal baru akan menjadi perkiraan spektrum yang lebih baik.

FKaria
sumber

Gerschgoring tidak memberikan aproksimasi selain batas kesalahan, jadi tidak relevan di sini. Selain itu, menggunakan metode Anda pada matriks jarang akan membutuhkan matriks vektor eigen padat, yang tidak mungkin disimpan untuk masalah OP.

Arnold Neumaier

Seperti yang saya katakan, diagonal itu sendiri merupakan perkiraan spektrum dengan batas kesalahan yang diberikan oleh teorema lingkaran Gershgorin, tentu saja batas kesalahan Gershgorin bukan perkiraan. Diagonal akan menjadi perkiraan yang baik jika istilah off-diagonal kecil, yang saya percaya adalah kasusnya karena OP mengatakan bahwa matriks jarang.

FKaria

5

Sebagian besar matriks jarang yang muncul dalam praktik memiliki beberapa elemen off-diagonal yang signifikan di setiap baris dan kolom, yang membuat perkiraan diagonal sangat buruk (misalnya, untuk Laplacian dari grafik biasa, diagonalnya konstan), dan kesalahannya tidak berguna.

Arnold Neumaier

Perkiraan spektrum matriks besar

Jawaban: