Algoritma cepat apa yang ada untuk komputasi SVD terpotong?

Mungkin di luar topik di sini, tetapi sudah ada beberapa ( satu , dua ) pertanyaan terkait.

Mengaduk-aduk dalam literatur (atau pencarian google untuk Algoritma SVD Terpotong) muncul banyak makalah yang menggunakan SVD terpotong dalam berbagai cara, dan klaim (frustasi, sering tanpa kutipan) bahwa ada algoritma cepat untuk menghitungnya, tetapi tidak ada yang tampaknya menunjuk pada apa itu algoritma.

Satu-satunya hal yang dapat saya temukan adalah algoritma acak tunggal , yang digunakan di perpustakaan redSVD .

Yang ingin saya lihat adalah seperangkat algoritma yang tepat dan tidak eksak, cocok untuk memahami bagaimana sistem bekerja (tetapi tentu saja tidak untuk benar-benar mengimplementasikannya!).

Adakah yang punya referensi bagus untuk hal semacam ini?

algorithms svd numerics John Doucette
sumber

Jika saya ingin menyimpan data dengan baik, saya menggunakan b-tree (atau rb-tree) di hash (pikirkan ram). Jika saya memiliki b-tree untuk data, maka saya bisa dalam O (log (n)) sampel waktu kuantil dan semacamnya. Saya bertaruh bahwa dengan data yang besar, pengambilan sampel seperti itu dapat digunakan untuk menghitung perkiraan yang jarang untuk matriks svd dalam waktu singkat. Anda mungkin juga mencari "penginderaan terkompresi" yang merupakan pendekatan yang sangat statistik untuk kompresi data ekstrem.

EngrStudent

Dengan terpotong SVD Anda berarti bahwa Anda hanya tertarik untuk menemukan beberapa vektor / nilai singular terkemuka, yang bertentangan dengan mereka semua?

Amuba mengatakan Reinstate Monica

@amoeba Yap, itulah idenya.

John Doucette

Jawaban:

Secara garis besar, ada dua pendekatan untuk menghitung nilai eigen atau dekomposisi nilai singular. Salah satu pendekatan adalah mendiagonalisasi matriks dan ini pada dasarnya menghasilkan seluruh dekomposisi nilai eigen / nilai singular (seluruh spektrum nilai eigen) pada saat yang sama, lihat beberapa tinjauan umum di sini: Apa algoritma yang efisien untuk menghitung dekomposisi nilai singular (SVD)? Alternatifnya adalah dengan menggunakan algoritma iteratif yang menghasilkan satu (atau beberapa) vektor eigen dalam satu waktu. Iterasi dapat dihentikan setelah jumlah vektor eigen yang diinginkan telah dihitung.

Saya tidak berpikir ada algoritma berulang khusus untuk SVD. Ini karena seseorang dapat menghitung SVD dari matriks dengan melakukan eigendekomposisi dari simetris persegi matriks Oleh karena itu alih-alih bertanya apa algoritma komputasi dipotong SVD, Anda harus bertanya apa yang berulang algoritma menghitung eigendecomposition: $n\times m$ $\mathbf B$ $(n+m)\times(n+m)$

SEBUAH = (\begin{array}{cc} 0 & B \\ B^{⊤} & 0 \end{array}) .

$\mathbf A=\left(\begin{array}{cc}0 & \mathbf B\\\mathbf B^\top & 0\end{array}\right).$

algoritma untuk SVD terpotong \approx algoritma iteratif untuk komposisi eigend .

$\text{algorithm for truncated SVD} \approx \text{iterative algorithm for eigendecomposition}.$

Algoritma iteratif yang paling sederhana disebut power iteration dan memang sangat sederhana:

Inisialisasi acak $\mathbf x$ .
Perbarui $\mathbf x \gets \mathbf A\mathbf x$ .
Normalisasi $\mathbf x \gets \mathbf x / \|\mathbf x\|$ .
Pergi langkah # 2 kecuali terkonvergensi.

Semua algoritma yang lebih kompleks pada akhirnya didasarkan pada ide iterasi daya, tetapi cukup canggih. Matematika yang diperlukan diberikan oleh subruang Krylov . Algoritme adalah iterasi Arnoldi (untuk matriks nonsimetrik persegi), nonsimetrik iterasi Lanczos (untuk matriks simetris persegi), dan variasi-variasi darinya seperti misalnya "metode Lanczos yang dimulai kembali secara implisit" dan yang lainnya.

Anda dapat menemukan ini dijelaskan dalam misalnya buku teks berikut:

Semua bahasa pemrograman dan paket statistik yang masuk akal (Matlab, R, Python numpy, sebut saja) menggunakan pustaka Fortran yang sama untuk melakukan dekomposisi eigen / nilai singular. Ini adalah LAPACK dan ARPACK . ARPACK adalah singkatan dari ARnoldi PACKage, dan ini semua tentang iterasi Arnoldi / Lanczos. Misalnya dalam Matlab ada dua fungsi untuk SVD: svdmelakukan dekomposisi penuh melalui LAPACK, dan svdsmenghitung sejumlah vektor tunggal melalui ARPACK dan itu sebenarnya hanya pembungkus untuk suatueigs panggilan pada matriks "persegi".

Memperbarui

$\mathbf B$ $\mathbf A$ $\mathbf A$ $\mathbf B$ $\mathbf A$ dan dengan demikian menghemat ruang dan waktu.

Ada perpustakaan Fortran untuk metode ini juga, itu disebut PROPACK :

Paket perangkat lunak PROPACK berisi seperangkat fungsi untuk menghitung dekomposisi nilai singular matriks besar dan jarang atau terstruktur. Rutinitas SVD didasarkan pada algoritma bidiagonisasi Lanczos dengan reorthogonalization parsial (BPRO).

Namun, PROPACK tampaknya jauh lebih sedikit standar daripada ARPACK dan tidak didukung secara native dalam bahasa pemrograman standar. Buku ini ditulis oleh Rasmus Larsen yang memiliki kertas lebar dua halaman panjang 1998-halaman Lanczos tahun 1998 dengan re - reogogenisasi parsial dengan apa yang tampaknya gambaran yang bagus. Terima kasih kepada @MichaelGrant via utas Ilmu Komputasi SE ini .

Di antara makalah yang lebih baru, yang paling populer adalah Baglama & Reichel, 2005, Augmented secara implisit memulai kembali metode bidiagonisasi Lanczos , yang mungkin sekitar canggih. Terima kasih kepada @Dougal karena memberikan tautan ini di komentar.

Perbarui 2

Memang ada pendekatan yang sama sekali berbeda dijelaskan secara rinci dalam makalah tinjauan umum yang Anda kutip sendiri: Halko et al. 2009, Menemukan struktur dengan keacakan: Algoritma probabilitas untuk membangun dekomposisi matriks perkiraan . Saya tidak cukup tahu tentang hal itu untuk berkomentar.

amuba kata Reinstate Monica
sumber

Perhatikan bahwa ada metode iterasi khusus SVD; mis. Augmentedisasi yang Dipartisi Secara Tersirat Memulai Kembali Metode Bidiagonisasi Lanczos , J. Baglama dan L. Reichel, SIAM J. Sci. Komputasi. 2005. (Saya belum membaca makalah untuk mengetahui apakah secara fundamental berbeda dari pendekatan nilai eigen yang Anda berikan, hanya tahu bahwa orang-orang menyukai metode itu.)

Dougal

Terima kasih untuk tautannya, @Dougal. Saya harus mengatakan bahwa saya tidak benar-benar mengetahui salah satu dari metode ini dengan baik, jadi tidak dapat mengomentari hal itu. Akan lebih bagus jika seseorang yang lebih berpengetahuan akan menjelaskan hubungan antara berbagai metode berulang. Sejauh yang saya mengerti, metode vanilla Lanczos adalah untuk menghitung nilai eigen dari matriks persegi dan bukan untuk SVD; "Lanczos yang ditambahkan secara implisit dimulai kembali" harus terkait erat dengan itu, tetapi Anda benar - sepertinya langsung tentang SVD. Tidak yakin bagaimana semuanya cocok. Saya akan memperbarui jawaban saya jika saya bisa melihat lebih dekat.

Amuba mengatakan Reinstate Monica

@Dougal, saya membaca sepintas lalu dan membuat pembaruan.

Amuba mengatakan Reinstate Monica

@amoeba akan "memotong SVD" dalam konteks kuadrat terkecil yang diatur pada dasarnya sama dengan "regresi komponen prinsip" ?

GeoMatt22

@amoeba Bisakah Anda mengomentari penerapan SVD acak Facebook , beberapa orang tampaknya mengatakan bahwa itu adalah salah satu solusi tercepat yang mungkin saat ini. Alangkah baiknya jika Anda dapat mengedit untuk mengomentari ini juga.

Tim

Saya baru saja menemukan thread melalui googling SVD cepat, jadi saya mencoba untuk mencari tahu sendiri, tapi mungkin Anda harus melihat ke dalam pendekatan lintas adaptif (ACA).

$M$ $M=\sum_{i=0}^k U_i\cdot V^T_i$ $N\times N$ $O(N)$ ). Jadi sangat cepat; sayangnya banyak orang menggunakan kata "cepat" dengan ringan.

Sekali lagi, itu tergantung pada masalah Anda jika itu berhasil. Dalam banyak kasus saya pribadi temui, ACA adalah alat numerik yang sangat berguna.

Catatan: Saya ingin menulis ini sebagai komentar, tetapi karena saya baru saja membuat akun ini, saya tidak memiliki reputasi yang cukup untuk komentar ... Tetapi memposting berfungsi.

oli
sumber

Berikut adalah teknik yang saya gunakan dengan sukses di masa lalu untuk menghitung SVD terpotong (pada dataset Netflix). Ini diambil dari makalah ini . Dalam pengaturan penyaringan kolaboratif, saya harus mencatat bahwa sebagian besar nilai yang hilang dan intinya adalah untuk memprediksi mereka , jadi untuk menggunakan SVD terpotong untuk memecahkan masalah seperti itu, Anda harus menggunakan teknik yang bekerja di bawah kondisi itu. Deskripsi singkat:

Sebelum Anda melakukan apa pun, paskan model sederhana (mis. Global mean + nilai konstanta kolom dan baris), dan hanya sekali Anda selesai melakukannya Anda harus beralih menggunakan SVD terpotong agar sesuai dengan residu.
Inisialisasi vektor acak dengan panjang k (di mana peringkat Anda memotong) untuk setiap baris dan kolom (untuk setiap film dan pengguna dalam kasus Netflix).
Pegang vektor baris tetap dan perbarui vektor kolom untuk meminimalkan kesalahan wrt entri yang dikenal dalam matriks. Prosedur ini diberikan dalam kode matlab di kertas.
Tahan vektor kolom tetap dan perbarui vektor baris dengan cara yang analog.
Ulangi 3 & 4 sampai Anda bertemu atau mendapatkan hasil yang cukup baik.

Joe Pete yang kekar
sumber