# 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
Commented Jul 30, 2013 at 17:39
• Don't forget to remove the mean before SVD for PCA! Commented Sep 7, 2014 at 18:08
• Try Lanczos SVD!
– ciri
Commented Jul 3, 2015 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? Commented Sep 7, 2014 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. Commented Sep 8, 2014 at 7:30