Implementing Randomized Matrix Algorithms in Parallel and Distributed Environments
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
Randomized matrix methods run in parallel and distributed settings by random-projection preconditioning and importance sampling, producing practical solvers. A Gaussian-based scheme (LSRN) projects A down to about 2n rows (γ=2), yields condition numbers ~6–10, and uses a Chebyshev semi-iterative solver to cut synchronizations; it outperforms dense LAPACK least-squares on tall matrices and scales on an Amazon EC2 cluster. L1 uses Cauchy transforms, MapReduce sampling, and ellipsoid/IPS iterations to get a few digits in few passes.
AI-written summary · about
chapters (17)
- 0:00Introduction
- 1:09Can you do largescale vector space analytics
- 2:14Why Randomized Matrix Algorithms
- 3:13Least Squares
- 4:03Overconstrained Regression
- 5:25Gaussian Elimination
- 6:09Statistical Leverage
- 11:06Bottom Line
- 12:08LSRN
- 17:53iterating
- 21:38meta
- 23:24tradeoffs
- 24:44data sets
- 25:24low precision solutions
- 25:49Inscribed ellipsoids
- 26:50Initial guesses
- 27:47Least absolute deviations
related talks
01h 31mPast, Present and Future of Randomized Numerical Linear Algebra II
32mRandomized Numerical Linear Algebra: Overview
01h 27mPast, Present and Future of Randomized Numerical Linear Algebra I
48mRandomized Numerical Linear Algebra
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
28mRandomized Constrained Matrix Decompositions
44mScalable Algorithmic Primitives for Data Science
35mRandomized Algorithms for Computing Full Matrix Factorizations