Finding Structure with Randomness: Probabilistic Algorithms for Constructing Low-Rank Matrix Decompositions

Start: 10/26/2011 - 1:00pm
End  : 10/26/2011 - 2:00pm

Applied Math Seminar

Joel Tropp, California Institute of Technology


Finding structure with randomness: Probabilistic algorithms for
constructing low-rank matrix decompositions

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

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


Bauer Court (BC) 24, in CMC