Bagaimana keadaan terkini tentang algoritma untuk dekomposisi nilai singular?

Saya sedang mengerjakan perpustakaan matriks header-only untuk memberikan tingkat kemampuan aljabar linier yang masuk akal dalam paket sesederhana mungkin, dan saya mencoba mensurvei seperti apa keadaan seni saat ini: menghitung SVD dari sebuah matriks kompleks.

Saya sedang melakukan dekomposisi dua fase, bidiagonisasi diikuti oleh perhitungan nilai singular. Saat ini saya menggunakan metode rumah tangga untuk bidiagonisasi (saya percaya LAPACK juga menggunakan ini), dan saya pikir itu sama baiknya dengan yang didapat saat ini (kecuali jika seseorang mengetahui algoritma untuk itu..). $\mathcal{O}(N^2)$

Perhitungan nilai singular adalah yang berikutnya dalam daftar saya, dan saya agak keluar dari lingkaran tentang apa algoritma umum untuk melakukan ini. Saya membaca di sini bahwa penelitian sedang menuju ke metode iterasi terbalik yang menjamin ortogonalitas dengan kompleksitas . Saya akan tertarik mendengar tentang itu atau kemajuan lainnya. $\mathcal{O}(N)$

apakah ada dokumen untuk lib matriks khusus header (selain dari .h)? Juga tolong tambahkan tag "svd".

denis

Jawaban:

"Algoritma acak" baru-baru ini menjadi sangat populer untuk sebagian svds. Implementasi header saja dapat diunduh di sini: http://code.google.com/p/redsvd/

Peninjauan metode saat ini dapat ditemukan di sini: http://arxiv.org/abs/0909.4061

Untuk svds penuh, saya tidak yakin apakah Anda bisa melakukan lebih baik daripada Householder.

dranxo
sumber

Kedengarannya sangat menarik, saya harus melihat kertas survei itu, terima kasih!

OP tertarik pada algoritma untuk matriks padat. Saya tidak berpikir algoritma acak kompetitif dalam pengaturan itu, jika mereka bekerja sama sekali.

Federico Poloni

Posting ini menunjukkan bahwa metode acak berfungsi dengan baik pada matriks padat research.facebook.com/blog/294071574113354/fast-randomized-svd

dranxo

@ docxo Tidak ada perbandingan akurasi sama sekali pada posting itu, dan hasil waktu tidak terlihat sangat teliti. Juga, algoritma acak didasarkan pada proyeksi + solusi tepat dari masalah skala kecil. Ini berarti OP akan memerlukan implementasi "metode standar" untuk masalah skala kecil yang dihasilkan.

Federico Poloni

Cukup adil. Meskipun saya agak bingung mengapa kita harus berpikir bahwa metode ini hanya bekerja pada matriks yang jarang. Langsung keluar abstrak dari makalah Joel Tropp: "Untuk matriks input padat, algoritma acak membutuhkan O (mn log (k)) operasi floating-point (jepit) berbeda dengan O (mnk) untuk algoritma klasik." arxiv.org/pdf/0909.4061v2.pdf

dranxo

Saya membaca di sini bahwa penelitian sedang menuju ke metode iterasi terbalik yang menjamin ortogonalitas dengan kompleksitas . Saya akan tertarik mendengar tentang itu atau kemajuan lainnya. $\mathcal{O}(N)$

(Saya hanya ingin membuat beberapa komentar karena saya tidak punya waktu untuk menulis rincian, tetapi itu agak besar untuk kotak komentar.)

Yang saya yakini akan menjadi algoritma MRRR (beberapa representasi yang relatif kuat) dari Dhillon dan Parlett. Ini berakar pada karya sebelumnya oleh Fernando, yang pada gilirannya terinspirasi oleh masalah yang ditimbulkan oleh Jim Wilkinson dalam buku monumentalnya tentang masalah nilai eigen. Bagian "iterasi terbalik" untuk memperoleh vektor singular berakar dalam konsep "faktorisasi bengkok" oleh Fernando , yang memanfaatkan matriks faktorisasi menjadi dan dekomposisi . $\mathbf L\mathbf D\mathbf L^\top$ $\mathbf U\mathbf D\mathbf U^\top$

Bagian "nilai singular" dari algoritma, di sisi lain, berasal dari algoritme perbedaan selisih (bergeser) (dqd) , yang merupakan puncak dari karya sebelumnya oleh Fernando, Parlett , Demmel dan Kahan (dengan inspirasi dari Heinz Rutishauser).

Seperti yang Anda ketahui metode SVD biasanya melanjutkan dengan dekomposisi bidiagonal terlebih dahulu sebelum nilai singular diperoleh dari matriks bidiagonal. Sayangnya saya tidak terlalu memperbarui metode terbaik saat ini untuk dekomposisi bidiagonal front-end; Terakhir saya periksa, metode yang biasa adalah mulai dengan dekomposisi QR dengan pivoting kolom dan kemudian menerapkan transformasi ortogonal dengan tepat pada faktor segitiga untuk akhirnya mendapatkan dekomposisi bidiagonal.

Saya mengerti bahwa saya kurang detail; Saya akan mencoba menyempurnakan jawaban ini lebih jauh setelah saya memiliki akses ke perpustakaan saya ...

JM
sumber

Matriks ke bentuk bi-diagonal, lakukan kolom kemudian baris, ulangi diagonal: gunakan givens atau rumah tangga untuk membidik kolom hingga diagonal, lalu lakukan hal yang sama untuk baris ke super-diagonal.

adam W

Abaikan komentar saya sebelumnya, saya memikirkan bentuk tri-diagonal. Maaf. Bi-diagonalisasi tidak sepele dalam kesamaan (itu sebenarnya akan mengungkapkan nilai eigen), tetapi referensi Anda tidak melakukan kesamaan, itu melakukan sesuatu yang lain; kalikan kiri dan kanan dengan matriks ortogonal yang berbeda. adalah bi-diagonal dengan dan , yang dapat dilakukan seperti yang Anda katakan dengan QR terlebih dahulu, tetapi tidak begitu mudah dijelaskan dalam komentar. Saya mungkin tertarik jika Anda menyempurnakan jawaban lebih lanjut (tapi saya juga bisa mengetahuinya karena studi saya mengarah ke arah ini saat ini).

U A V

$UAV$

U U^{⊤} = I

$UU^\top=I$

V V^{⊤} = I

$VV^\top=I$

adam W

Ada perpustakaan PROPACK dan nu-TRLan.

http://soi.stanford.edu/~rmunk/PROPACK/

http://crd-legacy.lbl.gov/~kewu/trlan/

kekuasaan
sumber

Di sini, poster meminta algoritma, bukan perpustakaan; bisakah Anda berbicara tentang algoritma yang digunakan di perpustakaan ini, kompleksitas komputasinya, dan mengapa perpustakaan ini canggih?

Geoff Oxberry