Schnellster PCA-Algorithmus für hochdimensionale Daten

Ich möchte eine PCA für einen Datensatz durchführen, der aus ungefähr 40 000 Proben besteht, wobei jede Probe ungefähr 10 000 Merkmale aufweist.

Die Verwendung der Matlab-Princomp-Funktion dauert durchweg über eine halbe Stunde. An diesem Punkt beende ich den Prozess. Ich möchte eine Implementierung / einen Algorithmus finden, der / der in weniger als 10 Minuten ausgeführt wird. Was wäre der schnellste Algorithmus? Wie lange würde ein i7 Dual Core / 4 GB RAM dauern?

Zunächst sollten Sie angeben, ob Sie alle oder die wichtigsten Komponenten möchten.

Bezeichnen Sie Ihre Matrix wobei N die Anzahl der Abtastwerte und die M- Dimensionalität ist.$A \in \mathbb{R}^{N \times M}$$N$$M$

Wenn Sie alle Komponenten möchten, besteht der klassische Weg darin, die Kovarianzmatrix (mit einer Zeitkomplexität von O ( N M 2 ) ) zu berechnen und dann SVD darauf anzuwenden (zusätzliches O ( M 3 ) ). In Bezug auf den Speicher würde dies O ( 2 M 2 ) (Kovarianzmatrix + singuläre Vektoren und Werte, die eine orthogonale Basis bilden) oder ≈ 1,5 GB mit doppelter Genauigkeit für Ihr spezielles A benötigen .$C \in \mathbb{R}^{M\times M}$$O(NM^2)$$O(M^3)$$O(2M^2)$$\approx 1.5$$A$

Sie können SVD direkt auf die Matrix anwenden, wenn Sie jede Dimension zuvor normalisieren und linke Singularvektoren verwenden. Praktisch würde ich jedoch erwarten, dass die SVD der Matrix A länger dauert.$A$$A$

Wenn Sie nur einen Bruchteil der (möglicherweise wichtigsten) Komponenten benötigen, möchten Sie möglicherweise iterative PCA anwenden . Soweit ich weiß, sind alle diese Algorithmen eng mit dem Lanczos-Prozess verbunden, daher sind Sie vom Spektrum des abhängig, und es wird praktisch schwierig sein, die Genauigkeit der SVD für erhaltene Vektoren zu erreichen, und sie wird sich mit der Anzahl der singulären Vektoren verschlechtern.$C$

Ich denke, Sie brauchen nur ein paar (oder ein paar hundert) dominante Singularwert / Vektor-Paare. Dann ist es am besten, eine iterative Methode zu verwenden, die viel schneller ist und viel weniger Speicher verbraucht.

In Matlab siehe

Hilfe svds

Sie können meine Antwort auf Cross Validated überprüfen . Ich wollte es hier nicht kopieren. Grundsätzlich können Sie eine schnelle, randomisierte SVD verwenden, um die PCA-Basis und -Koeffizienten zu berechnen.

Sie können den Fast PCA-Algorithmus ausprobieren, der auf einer iterativen Methode zur Berechnung einiger Eigenvektoren basiert. Siehe A. Sharma und KK Paliwal, Schnelle Hauptkomponentenanalyse unter Verwendung einer Festpunktanalyse, Pattern Recognition Letters, 28, 1151-1155, 2007 .