Fast Monte Carlo Algorithms for Large Matrices and Massive Data Sets

We are interested in developing and analyzing fast Monte Carlo algorithms for performing useful computations on large matrices. Examples of such computations include matrix multiplication, the computation of the Singular Value Decomposition of a matrix, the computation of compressed approximate CUR decomposition of a matrix, and testing the feasibility or infeasibility of a linear program. We present a Pass-Efficient model of data streaming computation in which our algorithms may naturally be formulated and present algorithms that are efficient within this model for each of the four types of matrix operations mentioned previously. We also discuss applications of these methods to the analysis of massive data sets. This is joint work with Petros Drineas and Ravi Kannan, and is the first of a two-part talk we are giving.
Michael W. Mahoney is currently a J. W. Gibbs Assistant Professor in the Department of Mathematics and a Research Affiliate in the Department of Computer Science at Yale University. His research interests include applied mathematics and theoretical computer science, and the application of these methods to problems in physics, chemistry, and biology involving large data sets. For example, recent work has involved the design and mathematical analysis of randomized algorithms for extremely large linear algebra problems, and the application of these algorithmic methods to the identification and extraction of structure in extremely large chemical and biological data sets. He received his Ph.D. from the Department of Physics at Yale University with a dissertation in computational liquid state statistical mechanics.