Memahami bagaimana Numpy melakukan SVD

13

Saya telah menggunakan metode yang berbeda untuk menghitung peringkat matriks dan solusi sistem persamaan matriks. Saya menemukan fungsi linalg.svd. Membandingkan ini dengan upaya saya sendiri untuk memecahkan sistem dengan Gaussian Elimination, tampaknya lebih cepat dan lebih tepat. Saya mencoba memahami bagaimana ini mungkin.

Sejauh yang saya tahu, fungsi linalg.svd menggunakan algoritma QR untuk menghitung nilai eigen dari matriks saya. Saya tahu bagaimana ini bekerja secara matematis, tetapi saya tidak tahu bagaimana Numpy berhasil melakukannya dengan cepat dan tanpa kehilangan banyak presisi.

Jadi pertanyaan saya: Bagaimana fungsi numpy.svd bekerja, dan lebih khusus lagi, bagaimana ia berhasil melakukannya dengan cepat dan akurat (dibandingkan dengan eliminasi gaussian)?

RobVerheyen
sumber
2
numpy menggunakan rutin Lapack dgesdduntuk SVD bernilai nyata. Jadi pertanyaan Anda yang sebenarnya mungkin adalah "bagaimana cara kerja Lapack dgesdd?", Dan itu cukup banyak topik untuk stackoverflow.
talonmies
Jika Anda BENAR-BENAR penasaran, saya sarankan memeriksa sumber LAPACK.
Terima kasih atas komentar Anda, dan permintaan maaf saya tidak sopan.
RobVerheyen
Posting ini adalah pos-silang dari Stack Overflow . Cross-postingan umumnya tidak disarankan di situs Stack Exchange. Protokol standar untuk memposting ulang pertanyaan di situs yang berbeda adalah untuk menutup, menghapus, atau memigrasikan pos asli sebelum mencoba memposting ulang di situs yang berbeda. (Jika Anda memigrasikan pertanyaan itu, ia mem-posting ulang secara otomatis.)
Geoff Oxberry
Maaf, saya tidak mengetahui protokolnya. Saya harap saya masih bisa mendapatkan jawaban.
RobVerheyen

Jawaban:

15

Ada sejumlah masalah dalam pertanyaan Anda.

Jangan gunakan Eliminasi Gaussian (faktorisasi LU) untuk menghitung peringkat numerik dari sebuah matriks. Faktorisasi LU tidak dapat diandalkan untuk tujuan ini dalam aritmatika titik-mengambang. Sebagai gantinya, gunakan dekomposisi QR yang mengungkapkan peringkat (seperti xGEQPXatau xGEPQYdi LAPACK, di mana x adalah C, D, S, atau Z, meskipun rutinitas tersebut sulit dilacak; lihat jawaban JedBrown pada pertanyaan terkait ), atau gunakan SVD (dekomposisi nilai singular, seperti xGESDDatau xGESVD, di mana x lagi C, D, S, atau Z). SVD adalah algoritma yang lebih akurat dan andal untuk penentuan peringkat numerik, tetapi membutuhkan lebih banyak operasi floating-point.

Namun, untuk menyelesaikan sistem linier, faktorisasi LU (dengan pivoting parsial, yang merupakan implementasi standar dalam LAPACK) dalam praktiknya sangat andal. Ada beberapa kasus patologis yang faktorisasi LU dengan pivoting parsial tidak stabil (lihat Kuliah 22 dalam Aljabar Linier Numerik)oleh Trefethen dan Bau untuk detail). Faktorisasi QR adalah algoritme numerik yang lebih stabil untuk menyelesaikan sistem linier, yang mungkin itulah sebabnya ia memberi Anda hasil yang presisi. Namun, itu membutuhkan lebih banyak operasi floating-point daripada faktorisasi LU dengan faktor 2 untuk matriks kuadrat (saya percaya; JackPoulson dapat memperbaiki saya dalam hal itu). Untuk sistem persegi panjang, faktorisasi QR adalah pilihan yang lebih baik karena akan menghasilkan solusi kuadrat-terkecil untuk sistem linier yang ditentukan secara berlebihan. SVD juga dapat digunakan untuk menyelesaikan sistem linear, tetapi akan lebih mahal daripada faktorisasi QR.

janneb benar bahwa numpy.linalg.svd adalah pembungkus xGESDDdi LAPACK. Dekomposisi nilai singular diproses dalam dua tahap. Pertama, matriks yang akan diurai dikurangi menjadi bentuk bidiagonal. Algoritma yang digunakan untuk mereduksi menjadi bentuk bidiagonal di LAPACK mungkin adalah algoritma Lawson-Hanson-Chan, dan memang menggunakan faktorisasi QR pada satu titik. Kuliah 31 dalam Aljabar Linier Numerik oleh Trefethen dan Bau memberikan ikhtisar proses ini. Kemudian, xGESDDgunakan algoritma divide-and-conquer untuk menghitung nilai singular dan vektor singular kiri dan kanan dari matriks bidiagonal. Untuk mendapatkan latar belakang pada langkah ini, Anda harus berkonsultasi dengan Komputasi Matriks oleh Golub dan Van Loan, atau Aljabar Linear Numerik Terapan oleh Jim Demmel.

Akhirnya, Anda tidak harus mengacaukan nilai singular dengan nilai eigen . Dua set jumlah ini tidak sama. SVD menghitung nilai singular dari sebuah matriks. Komputasi Numerik Cleve Moler dengan MATLAB memberikan gambaran yang bagus tentang perbedaan antara nilai singular dan nilai eigen . Secara umum, tidak ada hubungan yang jelas antara nilai singular dari matriks yang diberikan dan nilai eigennya, kecuali dalam kasus matriks normal , di mana nilai singular adalah nilai absolut dari nilai eigen.

Geoff Oxberry
sumber
Saya pikir "tidak terkait" cukup kuat untuk hubungan antara nilai eigen dan nilai singular. Hubungannya cukup tidak jelas kecuali Anda mengetahui dekomposisi penuh Jordan dari matriks Anda, tetapi Anda dapat menggunakan salah satu untuk mendapatkan perkiraan dari yang lain jika Anda memiliki informasi (atau bersedia untuk membuat asumsi) tentang kata dekomposisi Jordan.
Dan
Apa yang akan Anda sarankan sebagai gantinya?
Geoff Oxberry
Pertama-tama, terima kasih atas jawaban yang terperinci. Saya menemukan bahwa saya tidak dapat menggunakan dekomposisi LU untuk menentukan peringkat matriks dengan cara yang sulit. Jawaban Anda tampaknya menyiratkan bahwa factorisation QR sebenarnya akan menjadi metode yang lebih cepat untuk menyelesaikan masalah saya, benar? Apakah ada keuntungan berbeda dalam menggunakan SVD? Saya sangat menyadari fakta bahwa nilai singular bukan nilai eigen. Saya merujuk pada fakta bahwa nilai singular dapat dihitung sebagai nilai eigen dari matriks dikalikan dengan transposinya dari kiri. Maaf itu tidak jelas.
RobVerheyen
Saya mungkin menambahkan bahwa matriks yang saya pecahkan sebenarnya tunggal. Bahkan, peringkat matriks hanya sekitar setengah dari ukuran matriks. Mungkin ini membuat beberapa metode lebih disukai?
RobVerheyen
1
@RobVerheyen: QR akan lebih lambat daripada LU, tetapi jauh lebih akurat. SVD akan lebih lambat daripada QR, tetapi SVD dianggap sebagai metode yang paling dapat diandalkan untuk menentukan peringkat numerik (misalnya, MATLAB menggunakan SVD dalam rankfungsinya). Ada juga sedikit keleluasaan yang terlibat ketika menggunakan salah satu pendekatan; dalam pendekatan SVD, peringkat numerik adalah jumlah nilai singular di atas batas tertentu (biasanya sangat kecil). (Pendekatan QR serupa, tetapi menggantikan nilai singular dengan entri diagonal dari matriks R.)
Geoff Oxberry
8

Karena kata-kata dari pertanyaan Anda, saya mengasumsikan bahwa matriks Anda adalah persegi. Rutinitas SVD LAPACK, seperti zgesvd , pada dasarnya melanjutkan dalam tiga tahap untuk matriks persegi:

  1. UAVAAB:=UAHAVAUAVABO(n3)
  2. {UB,VB,Σ}B=UBΣVBHO(n2)O(n3)
  3. Langkah ini sepele. Karena , A = ( U A U B ) Σ ( V A V B ) H , sehingga SVD dapat secara eksplisit dibentuk setelah menerapkan transformasi Householder yang secara implisit menentukanUABVAH=AA=(UAUB)Σ(VAVB)HUAVAUBVBO(n3)
Jack Poulson
sumber
7

numpy.linalg.svd adalah pembungkus sekitar {Z, D} GESDD dari LAPACK. LAPACK, pada gilirannya, sangat hati-hati ditulis oleh beberapa pakar terkemuka dunia dalam aljabar linear numerik. Memang, akan sangat mengejutkan jika seseorang yang tidak akrab dengan bidang itu akan berhasil mengalahkan LAPACK (baik dalam kecepatan atau akurasi).

Adapun mengapa QR lebih baik daripada eliminasi Gaussian, itu mungkin lebih cocok untuk /scicomp//

janneb
sumber
Terima kasih atas jawabannya dan referensi. Saya akan mencobanya di sana.
RobVerheyen