menghitung SVD terpotong, satu nilai / vektor tunggal pada suatu waktu

Apakah ada algoritma SVD terpotong yang menghitung nilai singular satu per satu?

Masalah saya: Saya ingin menghitung nilai singular pertama (dan vektor singular) dari matriks padat , tapi saya tidak tahu apa nilai tepat. itu besar, jadi untuk alasan efisiensi, saya lebih suka tidak mengevaluasi SVD lengkap hanya untuk memotong SV terkecil setelah itu.M k $k$$M$$k$$M$

Idealnya, akan ada cara untuk menghitung nilai singular secara serial, dari terbesar ( ) hingga terkecil ( ). Dengan begitu, saya hanya bisa menghentikan perhitungan setelah menghitung th nilai singular jika turun di bawah ambang batas.σ 1 σ n k σ k / σ $\sigma_1, \sigma_2,\ldots$$\sigma_1$$\sigma_n$$k$$\sigma_k/\sigma_1$

Apakah ada algoritma seperti itu (lebih disukai dengan implementasi Python)? Dalam googling saya, saya hanya menemukan fungsi SVD terpotong yang menggunakan k sebagai parameter, sehingga memaksa Anda untuk menebaknya secara apriori.

Ada beberapa opsi yang tersedia jika Anda menginginkan perkiraan faktor-faktor peringkat-k.

1. Faktorisasi QR dengan peringkat tinggi
2. Dekomposisi interpolatif (ID) dan teknik acak lainnya.

Perkiraan faktorisasi dari formulir di atas dapat dikonversi menjadi dekomposisi standar seperti QR atau SVD menggunakan teknik standar. Ulasan yang baik tersedia di surat kabar oleh Halko, Martinsson dan Tropp "Menemukan struktur dengan acak: Algoritma probabilistik untuk membangun perkiraan dekomposisi matriks"

Dalam hal perangkat lunak antarmuka untuk algoritma ID tersedia dalam scipy (scipy.linalg.interpolative) http://docs.scipy.org/doc/scipy-dev/reference/linalg.interpolative.html yang memungkinkan Anda pengguna untuk menentukan .$\epsilon$

(Diedit, karena saya salah membaca pertanyaan pada awalnya; Anda sudah tahu bahwa ada rutinitas yang tersedia untuk menghitung nilai singular pertama .)$k$

Jika Anda mengecualikan pendekatan penghitungan seluruh SVD, sebagian algoritma SVD mengurangi menggunakan metode iteratif untuk memecahkan masalah nilai eigen Hermitian terkait. Jadi, salah satu strategi yang bisa Anda ambil adalah meng-hand-code hal ini sendiri, dan terus memecahkan untuk mendapatkan nilai tunggal terbesar yang belum terpecahkan hingga Anda ingin berhenti, menggunakan sesuatu seperti strategi shift-and-invert. Mungkin ada cara yang elegan untuk melakukan hal semacam ini dalam paket canggih seperti SLEPc .

Strategi lain adalah sebagai berikut:

• $s_{1}$
• $\tau \cdot s_{1} \cdot f$$\tau$$0 < f \leq 1$
• Panggil rutin SVD yang jarang.

$k$