skip to main content

Applied Mathematics Colloquium

Monday, January 23, 2012
4:15pm to 5:15pm
Add to Cal
Annenberg 105
Finding structure with randomness: Probabilistic algorithms for constructing low-rank matrix decompositions
Joel Tropp, Assistant Professor, Computing & Mathematical Sciences, Caltech,
Computer scientists have long known that randomness can be used to improve the performance of algorithms. A familiar application is the process of dimension reduction, in which a random map transports data from a high-dimensional space to a lower-dimensional space while approximately preserving some geometric properties. By operating with the compact representation of the data, it is theoretically possible to produce approximate solutions to certain large problems very efficiently.

Recently, it has been observed that dimension reduction has powerful applications in numerical linear algebra and numerical analysis. This talk provides a high-level introduction to randomized methods for computing standard matrix approximations, and it summarizes a new analysis that offers (nearly) optimal bounds on the performance of these methods. In practice, the techniques are so effective that they compete with or even outperform classical algorithms. Since matrix approximations play a ubiquitous role in areas ranging from information processing to scientific computing, it seems certain that randomized algorithms will eventually supplant the standard methods in some application domains.

Joint work with Gunnar Martinsson and Nathan Halko. The paper is available at
For more information, please contact Sydney Garstang by phone at x4555 or by email at [email protected] or visit