11
$\begingroup$

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 ?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$
    – mellow
    Sep 5, 2012 at 18:49
  • $\begingroup$ How sparse is your matrix? $\endgroup$
    – Arnold Neumaier
    Sep 7, 2012 at 7:06
  • $\begingroup$ The percentage of zeros in the matrix is above 80% $\endgroup$
    – mellow
    Sep 7, 2012 at 7:27
  • $\begingroup$ Check out kernal-PCA also. $\endgroup$
    – meawoppl
    Sep 7, 2012 at 19:06

4 Answers 4

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Yes it seems that iterative methods are way faster if I only need the first hundred components. $\endgroup$
    – mellow
    Sep 7, 2012 at 7:53
  • $\begingroup$ 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 ... $\endgroup$
    – mellow
    Sep 7, 2012 at 7:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – Arnold Neumaier
    Sep 7, 2012 at 8:06
  • 2
    $\begingroup$ Also of note for the dominant modes are newer randomized svd methods, as in stanford.edu/group/mmds/slides2010/Martinsson.pdf $\endgroup$
    – Nick Alger
    Sep 8, 2012 at 5:00
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.