19

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).

amoeba
  • 93,463
  • 28
  • 275
  • 317
svd
  • 191
  • 1
  • 3

1 Answers1

16

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.)

usεr11852
  • 33,608
  • 2
  • 75
  • 117
  • 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? – amoeba Sep 07 '14 at 22:16
  • 1
    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. – usεr11852 Sep 08 '14 at 07:30
  • 2
    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 [tag:pca] tag, so it is nice to see it finally answered. – amoeba Sep 08 '14 at 13:01
  • 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?](http://stats.stackexchange.com/questions/159325), 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. – amoeba Jul 02 '15 at 15:47
  • No, it was accidental. You answered your own question in your post though; truncated SVD are essentially truncated eigendecompositions (see for example [ARPACK](http://www.caam.rice.edu/software/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. – usεr11852 Jul 02 '15 at 22:40
  • I will look into writing a few sentences on the mater in next couple of weeks. (I have been extremely busy this month - you can see I haven't answer anything in weeks.) – usεr11852 Jul 02 '15 at 22:44
  • Did you mean to link to https://en.wikipedia.org/wiki/QR_algorithm instead of to the QR decomposition? Thanks – wlad Dec 21 '20 at 10:40
  • I don't remember my Sept 2014 intentions, sorry. :) But I prefer the link to the QR decomposition; it emphasises the generality of QR decomposition how much of a central concept it is as well as clearly links to the QR algorithm for a particular implementation. – usεr11852 Dec 21 '20 at 11:04