Algorithme PCA le plus rapide pour les données de grande dimension

Je voudrais effectuer une PCA sur un ensemble de données composé d'environ 40 000 échantillons, chaque échantillon affichant environ 10 000 fonctionnalités.

L'utilisation de la fonction Matlab princomp prend systématiquement plus d'une demi-heure, moment auquel je tue le processus. Je voudrais trouver une implémentation / algorithme qui fonctionne en moins de 10 minutes. Quel serait l'algorithme le plus rapide? Combien de temps cela prendrait-il sur un Ram i7 dual core / 4 Go?

Tout d'abord, vous devez préciser si vous souhaitez tous les composants ou les plus importants?

Notons votre matrice avec N étant le nombre d'échantillons et M la dimensionnalité.$A \in \mathbb{R}^{N \times M}$$N$$M$

Dans le cas où vous souhaitez que tous les composants, la méthode classique consiste à calculer la matrice de covariance (qui a une complexité temporelle de O ( N M 2 ) ), puis à lui appliquer SVD ( O supplémentaire ( M 3 ) ). En termes de mémoire, cela prendrait O ( 2 M 2 ) (matrice de covariance + vecteurs singuliers et valeurs formant une base orthogonale) ou ≈ 1,5 Go en double précision pour votre A particulier .$C \in \mathbb{R}^{M\times M}$$O(NM^2)$$O(M^3)$$O(2M^2)$$\approx 1.5$$A$

Vous pouvez appliquer SVD directement à la matrice si vous normalisez chaque dimension avant cela et prenez des vecteurs singuliers gauches. Cependant, pratiquement je m'attendrais à ce que la SVD de la matrice A prenne plus de temps.$A$$A$

Si vous n'avez besoin que d'une fraction des composants (peut-être les plus importants), vous pouvez appliquer l' APC itérative . Pour autant que je sache, tous ces algorithmes sont étroitement liés au processus de Lanczos, vous êtes donc tributaire du spectre du et pratiquement il sera difficile d'atteindre la précision de la SVD pour les vecteurs obtenus et il se dégradera avec le nombre de vecteurs singuliers.$C$

Je suppose que vous n'avez besoin que de quelques (ou quelques centaines) paires de valeurs / vecteurs singulières dominantes. Ensuite, il est préférable d'utiliser une méthode itérative, qui sera beaucoup plus rapide et consommera beaucoup moins de mémoire.

Dans Matlab, voir

aide svds

Vous pouvez vérifier ma réponse sur Cross Validated . Je ne voulais pas le copier ici. Fondamentalement, vous pouvez utiliser un SVD rapide et aléatoire pour calculer la base et les coefficients de l'ACP.

Vous pouvez essayer l'algorithme Fast PCA qui est basé sur une manière itérative de calculer quelques vecteurs propres. Voir, A.Sharma et KK Paliwal, Fast principal component analysis using fixed-point analysis, Pattern Recognition Letters, 28, 1151-1155, 2007 .