An Algebraic View of the New Randomized Kaczmarz Linear Solver
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
Claims a solver that turns an n-by-n Laplacian into a larger m-by-m square system so randomized Kaczmarz (Kaczmar/Casmaj) runs provably fast by choosing a low-stretch spanning tree to build a null-space basis via path embedding; each Kaczmarz update reduces one row and is implemented with an implicit flow data structure (a simple instantiation of dynamic trees) giving O(log n) update cost. Convergence depends on tree stretch so total work is linear in edges but with large constants and a highly sequential iteration order, so current experiments show correctness but slow practical performance.
AI-written summary · about
chapters (15)
- 0:00Intro
- 3:32Problem Setup (More Structure)
- 3:58Laplacians of Graphs
- 4:52Direct Solvers do not Scale Well
- 6:39Conjugate Gradients (and Variants)
- 8:32The Idea of Preconditioning (Still Ancient)
- 10:26Combinatorial Subgraph Preconditioners
- 11:43Reasoning about Convergence Rates: Incidence Factors
- 14:37Constructing the Subgraph
- 17:59The Big Picture
- 21:37Kaczmarz and our Augmented System
- 23:14Constructing the Null-Space Basis
- 25:04Convergence of Randomized Kaczmarz
- 25:45The Condition Number of the Null-Space Basis
- 27:39Super-Efficient Projections (IT): The Key Idea
related talks
39mSketching and Randomization for Distributed Submodular and Coverage Optimization
47mMultiscale Analysis on and of Graphs
19mDeterministic Dynamic Matching In Worst-Case Update Time
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
29mImproved Deterministic Algorithms for Sparse Max-SAT
46mDistributed Graph Techniques in the MPC Model
01h 05mRandom Walks on Simplicial Complexes for Exploring Networks
01h 05mGraph Algorithms in the MPC Model