Apa itu algoritma yang efisien untuk menghitung dekomposisi nilai singular (SVD)?

17

Artikel Wikipedia tentang analisis komponen utama menyatakan itu

Algoritma yang efisien ada untuk menghitung SVD tanpa harus membentuk matriks X T X , jadi menghitung SVD sekarang menjadi cara standar untuk menghitung analisis komponen utama dari matriks data, kecuali hanya segelintir komponen yang diperlukan.XXTX

Bisakah seseorang memberi tahu saya apa algoritma efisien yang dibicarakan oleh artikel ini? Tidak ada referensi yang diberikan (URL atau kutipan ke artikel yang mengusulkan cara perhitungan ini akan menyenangkan).

pca algorithms svd numerics svd
sumber
4
Pencarian Google pada algoritma dekomposisi nilai singular melakukan pekerjaan yang baik untuk menyoroti informasi yang relevan.
whuber
1
Jangan lupa untuk menghapus mean sebelum SVD untuk PCA!
Memming
Coba Lanczos SVD!
ciri

Jawaban:

12

MNAmasukkan deskripsi gambar di sini

Seperti yang Anda lihat tergantung pada use case Anda ada pendekatan yang berbeda (konvensi penamaan rutin dapat ditemukan di sini ). Itu karena, misalnya ada bentuk matriks di mana pengurangan Anggota Rumah Tangga bisa lebih mahal daripada rotasi Givens (untuk menyebutkan dua cara "jelas" untuk mendapatkan QR). Referensi standar tentang masalah ini adalah Komputasi Matriks Golub dan Van Loan (saya sarankan menggunakan setidaknya edisi ke-3). Saya juga menemukan Å. Metode Numerik Björck untuk Kuadrat Terkecil Masalah sumber daya yang sangat baik dalam hal ini; sementara SVD bukan fokus utama buku ini, ia membantu mengontekstualisasikan penggunaannya.

Jika saya harus memberi Anda satu saran umum tentang masalah ini adalah jangan mencoba untuk menulis algoritma SVD Anda sendiri kecuali Anda telah berhasil mengambil beberapa kelas pada Aljabar Linear Numerik dan Anda tahu apa yang Anda lakukan. Saya tahu ini kedengarannya berlawanan dengan intuisi tetapi sebenarnya, ada banyak hal yang bisa salah dan Anda berakhir dengan (paling baik) implementasi sub-optimal (jika tidak salah). Ada beberapa suite gratis yang sangat bagus untuk masalah ini (mis. Eigen , Armadillo dan Trilinos untuk beberapa nama.)

usεr11852 kata Reinstate Monic
sumber
XA
1
MNAXTX
2
Ya, saya salah: QR tidak terbatas pada matriks persegi. +1, omong-omong. Pertanyaan ini adalah salah satu pertanyaan tertinggi yang belum dijawab dengan tag pca , jadi senang melihatnya akhirnya dijawab.
Amuba kata Reinstate Monica
Jawaban Anda tidak menyebutkan berbagai macam algoritma iteratif. Apakah itu disengaja? Seseorang bertanya tentang algoritma SVD iteratif, lihat Apa algoritma cepat yang ada untuk menghitung SVD terpotong? , dan saya mengirim jawaban di sana mencoba memberikan beberapa ikhtisar. Mungkin kita harus setidaknya menghubungkan jawaban kita. Dan tentu saja akan sangat bagus jika Anda dapat memperluas milik Anda dengan beberapa diskusi tentang algoritma QR vs algoritma iteratif.
Amuba kata Reinstate Monica
Tidak, itu kebetulan. Anda menjawab pertanyaan Anda sendiri di pos Anda; SVD yang terpotong pada dasarnya merupakan komposisi eigend yang terpotong (lihat misalnya ARPACK ). Ada beberapa perbedaan baik tetapi mereka baik - baik saja ; beberapa perangkat lunak (mis. MATLAB's svds) hanya menggunakan fungsi SVD terpotong mereka sebagai pembungkus untuk eigsrutinitas eigendecomposition ( ) terpotong mereka .
usεr11852 mengatakan Reinstate Monic