There exists a simple, efficient randomized algorithm for computing an approximation to a singular value decomposition (SVD) of a matrix A for which representations enabling the rapid application of both A and the transpose of A are available. The algorithm has a negligible probability of failure (1e-17 is typical), and, unlike the classical Lanczos method for computing approximations to SVDs, operates reliably independently of the structure of the matrix A. The accuracy of the rank-k approximation which the algorithm constructs is of the same order as the accuracy of the best possible rank-k approximation.
This talk is for non-experts – anyone who would not like to browse the full article on the topic, which is available at the very bottom of http://www.cs.yale.edu/~tygert
The talk is somewhat like a caboose to Professor Coifman’s talk from mid-October.