What are efficient algorithms to compute singular value decomposition (SVD)?

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

• A Google search on singular value decomposition algorithm does a fine job of highlighting relevant information.
– whuber
Jul 30 '13 at 17:39
• Don't forget to remove the mean before SVD for PCA! Sep 7 '14 at 18:08
• Try Lanczos SVD!
– ciri
Jul 3 '15 at 15:37

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:
• 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? Sep 7 '14 at 22:16
• 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. Sep 8 '14 at 7:30
• 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. Jul 2 '15 at 22:40