Algoritma PCA tercepat untuk data dimensi tinggi

Saya ingin melakukan PCA pada dataset yang terdiri dari sekitar 40.000 sampel, masing-masing sampel menampilkan sekitar 10.000 fitur.

Menggunakan fungsi princomp Matlab secara konsisten membutuhkan waktu lebih dari setengah jam di mana saya mematikan proses. Saya ingin mencari implementasi / algoritma yang berjalan dalam waktu kurang dari 10 menit. Apa yang akan menjadi algoritma tercepat? Berapa lama waktu yang dibutuhkan untuk i7 dual core / 4GB Ram?

Pertama-tama, Anda harus menentukan apakah Anda ingin semua komponen atau yang paling signifikan?

Nyatakan matriks Anda dengan menjadi jumlah sampel dan dimensi N $A \in \mathbb{R}^{N \times M}$$N$$M$

Jika Anda ingin semua komponen cara klasik untuk pergi adalah menghitung matriks kovarians (yang memiliki kompleksitas waktu ) dan kemudian menerapkan SVD untuk itu (tambahan ). Dalam hal memori, ini akan membutuhkan (matriks kovarian + vektor tunggal dan nilai-nilai yang membentuk basis ortogonal) atau GB dalam presisi ganda untuk . O ( N M 2 ) O ( M 3 ) O ( 2 M 2 ) ≈ 1.5 $C \in \mathbb{R}^{M\times M}$$O(NM^2)$$O(M^3)$$O(2M^2)$$\approx 1.5$$A$

Anda bisa menerapkan SVD langsung ke matriks jika Anda menormalkan setiap dimensi sebelum itu dan mengambil vektor singular kiri. Namun, praktis saya akan mengharapkan SVD dari matriks lebih lama.$A$$A$

Jika Anda hanya membutuhkan sebagian kecil komponen (mungkin paling signifikan), Anda mungkin ingin menerapkan PCA iteratif . Sejauh yang saya tahu semua algoritma ini terkait erat dengan proses Lanczos sehingga Anda bergantung pada spektrum dan secara praktis akan sulit untuk mencapai akurasi SVD untuk vektor yang diperoleh dan akan menurun dengan jumlah vektor tunggal.$C$

Saya kira Anda hanya perlu beberapa (atau beberapa ratus) pasangan nilai / vektor singular dominan. Maka yang terbaik adalah menggunakan metode berulang, yang akan jauh lebih cepat dan mengkonsumsi memori jauh lebih sedikit.

Di Matlab, lihat

bantuan svds

Anda dapat memeriksa jawaban saya di Cross Validated . Saya tidak ingin menyalinnya di sini. Pada dasarnya, Anda dapat menggunakan SVD acak yang cepat untuk menghitung basis dan koefisien PCA.

Anda dapat mencoba algoritma PCA Cepat yang didasarkan pada cara iteratif menghitung beberapa vektor eigen. Lihat, A.Sharma dan KK Paliwal, analisis komponen utama cepat menggunakan analisis titik tetap, Pola Pengenalan Huruf, 28, 1151-1155, 2007 .