Bagaimana SVD dari matriks dihitung dalam praktiknya

Bagaimana MATLAB, misalnya, menghitung SVD dari matriks yang diberikan? Saya berasumsi jawabannya mungkin melibatkan menghitung vektor eigen dan nilai eigen A*A'. Jika itu masalahnya, saya juga ingin tahu bagaimana cara menghitungnya?

Ini biasanya dilakukan dengan menggunakan algoritma Golub-Reinsch, dan tidak, itu tidak melibatkan perhitungan nilai eigen dan vektor eigen dari . $AA^{T}$

Lihat

GH Golub dan C. Reinsch. Dekomposisi Nilai Singular dan Solusi Kuadrat Terkecil. Numerische Mathematik 14: 403-420, 1970.

Materi ini dibahas dalam banyak buku pelajaran tentang aljabar linear numerik.

Terlepas dari makalah Golub-Reinsch (sekarang klasik) yang dicatat Brian dalam jawabannya (saya telah ditautkan dengan versi Buku Pegangan dari makalah ini), serta kertas pendahulunya (juga sekarang klasik) Golub-Kahan , ada sejumlah perkembangan penting dalam komputasi SVD sejak itu. Pertama, saya harus merangkum cara kerja metode yang biasa.

Gagasan dalam menghitung SVD suatu matriks secara kualitatif mirip dengan metode yang digunakan untuk menghitung eigendekomposisi matriks simetris (dan, seperti dicatat dalam OP, ada hubungan intim di antara mereka). Secara khusus, satu hasil dalam dua tahap: transformasi ke matriks bidiagonal , dan kemudian menemukan SVD dari matriks bidiagonal. Ini sepenuhnya analog dengan prosedur pertama mengurangi matriks simetris menjadi bentuk tridiagonal, dan kemudian menghitung komposisi eigend dari tridiagonal yang dihasilkan.

Untuk menghitung SVD dari matriks bidiagonal, satu terobosan yang sangat menarik adalah makalah oleh Jim Demmel dan Velvel Kahan , yang menunjukkan bahwa seseorang dapat menghitung bahkan nilai singular kecil dari matriks bidiagonal dengan akurasi yang baik, dengan memodifikasi metode yang diusulkan pada Golub-Reinsch. Hal ini kemudian diikuti oleh (re?) Penemuan yang dqd algoritma , yang merupakan keturunan dari algoritma quotient-perbedaan lama Rutishauser. (Beresford Parlett memberikan diskusi yang bagus di sini.) Jika memori berfungsi, ini sekarang metode yang disukai digunakan secara internal oleh LAPACK. Terlepas dari ini, selalu mungkin untuk mendapatkan versi perkembangan SVD dalam solusi masalah eigen simetris; misalnya, ada versi SVD dari Divide-and-Conquer, serta versi SVD dari algoritma Jacobi lama (yang mungkin lebih akurat dalam beberapa keadaan).

Adapun bidiagonisasi, satu metode ditingkatkan diuraikan dalam makalah Barlow , yang membutuhkan sedikit lebih banyak pekerjaan daripada prosedur asli Golub dan Reincsh, tetapi menghasilkan matriks bidiagonal yang lebih akurat.