Implementing Randomized Matrix Algorithms in Parallel and Distributed Environments, Michael Mahoney

• Report rights infringement
• published: 24 Aug 2012
• views: 1535

Implementing Randomized Matrix Algorithms in Parallel and Distributed Environments Michael W. Mahoney, Stanford University Motivated by problems in large-scale data analysis, random- ized algorithms for matrix problems such as regression and low-rank matrix approximation have been the focus of a great deal of attention in recent years. These algorithms exploit novel random sampling and random projection meth- ods; and implementations of these algorithms have already proven superior to traditional state-of-the-art algorithms, as implemented in Lapack and high-quality scientific comput- ing software, for moderately-large problems stored in RAM on a single machine. Here, we describe the extension of these methods to computing high-precision solutions in par- allel and distributed environments that are more common in very large-scale data analysis applications. In particular, we consider both the Least Squares Approx- imation problem and the Least Absolute Deviation prob- lem, and we develop and implement randomized algorithms that take advantage of modern computer architectures in order to achieve improved communication profiles. Our iterative least-squares solver, LSRN, is competitive with state-of-the-art implementations on moderately-large prob- lems; and, when coupled with the Chebyshev semi-iterative method, scales well for solving large problems on clusters that have high communication costs such as on an Amazon Elastic Compute Cloud cluster. Our iterative least-absolute- deviations solver is based on fast ellipsoidal rounding, ran- dom sampling, and interior-point cutting-plane methods; and we demonstrate significant improvements over tradi- tional algorithms on MapReduce. In addition, this algorithm can also be extended to solve more general convex problems on MapReduce. MMDS 2012. Workshop on Algorithms for Modern Massive Data Sets Stanford University July 10--13, 2012 Synopsis The Workshops on Algorithms for Modern Massive Data Sets (MMDS 2012) addressed algorithmic and statistical challenges in modern large-scale data analysis. The goals of this series of workshops are to explore novel techniques for modeling and analyzing massive, high-dimensional, and nonlinearly-structured scientific and internet data sets; and to bring together computer scientists, statisticians, mathematicians, and data analysis practitioners to promote the cross-fertilization of ideas. Videotaping sponsored by Cloudera