Applied Mathematics Colloquium
Finding structure with randomness: Probabilistic algorithms for constructing low-rank matrix decompositions
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 withor even outperformclassical 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