Bagaimana cara menghitung SVD dari matriks jarang yang besar?

26

Apa cara terbaik untuk menghitung dekomposisi nilai singular (SVD) dari matriks positif yang sangat besar (65M x 3.4M) di mana data sangat jarang?

Kurang dari 0,1% dari matriks adalah nol. Saya butuh cara itu:

  • akan masuk ke dalam memori (saya tahu bahwa ada metode online)
  • akan dihitung dalam waktu yang wajar: 3,4 hari
  • akan cukup akurat namun akurasi bukan perhatian utama saya dan saya ingin dapat mengontrol berapa banyak sumber daya yang saya masukkan ke dalamnya.

Akan sangat bagus untuk memiliki perpustakaan Haskell, Python, C # dll yang mengimplementasikannya. Saya tidak menggunakan mathlab atau R tetapi jika perlu saya bisa menggunakan R.

svd numerics Sonia
sumber
3
Berapa banyak memori yang Anda miliki? 0,1% dari 65M * 3,4M masih 221e9 bukan nilai nol. Jika Anda menggunakan 4 byte per nilai, itu masih lebih dari 55 gb dengan asumsi tidak ada overhead, jadi sparsity masih tidak menyelesaikan masalah ... Apakah Anda perlu memuat seluruh set ke memori sekaligus?
Bitwise
Saya seharusnya lebih tepat. Tidak lebih dari 250-500mb dengan integer 32-bit. Mungkin jauh lebih sedikit, tetapi dimensionalilty adalah masalah yang saya mengerti. Saya memiliki mesin 16GB.
Sonia
Bagaimana dengan ini? quora.com/…
Bitwise
Halaman web ini terhubung ke pustaka Python yang mengimplementasikan "algoritma SVD cepat, inkremental, memori rendah, matriks besar": en.wikipedia.org/wiki/Latent_semantic_analysis
Bitwise
Lihat juga stats.stackexchange.com/questions/2806 .
Amuba kata Reinstate Monica

Jawaban:

21

Jika cocok dengan memori, buat matriks jarang dalam R menggunakan paket Matrix , dan coba irlba untuk SVD. Anda dapat menentukan berapa banyak vektor tunggal yang Anda inginkan dalam hasilnya, yang merupakan cara lain untuk membatasi perhitungan.

Itu matriks yang cukup besar, tapi saya sudah mendapatkan hasil yang sangat baik dengan metode ini di masa lalu. irlbacukup canggih. Ini menggunakan algoritma bi-diagonisasi Lanczos yang dimulai kembali secara implisit .

Itu dapat mengunyah dataset hadiah Netflix (480.189 baris dengan 17.770 kolom, 100.480.507 entri tidak nol) dalam milidetik. Dataset Anda ~ 200.000 kali lebih besar dari dataset Netflix, jadi butuh waktu lebih lama dari itu. Mungkin masuk akal untuk berharap bahwa ia dapat melakukan perhitungan dalam beberapa hari.

Zach
sumber
matriks data cocok dengan memori, apakah irlba akan menangani dekomposisi dengan cara yang efisien memori juga?
Sonia
@Onia: irlba sangat hemat memori: ia menghitung solusi perkiraan, Anda dapat membatasi jumlah vektor tunggal, dan itu dirancang untuk bekerja pada matriks jarang. Sejauh yang saya tahu, ini secepat yang Anda dapatkan untuk menghitung sebagian SVD.
Zach
@Onia: Semoga beruntung!
Zach
Memberi ini uji coba memori ... Saya akan menghitung bentuk blok segitiga sebelum menjalankannya.
Sonia
@Onia apakah Anda menyimpannya jarang Matrix? Coba batasi jumlah nilai tunggal yang Anda hitung ... mungkin hanya melihat 10 besar?
Zach