# Fastest PCA algorithm for high-dimensional data

I would like to perform a PCA on a dataset composed of approximately 40 000 samples, each sample displaying about 10 000 features.

Using Matlab princomp function consistently takes over half an hour at which point I kill the process. I would like to find an implementation/algorithm that runs in less than 10 minutes. What would be the fastest algorithm ? How long would it take on a i7 dual core / 4GB Ram ?

-
Yes, you are right, I should be more precise. It takes more than half hour, then I decided to kill the process. I have to do this at least ten times, do it would be nice to have something that works in less than 10 minutes –  mellow Sep 5 '12 at 18:49
How sparse is your matrix? –  Arnold Neumaier Sep 7 '12 at 7:06
The percentage of zeros in the matrix is above 80% –  mellow Sep 7 '12 at 7:27
Check out kernal-PCA also. –  meawoppl Sep 7 '12 at 19:06

## 4 Answers

First of all, you should specify whether you want all components or the most significant ones?

Denote your matrix $A \in \mathbb{R}^{N \times M}$ with $N$ being number of samples and $M$ dimensionality.

In case you want all components the classical way to go is to compute covariance matrix $C \in \mathbb{R}^{M\times M}$ (which has time complexity of $O(NM^2)$) and then apply SVD to it (additional $O(M^3)$). In terms of memory this would take $O(2M^2)$ (covariance matrix + singular vectors and values forming orthogonal basis) or $\approx 1.5$ GB in double precision for your particular $A$.

You could apply SVD directly to the matrix $A$ if you normalize each dimension prior to that and take left singular vectors. However, practically I would expect SVD of the matrix $A$ to take longer.

If you need only a fraction of (perhaps most significant) components you may want to apply iterative PCA. As far as I know all these algorithms are closely related to Lanczos process thus you are dependent on the spectrum of the $C$ and practically it will be difficult to achieve accuracy of SVD for obtained vectors and it will degrade with the number of singular vector.

-

I guess you only need a few (or a few hundred) dominant singular value/vector pairs. Then it is best to use an iterative method, which will be much faster and consume far less memory.

In Matlab, see

help svds

-
Yes it seems that iterative methods are way faster if I only need the first hundred components. –  mellow Sep 7 '12 at 7:53
As far as the svds is concerned, I tried to put my matrix into a sparse format and modify the princomp function to put svds instead of svd, and to my surprise it took much longer on a 2000*4000 matrix (180 s instead of 15s). Bizarre ... –  mellow Sep 7 '12 at 7:55
There is no need to switch to the sparse format. Also, you need to reduce the number of singular vectors you want to compute. For computing the fiull svd, svds is not suitable. –  Arnold Neumaier Sep 7 '12 at 8:06
Also of note for the dominant modes are newer randomized svd methods, as in stanford.edu/group/mmds/slides2010/Martinsson.pdf –  Nick Alger Sep 8 '12 at 5:00

You can try the Fast PCA algorithm which is based on an iterative way of computing a few eigenvectors. See, A.Sharma and K.K. Paliwal, Fast principal component analysis using fixed-point analysis, Pattern Recognition Letters, 28, 1151-1155, 2007.

-

You may check my answer on Cross Validated. I didn't want to copy it here. Basically, you can use fast, randomized SVD to compute PCA basis and coefficients.

-