When

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

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

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

Category

Applied Math Seminar

Speaker

Joel Tropp, California Institute of Technology

Abstract

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

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

http://users.cms.caltech.edu/~jtropp/papers/HMT11-Finding-Structure-SIRE...

Where

Bauer Court (BC) 24, in CMC