Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

A classical problem in matrix computations is the efficient and reliable approximation of a given matrix by a lower ranked one, with applications throughout wide areas of computational sciences and engineering. The truncated singular value decomposition (SVD) is known to provide the best such approximation for any given fixed rank. However, the SVD is also known to be very costly to compute. Among the different approaches in the literature for computing low-rank approximations, randomized algorithms have attracted researchers' recent attention due to their surprising reliability and computational efficiency in different application areas. In this talk, we develop a novel error analysis that considers randomized algorithms within the subspace iteration framework and show with near certainty that highly accurate low-rank approximations as well as singular values can indeed be computed quickly for matrices with rapidly decaying singular values. Such matrices appear frequently in diverse application areas such as data analysis, fast structured matrix computations and fast direct methods for large sparse linear systems of equations and are the driving motivation for randomized methods. Furthermore, we show that the low-rank approximations computed by these randomized algorithms are actually rank-revealing approximations, and the special case of a rank-1 approximation can also be used to correctly estimate matrix 2-norms with near certainty. Our numerical experiments are in full support of our conclusions.