Makalah penting tentang dekomposisi matriks

18

Baru-baru ini saya membaca buku Skillicorn tentang dekomposisi matriks, dan sedikit kecewa, karena ditargetkan untuk audiens sarjana. Saya ingin mengkompilasi (untuk saya dan orang lain) bibliografi singkat dari makalah penting (survei, tetapi juga makalah terobosan) pada dekomposisi matriks. Apa yang ada dalam pikiran saya terutama adalah sesuatu pada SVD / PCA (dan varian kuat / jarang), dan NNMF, karena sejauh ini yang paling banyak digunakan. Apakah Anda semua memiliki rekomendasi / saran? Saya menahan milik saya untuk tidak bias jawaban. Saya akan meminta untuk membatasi setiap jawaban menjadi 2-3 makalah.

PS: Saya menyebut kedua dekomposisi ini sebagai yang paling banyak digunakan dalam analisis data . Tentu saja QR, Cholesky, LU dan polar sangat penting dalam analisis numerik. Tapi itu bukan fokus pertanyaan saya.

matrix-decomposition svd numerics gappy
sumber

Jawaban:

16

Bagaimana Anda tahu bahwa SVD dan NMF sejauh ini merupakan dekomposisi matriks yang paling banyak digunakan daripada LU, Cholesky dan QR? 'Terobosan' favorit pribadi saya harus berupa algoritme QR pengungkapan peringkat yang dijamin,

  • Chan, Tony F. "Peringkat mengungkapkan faktorisasi QR". Aljabar Linier dan Volume Penerapannya 88-89, April 1987, Halaman 67-82. DOI: 10.1016 / 0024-3795 (87) 90103-0

... pengembangan gagasan QR sebelumnya dengan pivot-kolom:

  • Businger, Peter; Golub, Gene H. (1965). Linear least square solusi oleh transformasi Householder. Numerische Mathematik Volume 7, Number 3, 269-276, DOI: 10.1007 / BF01436084

A ( yang ?) Buku teks klasik adalah:

  • Golub, Gene H .; Van Loan, Charles F. (1996). Komputasi Matriks (edisi ketiga), Johns Hopkins, ISBN 978-0-8018-5414-9 .

(saya tahu Anda tidak meminta buku teks tetapi saya tidak bisa menolak)

Sunting: Sedikit lagi googling menemukan sebuah makalah yang abstraknya menyarankan kita bisa sedikit berselisih. Teks saya di atas berasal dari perspektif 'numerical linear algebra' (NLA); mungkin Anda lebih peduli dengan perspektif 'statistik terapan / psikometri' (AS / P)? Bisakah Anda mengklarifikasi?

onestop
sumber
2
Saya akan mengatakan "the" buku teks sendiri, dengan Stewart's Matrix Algorithms ( kedua bagian ) dekat. Saya akan memberikan daftar makalah perintis sendiri, tetapi OP benar-benar harus menjelaskan jika dia ingin sudut pandang angka atau sudut pandang statistik (saya bisa membantu dengan yang pertama, tetapi tidak begitu banyak yang terakhir).
JM bukan ahli statistik
1
+1 untuk Golub dan Pinjaman Van. Dan, ya, artikel definitif sesuai.
shabbychef
2
Saya mengedit pertanyaan saya untuk mengklarifikasi bahwa saya fokus pada bagian statistik. Saya setuju dengan semua orang bahwa Golub dan Van Loan adalah referensi standar untuk dekomposisi matriks. Tapi itu menghilangkan topik dekomposisi skala sangat besar melalui proyeksi acak. Makalah survei saya akan dimasukkan dalam daftar saya adalah "Mencari struktur dengan keacakan: Algoritma stokastik untuk membangun perkiraan dekomposisi matriks" oleh Halko et al.
gappy
4

Untuk NNMF, Lee dan Seung menggambarkan algoritma berulang yang sangat sederhana untuk diimplementasikan. Sebenarnya mereka memberikan dua algoritma yang sama, satu untuk meminimalkan norma residu Frobenius, yang lain untuk meminimalkan Kullback-Leibler Divergence dari pendekatan dan matriks asli.

shabbychef
sumber
3

Mungkin, Anda dapat menemukan hal yang menarik

  1. [Belajar dengan Faktor Matriks] tesis PhD oleh Nathan Srebro,
  2. [Investigasi Berbagai Metode Faktorisasi Matriks untuk Sistem Rekomendasi Besar] , Gábor Takács et.al. dan teknik yang hampir sama dijelaskan di sini

Dua tautan terakhir menunjukkan bagaimana faktorisasi matriks jarang digunakan dalam Pemfilteran Kolaboratif. Namun, saya percaya bahwa algoritma faktorisasi seperti SGD dapat berguna di tempat lain (setidaknya mereka sangat mudah dikodekan)

bijey
sumber
2

Witten, Tibshirani - Dekomposisi matriks yang dihukum

http://www.biostat.washington.edu/~dwitten/Papers/pmd.pdf

http://cran.r-project.org/web/packages/PMA/index.html

Martinsson, Rokhlin, Szlam, Tygert - SVD Acak

http://cims.nyu.edu/~tygert/software.html

http://cims.nyu.edu/~tygert/blanczos.pdf

pslice
sumber
5
Terima kasih. Saya tahu kedua makalah. Saya bukan penggemar berat Witten [not Whitten] et al., Karena saya pikir ada makalah yang lebih penting tentang dekomposisi yang jarang. Pada SVD acak, saya terutama menyukai kertas ulasan "Menemukan struktur dengan keacakan: Algoritma stokastik untuk membangun perkiraan dekomposisi matriks" ( arxiv.org/abs/0909.4061 ) juga ditulis bersama oleh Martinsson.
gappy
saya setuju. Saya hanya meletakkan di sana 2 makalah yang tidak ada yang disebutkan.
pslice
2

Pada NIPS tahun ini ada sebuah makalah pendek tentang SVD terdistribusi dan berskala sangat besar yang bekerja dalam sekali jalan melalui matriks input streaming .

Makalah ini lebih berorientasi pada implementasi tetapi menempatkan segala sesuatunya ke dalam perspektif dengan waktu dan jam dinding yang sebenarnya. Tabel di dekat awal juga merupakan survei yang bagus.

pisk
sumber
Untuk apa NIPS berdiri?
onestop
@tinggian tautan ditambahkan. NIPS = Sistem Pemrosesan Informasi Saraf Tiruan. Ini adalah komunitas (bukan sistem :)). Tapi pisk berbicara tentang konferensi NIPS 2010.
robin girard