PCA terlalu lambat ketika keduanya n, p besar: Alternatif?

Pengaturan Masalah

Saya memiliki titik data (gambar) dimensi tinggi (4096), yang saya coba visualisasikan dalam 2D. Untuk tujuan ini, saya menggunakan t-sne dengan cara yang mirip dengan kode contoh berikut oleh Karpathy .

The scikit-belajar dokumentasi merekomendasikan menggunakan PCA untuk pertama menurunkan dimensi dari data:

Sangat disarankan untuk menggunakan metode pengurangan dimensionalitas lain (mis. PCA untuk data padat atau TruncatedSVD untuk data jarang) untuk mengurangi jumlah dimensi ke jumlah yang masuk akal (mis. 50) jika jumlah fitur sangat tinggi.

Saya menggunakan kode ini oleh Darks.Liu untuk melakukan PCA di Java:

//C=X*X^t / m
DoubleMatrix covMatrix = source.mmul(source.transpose()).div(source.columns);
ComplexDoubleMatrix eigVal = Eigen.eigenvalues(covMatrix);
ComplexDoubleMatrix[] eigVectorsVal = Eigen.eigenvectors(covMatrix);
ComplexDoubleMatrix eigVectors = eigVectorsVal[0];
//Sort sigen vector from big to small by eigen values 
List<PCABean> beans = new ArrayList<PCA.PCABean>();
for (int i = 0; i < eigVectors.columns; i++) {
    beans.add(new PCABean(eigVal.get(i).real(), eigVectors.getColumn(i)));
}
Collections.sort(beans);
DoubleMatrix newVec = new DoubleMatrix(dimension, beans.get(0).vector.rows);
for (int i = 0; i < dimension; i++) {
    ComplexDoubleMatrix dm = beans.get(i).vector;
    DoubleMatrix real = dm.getReal();
    newVec.putRow(i, real);
}
return newVec.mmul(source);

Ini menggunakan jblas untuk operasi aljabar linier, yang dari apa yang saya baca seharusnya menjadi pilihan tercepat di luar sana. Namun, menghitung vektor eigen dan nilai eigen (baris 3,4) ternyata menjadi hambatan besar (~ 10 menit, yang jauh lebih lama daripada yang saya mampu untuk tahap ini).

$O(n^3)$

Seperti yang saya lihat, pilihan saya adalah "mengoptimalkan" PCA atau memilih metode pengurangan dimensi lain yang secara inheren lebih cepat.

Pertanyaan saya

1. Apakah ada harapan bahwa PCA dapat digunakan dalam mode "offline"? yaitu, menggunakan satu set data yang besar gambar, melakukan PCA pada mereka, dan kemudian menggunakan komponen utama dihitung bagi mereka untuk mengurangi dimensi lain (baru!) titik data?
2. Dapatkah saya mempercepat perhitungan vektor eigen, dengan asumsi saya tahu sebelumnya bahwa saya hanya tertarik pada, katakanlah, 100 komponen utama teratas?
3. Apakah ada metode pengurangan dimensi alternatif yang sesuai dalam kasus saya (yaitu, sebelum menerapkan t-sne) yang akan lebih cepat daripada PCA? Saya mencari sesuatu yang dapat diimplementasikan dengan mudah di Jawa.

$X \in \mathbb R^{n \times p}$$X^T X = Q \Lambda Q^T$$Z \in \mathbb R^{m \times p}$$ZQ$$Z$, dan teori perturbasi matriks secara umum (jika Anda bisa mendapatkan salinan, buku teks Stewart dan Sun 1990 adalah referensi standar).

$k$rARPACK

Pertanyaan 3: Saya tidak tahu apa-apa tentang implementasi Java, tetapi utas ini membahas mempercepat PCA seperti halnya utas CV ini . Ada banyak penelitian tentang hal semacam ini dan ada banyak metode di luar sana menggunakan hal-hal seperti perkiraan peringkat rendah atau pengacakan.

Kode yang Anda gunakan akan membalikkan seluruh matriks. Ini mungkin O (p ^ 3) sudah. Anda dapat memperkirakan hasilnya dalam O (p ^ 2) tetapi itu masih lambat (tapi mungkin 100x lebih cepat). Intinya, ambil vektor sembarang dan lakukan iterasi daya. Dengan probabilitas tinggi, Anda akan mendapatkan perkiraan yang baik dari vektor eigen pertama. Kemudian hapus faktor ini dari matriks, ulangi untuk mendapatkan yang kedua. Dll

Tetapi apakah Anda sudah mencoba jika implementasi tSNE Barnes Hut cepat di ELKI mungkin hanya akan bekerja pada data Anda dengan indeks seperti pohon penutup? Implementasi saya berjalan dengan baik ketika orang lain gagal.

mlib$n \times K$$K \times p$$K \times p$