Memperbarui dekomposisi SVD setelah menambahkan satu baris baru ke matriks

Misalkan saya memiliki matriks padat $\textbf{A}$ dari $m \times n$ ukuran, dengan SVD dekomposisiDalam Aku dapat menghitung SVD sebagai berikut: .

A = {U S V}^{⊤} .

$\mathbf{A}=\mathbf{USV}^\top.$ Rsvd(A)

Jika baris baru ditambahkan ke , dapatkah seseorang menghitung dekomposisi SVD baru berdasarkan yang lama (yaitu dengan menggunakan , , dan ), tanpa menghitung ulang SVD dari awal? $(m+1)$ $\mathbf A$ $\mathbf U$ $\mathbf S$ $\mathbf V$

algorithms svd linear-algebra matrix-decomposition numerics pengguna1436187
sumber

Periksa literatur rank 1 updates. Revisi SVD online cepat untuk sistem rekomendasi ringan oleh Brand adalah makalah pertama yang dapat diakses. Saya belum melihat sesuatu untuk SVD sudah diterapkan di R sayangnya. Pembaruan Cholesky ada ( updowndari Matrix) berkat CHOLMOD. Kesederhanaan matriks

akan benar-benar membuat perbedaan untuk solusi akhir Anda; apakah Anda menganggap matriks padat atau jarang?

A

$A$

usεr11852 mengatakan Reinstate Monic

+1 ke @ usεr11852. Juga perhatikan bahwa jauh lebih mudah dan lebih standar untuk memperbarui QR dan dalam beberapa aplikasi QR sudah cukup dan seseorang tidak benar-benar membutuhkan SVD. Jadi pikirkan aplikasi Anda juga.

Amuba mengatakan Reinstate Monica

Ya, matriksnya padat.

user1436187

'Buang' literatur pemberi rekomendasi kemudian dan fokus pada pemrosesan gambar. Pertanyaan serupa dengan tur telah diposting dalam hal "gambar baru" dalam database. Misalnya dugaan saya adalah seseorang harus memiliki algoritma untuk memperbarui entri eigenfaces-nya secara online. Orang-orang ini bekerja dengan representasi matriks padat.

usεr11852 mengatakan Reinstate Monic

Beberapa utas terkait di situs web SE lainnya: scicomp.stackexchange.com/questions/2678 , scicomp.stackexchange.com/questions/19253 , mathoverflow.net/questions/143375 .

Amuba mengatakan Reinstate Monica

Ya, seseorang dapat memperbarui dekomposisi SVD setelah menambahkan satu baris baru ke matriks yang ada.

Secara umum formulasi masalah " tambah satu " ini dikenal sebagai pembaruan peringkat satu . Tautan MathOverflow yang disediakan oleh @amoeba pada " pembaruan peringkat dua efisien dari dekomposisi nilai eigen " adalah langkah pertama yang bagus jika Anda ingin mulai melihat lebih dalam masalah ini; makalah pertama memberikan solusi eksplisit untuk pertanyaan spesifik Anda. Hanya untuk memperjelas apa arti peringkat satu dan dua agar Anda tidak bingung, jika baru Anda sedemikian rupa sehingga: $A^*$

\begin{aligned} A^{*} = A - u v^{T} \end{aligned}

$\begin{align} A^* = A - uv^T \end{align}$

Jika dan adalah vektor, maka Anda merujuk ini sebagai pembaruan peringkat-satu (atau gangguan ). Dasar dari pembaruan ini ditentukan oleh rumus Sherman-Morrison. . Jika perturbasinya lebih dari satu pangkat yaitu. $u$ $v$

\begin{aligned} A^{*} = A - U V^{T} \end{aligned}

$\begin{align} A^* = A - UV^T \end{align}$

yang rumus Woodbury datang ke dalam bermain. Jika Anda melihat formula ini, Anda akan melihat bahwa ada banyak invers yang terlibat. Anda tidak menyelesaikan ini secara langsung. Karena Anda telah menyelesaikan banyak subsistem mereka (mis. Anda memiliki beberapa dekomposisi yang sudah dihitung), Anda menggunakannya untuk mendapatkan perkiraan yang lebih cepat dan / atau lebih stabil. (Itu sebabnya orang masih meneliti bidang ini.) Saya telah menggunakan buku " Statistik Komputasi " oleh JE Gentle sebagai referensi; Saya pikir Bab. 5 Aljabar Linear Numerik akan mengatur Anda dengan benar. (The uber-klasik: " Aljabar Matriks Dari Perspektif Statistik " oleh Harville sayangnya tidak menyentuh pembaruan peringkat sama sekali.)

Melihat ke sisi statistik / aplikasi hal-hal, peringkat satu pembaruan adalah umum dalam sistem rekomendasi karena seseorang mungkin memiliki ribuan entri pelanggan dan menghitung ulang SVD (atau dekomposisi yang diberikan dalam hal ini) setiap kali pengguna baru mendaftar atau produk baru ditambahkan atau dihapus cukup boros (jika tidak bisa dicapai). Biasanya matriks sistem rekomendasi jarang dan ini membuat algoritma lebih efisien. Makalah pertama yang dapat diakses adalah naskah " Revisi SVD online cepat untuk sistem rekomendasi ringan " oleh M. Brand. Pergi ke matriks padat Saya pikir bahwa melihat kertas dari Pengenalan Pola dan Pencitraan Proses dapat membuat Anda cukup jauh dalam mendapatkan algoritma yang sebenarnya untuk digunakan. Misalnya makalah:

Pembelajaran tambahan komponen utama dua arah untuk pengenalan wajah (2009) oleh Ren dan Dai,
Pada pembelajaran ruang bagian tambahan dan kuat (2003) oleh Li et al.
Ekstraksi dasar Sequential Karhunen-Loeve dan penerapannya pada gambar (2000) oleh Levey dan Lindenbaum.
Incremental Learning for Robust Visual Tracking (2007) oleh Ross et al.

semua tampaknya menangani masalah yang sama di intinya; fitur-fitur baru hadir dan kami perlu memperbarui perwakilan kami dengan cepat . Perhatikan bahwa matriks ini tidak simetris atau bahkan kotak. Karya lain dari M. Brand juga dapat mengatasi masalah ini (lihat makalah " Modifikasi peringkat rendah cepat dari dekomposisi nilai singular tipis (2006) " - ini juga disebutkan dalam tautan MO yang diberikan di awal posting.) banyak makalah besar tentang masalah ini tetapi sebagian besar cenderung sangat matematis (misalnya makalah Benaych-Georgesa dan Nadakuditi pada " Nilai tunggal dan vektor gangguan peringkat rendah dari matriks acak persegi panjang besar (2012)") dan saya tidak berpikir mereka akan segera membantu mendapatkan solusi. Saya sarankan Anda tetap fokus pada literatur Pemrosesan Gambar.

Sayangnya saya belum menemukan implementasi R untuk rutinitas peringkat satu. Jawaban pada " Implementasi SVD yang dapat diupdate dalam Python, C, atau Fortran? " Dari SE Computational Science memberikan sejumlah implementasi MATLAB dan C ++ yang mungkin ingin Anda pertimbangkan. Biasanya implementasi R, Python, dll. Adalah pembungkus di sekitar implementasi C, C ++ atau FORTRAN.

usεr11852 kata Reinstate Monic
sumber

Ini adalah komentar yang bagus, tetapi saya kecewa tidak menemukan jawaban untuk pertanyaan itu. Ternyata makalah lain oleh Matthew Brand , yang ditautkan dari jawaban MO, berisi solusi eksplisit.

whuber

Memberi +1 kepada Anda dan @whuber (dan saya tidak berpikir bahwa "menduplikasi" informasi apa pun yang disediakan di situs SE lain harus dihindari! Saya berpendapat bahwa kami harus mencoba membuat informasi yang disediakan di situs ini sebagai mandiri. mungkin, memang hampir semua informasi yang terkandung di sini dalam beberapa hal menggandakan buku teks yang ada, sumber daya online, atau makalah penelitian). Satu pertanyaan: Anda menyebutkan rumus Sherman-Morrison dan Woodbury yang menjelaskan bagaimana kebalikan dari perubahan matriks setelah peringkat-satu atau pembaruan peringkat yang lebih tinggi; apa yang harus mereka lakukan dengan SVD?

Amuba kata Reinstate Monica

Saya mengerti mengapa Anda mungkin ingin mengarahkan orang ke halaman MO untuk tautan itu, tetapi Anda dapat mempertimbangkan secara langsung bahwa itu memecahkan masalah! ("Langkah pertama yang baik" adalah pernyataan yang sangat meremehkan.) Banyak dari komentar Anda dapat disalahpahami sebagai indikasi bahwa Anda belum menemukan solusi yang baik.

whuber

@whuber: "Bagus" menjadi "hebat" dan sekarang saya menyebutkan kertasnya juga, lebih baik? :) (Terima kasih atas umpan baliknya.)

usεr11852 mengatakan Reinstate Monic

Demi sejarah: Bunch dan Nielsen adalah yang pertama menunjukkan cara memperbarui dan memutakhirkan SVD. Metode Brand pada dasarnya menggeneralisasikan metode dari makalah yang lebih tua ini.

JM bukan ahli statistik

Memperbarui dekomposisi SVD setelah menambahkan satu baris baru ke matriks

Jawaban: