Paved with Good Intentions: Analysis of a Randomized Block Kaczmarz Method

Abstract

The block Kaczmarz method is an iterative scheme for solving overdetermined least-squares problems. At each step, the algorithm projects the current iterate onto the solution space of a subset of the constraints. This paper describes a block Kaczmarz algorithm that uses a randomized control scheme to choose the subset at each step. This algorithm is the first block Kaczmarz method with an (expected) linear rate of convergence that can be expressed in terms of the geometric properties of the matrix and its submatrices. The analysis reveals that the algorithm is most effective when it is given a good row paving of the matrix, a partition of the rows into well-conditioned blocks. The operator theory literature provides detailed information about the existence and construction of good row pavings. Together, these results yield an efficient block Kaczmarz scheme that applies to many overdetermined least-squares problem.

References in corpus (4)

• Randomized Extended Kaczmarz for Solving Least-Squares
• Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences
• Restricted Invertibility and the Banach-Mazur distance to the cube
• Improved matrix algorithms via the Subsampled Randomized Hadamard Transform

Cited by in corpus (60)

• Randomized Iterative Methods for Linear Systems
• Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
• Stochastic Dual Ascent for Solving Linear Systems
• On the Randomized Kaczmarz Algorithm
• The Practicality of Stochastic Optimization in Imaging Inverse Problems
• Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm
• Inexact Coordinate Descent: Complexity and Preconditioning
• Randomized Numerical Linear Algebra: Foundations & Algorithms
• Convergence of the randomized Kaczmarz method for phase retrieval
• A Kaczmarz-inspired approach to accelerate the optimization of neural network wavefunctions
• Adaptively Sketched Bregman Projection Methods for Linear Systems
• A deterministic Kaczmarz algorithm for solving linear systems
• On the exponential convergence of the Kaczmarz algorithm
• Breaking Locality Accelerates Block Gauss-Seidel
• Convergence Rates for Greedy Kaczmarz Algorithms, and Faster Randomized Kaczmarz Rules Using the Orthogonality Graph
• On Block Accelerations of Quantile Randomized Kaczmarz for Corrupted Systems of Linear Equations
• A fast randomized Kaczmarz algorithm for sparse solutions of consistent linear systems
• Sketch and Project: Randomized Iterative Methods for Linear Systems and Inverting Matrices
• A Kaczmarz Method with Simple Random Sampling for Solving Large Linear Systems
• On the fast convergence of minibatch heavy ball momentum
• Stochastic Newton and Quasi-Newton Methods for Large Linear Least-squares Problems
• Sparse Sampling Kaczmarz-Motzkin Method with Linear Convergence
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent
• Sampled Limited Memory Methods for Massive Linear Inverse Problems
• On the relaxed greedy deterministic row and column iterative methods
• An accelerated randomized Bregman-Kaczmarz method for strongly convex linearly constraint optimization
• Randomized extended block Kaczmarz for solving least squares
• On block Gaussian sketching for the Kaczmarz method
• Linear convergence of the Randomized Sparse Kaczmarz Method
• Greed Works: An Improved Analysis of Sampling Kaczmarz-Motzkin
• A doubly stochastic block Gauss-Seidel algorithm for solving linear equations
• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip
• Heavy Ball Momentum Induced Sampling Kaczmarz Motzkin Methods for Linear Feasibility Problems
• Greedy Block Coordinate Descent (GBCD) Method for High Dimensional Quadratic Programs
• On the extended randomized multiple row method for solving linear least-squares problems
• Preconditioning in Expectation
• Deterministic Versus Randomized Kaczmarz Iterative Projection
• Linear Discriminant Analysis with the Randomized Kaczmarz Method
• Accelerating Random Kaczmarz Algorithm Based on Clustering Information
• Randomized Kaczmarz for Tensor Linear Systems
• Stochastic Iterative Methods for Online Rank Aggregation from Pairwise Comparisons
• Randomized Extended Kaczmarz is a Limit Point of Sketch-and-Project
• Preconvergence of the randomized extended Kaczmarz method
• Phase retrieval of complex-valued objects via a randomized Kaczmarz method
• Sampling Kaczmarz Motzkin Method for Linear Feasibility Problems: Generalization & Acceleration
• A Linearly Convergent Doubly Stochastic Gauss-Seidel Algorithm for Solving Linear Equations and A Certain Class of Over-Parameterized Optimization Problems
• Randomized Block Kaczmarz Method with Projection for Solving Least Squares
• Single Projection Kaczmarz Extended Algorithms
• Preconditioning Kaczmarz method by sketching
• On Application of Block Kaczmarz Methods in Matrix Factorization
• Block Kaczmarz Method with Inequalities
• On the alternating randomized block Kaczmarz method
• Fusion frames and randomized subspace actions
• A New Perspective on Randomized Gossip Algorithms
• Sketch-and-project methods for tensor linear systems
• A Note On The Randomized Kaczmarz Method With A Partially Weighted Selection Step
• Block sampling Kaczmarz-Motzkin methods for consistent linear systems
• Kaczmarz Algorithm with Soft Constraints for User Interface Layout
• Regularized Kaczmarz Algorithms for Tensor Recovery
• Refined upper bounds for the convergence of the randomized extended Kaczmarz and Gauss-Seidel algorithms