Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions

ABSTRACT:

Low-rank matrix approximations, such as partial spectral decompositions, play a central role in data analysis and scientific computing. The talk will describe a set of recently developed randomized algorithms for computing such approximations. These techniques exploit modern computational architectures more fully than classical methods and open the possibility of dealing with truly massive data sets.

The algorithms described are supported by a rigorous mathematical analysis that exploits recent work in random matrix theory. The talk will briefly review some of the key techniques involved.