Speaker: Prof. Joel A. Tropp, Department of Computing and Mathematical Sciences, California Institute of Technology, Pasadena, California
Location: LSK 301
Intended Audience: Public
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. This is joint work with Gunnar Martinsson and Nathan Halko (the paper is available here).
Joel A. Tropp is Assistant Professor of Applied & Computational Mathematics at the California Institute of Technology. He earned the Ph.D. degree in Computational Applied Mathematics from the University of Texas at Austin in 2004. Dr. Tropp’s work lies at the interface of applied mathematics, electrical engineering, computer science, and statistics. The bulk of this research concerns the theoretical and computational aspects of sparse approximation, compressive sampling, and randomized linear algebra. He has also worked extensively on the properties of structured random matrices. Dr. Tropp has received several major awards for young researchers, including the 2007 ONR Young Investigator Award and the 2008 Presidential Early Career Award for Scientists and Engineers. He is also winner of the 6th Vasil A. Popov prize and the 2011 Monroe H. Martin prize.