21
$\begingroup$

The Wikipedia article on principal component analysis states that

Efficient algorithms exist to calculate the SVD of $X$ without having to form the matrix $X^TX$, so computing the SVD is now the standard way to calculate a principal components analysis from a data matrix, unless only a handful of components are required.

Could someone tell me what are the efficient algorithms the article is talking about? There is no reference given (URL or citation to an article proposing this way of computation would be nice).

Improve this question
$\endgroup$
3
  • 6
    $\begingroup$ A Google search on singular value decomposition algorithm does a fine job of highlighting relevant information. $\endgroup$
    – whuber ♦
    Commented Jul 30, 2013 at 17:39
  • 2
    $\begingroup$ Don't forget to remove the mean before SVD for PCA! $\endgroup$
    – Memming
    Commented Sep 7, 2014 at 18:08
  • $\begingroup$ Try Lanczos SVD! $\endgroup$
    – ciri
    Commented Jul 3, 2015 at 15:37

1 Answer 1

Reset to default
19
$\begingroup$

The main work-horse behind the computation of SVD is the QR algorithm. Having said that there are many different algorithms to calculate the singular value decomposition of a generic $M$-by-$N$ matrix $A$. A great schematic on the issue available here (from the documentation of Intel's MKL) is the following: enter image description here

As you see depending on your use case there are different approaches (the routine naming conventions can be found here). That is because, for example there are matrix forms where a Householder reduction can be more expensive than a Givens rotation (to name two "obvious" way of getting QR). A standard reference on the matter is Golub's and Van Loan's Matrix Computations (I would suggest using at least the 3rd edition). I have also found Å. Björck's Numerical Methods for Least Squares Problems very good resource on that matter; while SVD is not the primary focus of the book it helps contextualizing the use it.

If I have to give you one general advice on the matter is do not try to write your own SVD algorithms unless you have successfully taken a couple of classes on Numerical Linear Algebra already and you know what you are doing. I know it sounds counter-intuitive but really, there as a tonne of stuff that can go wrong and you ending up with (at best) sub-optimal implementations (if not wrong). There some very good free suites on the matter (eg. Eigen, Armadillo and Trilinos to name a few.)

Improve this answer
$\endgroup$
8
  • $\begingroup$ The question was about computing SVD of the data matrix, not of its covariance matrix (using your notation, $X$, not $A$). Isn't QR algorithm applicable only to square matrices? If so, then how can it help computing SVD of the (non-square) data matrix? $\endgroup$
    – amoeba
    Commented Sep 7, 2014 at 22:16
  • 2
    $\begingroup$ Fixed. QR-based approaches (and LQ) are used in all cases; QR is not restricted to square matrices. The algorithms linked are for a general $M$-by-$N$ matrix $A$. The OP is inquiring within the context of PCA where the matrix $X^TX$ is relevant. $\endgroup$
    – usεr11852
    Commented Sep 8, 2014 at 7:30
  • 2
    $\begingroup$ Yep, I was wrong: QR is not restricted to square matrices. +1, by the way. This question was one of the highest voted unanswered questions with the pca tag, so it is nice to see it finally answered. $\endgroup$
    – amoeba
    Commented Sep 8, 2014 at 13:01
  • $\begingroup$ Your answer does not mention a whole variety of iterative algorithms. Was it on purpose? Somebody asked a question about iterative SVD algorithms, see What fast algorithms exist for computing truncated SVD?, and I posted an answer there trying to provide some overview. Perhaps we should at least cross-link our answers. And it would certainly be great if you can expand yours by some discussion of QR algorithms vs. iterative algorithms. $\endgroup$
    – amoeba
    Commented Jul 2, 2015 at 15:47
  • $\begingroup$ No, it was accidental. You answered your own question in your post though; truncated SVD are essentially truncated eigendecompositions (see for example ARPACK). There are some fine differences but they are fine; some software (eg. MATLAB's svds) go as far as simply using their truncated SVD function as a wrapper for their truncated eigendecomposition (eigs) routines. $\endgroup$
    – usεr11852
    Commented Jul 2, 2015 at 22:40

Your Answer

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

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