Faster randomized block Kaczmarz algorithms
From MaRDI portal
Abstract: The Kaczmarz algorithm is a simple iterative scheme for solving consistent linear systems. At each step, the method projects the current iterate onto the solution space of a single constraint. Hence, it requires very low cost per iteration and storage, and it has a linear rate of convergence. Distributed implementations of Kaczmarz have become, in recent years, the de facto architectural choice for large-scale linear systems. Therefore, in this paper we develop a family of randomized block Kaczmarz algorithms that uses at each step a subset of the constraints and extrapolated stepsizes, and can be deployed on distributed computing units. Our approach is based on several new ideas and tools, including stochastic selection rule for the blocks of rows, stochastic conditioning of the linear system, and novel strategies for designing extrapolated stepsizes. We prove that randomized block Kaczmarz algorithm converges linearly in expectation, with a rate depending on the geometric properties of the matrix and its submatrices and on the size of the blocks. Our convergence analysis reveals that the algorithm is most effective when it is given a good sampling of the rows into well-conditioned blocks. Besides providing a general framework for the design and analysis of randomized block Kaczmarz methods, our results resolve an open problem in the literature related to the theoretical understanding of observed practical efficiency of extrapolated block Kaczmarz methods.
Recommendations
- An accelerated randomized Kaczmarz algorithm
- A randomized Kaczmarz algorithm with exponential convergence
- Faster randomized block sparse Kaczmarz by averaging
- Randomized block Kaczmarz method with projection for solving least squares
- An accelerated randomized Kaczmarz method via low-rank approximation
Cites work
- scientific article; zbMATH DE number 3027894 (Why is no real title available?)
- A randomized Kaczmarz algorithm with exponential convergence
- Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
- An accelerated randomized Kaczmarz algorithm
- Block Kaczmarz method with inequalities
- Block-iterative methods for consistent and inconsistent linear equations
- Chebyshev semi-iterative methods, successive overrelaxation iterative methods, and second order Richardson iterative methods. I, II
- Column subset selection, matrix factorization, and eigenvalue optimization
- Decomposition through formalization in a product space
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Extrapolation algorithm for affine-convex feasibility problems
- Improved analysis of the subsampled randomized Hadamard transform
- Iterative methods for linear systems. Theory and applications
- Nonasymptotic convergence of stochastic proximal point methods for constrained convex optimization
- On a relaxation method of solving systems of linear inequalities
- On the acceleration of Kaczmarz's method for inconsistent linear systems
- On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints
- Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Random minibatch subgradient algorithms for convex problems with functional constraints
- Randomized block Kaczmarz method with projection for solving least squares
- Randomized extended Kaczmarz for solving least squares
- Randomized iterative methods for linear systems
- Randomized methods for linear constraints: convergence rates and conditioning
- Randomized projection methods for convex feasibility: conditioning and convergence rates
- Robust Stochastic Approximation Approach to Stochastic Programming
- Row-Action Methods for Huge and Sparse Systems and Their Applications
- Stochastic reformulations of linear systems: algorithms and convergence theory
- The linearized Bregman method via split feasibility problems: analysis and generalizations
- The rate of convergence for the method of alternating projections. II
- Worst-case complexity of cyclic coordinate descent: O(n^2) gap with randomized version
Cited in
(93)- A fast block nonlinear Bregman-Kaczmarz method with averaging for nonlinear sparse signal recovery
- Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency
- Randomized Kaczmarz with averaging
- Randomized extended average block Kaczmarz for solving least squares
- An accelerated randomized Kaczmarz algorithm
- Convergence analyses based on frequency decomposition for the randomized row iterative method
- A randomized sparse Kaczmarz solver for sparse signal recovery via minimax-concave penalty
- The block Kaczmarz algorithm based on solving linear systems with arrowhead matrices
- Faster randomized block sparse Kaczmarz by averaging
- On greedy randomized average block Kaczmarz method for solving large linear systems
- Solving, tracking and stopping streaming linear inverse problems
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- A class of pseudoinverse-free greedy block nonlinear Kaczmarz methods for nonlinear systems of equations
- On adaptive stochastic heavy ball momentum for solving linear systems
- On a fast deterministic block Kaczmarz method for solving large-scale linear systems
- The accelerated tensor Kaczmarz algorithm with adaptive parameters for solving tensor systems
- Accelerating the distributed Kaczmarz algorithm by strong over-relaxation
- On Adaptive Sketch-and-Project for Solving Linear Systems
- On averaging block Kaczmarz methods for solving nonlinear systems of equations
- Stochastic iterative methods for online rank aggregation from pairwise comparisons
- Average block column action methods for solving least squares problems
- Randomized block Kaczmarz methods with k-means clustering for solving large linear systems
- A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
- Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection
- Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems
- Randomized Block Adaptive Linear System Solvers
- Generalized Gearhart-Koshy acceleration for the Kaczmarz method
- Adaptive Bregman-Kaczmarz: an approach to solve linear inverse problems with independent noise exactly
- A residual-based surrogate hyperplane extended Kaczmarz algorithm for large least squares problems
- An almost-maximal residual tensor block Kaczmarz method for large tensor linear systems
- On convergence rates of Kaczmarz-type methods with different selection rules of working rows
- On greedy double block extended Kaczmarz algorithm for solving large inconsistent linear systems
- A greedy randomized average block projection method for linear feasibility problems
- Greedy block extended Kaczmarz method for solving the least squares problems
- Quantile-based random sparse Kaczmarz for corrupted and noisy linear systems
- A Deterministic Kaczmarz Algorithm for Solving Linear Systems
- On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations
- On adaptive block coordinate descent methods for ridge regression
- An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm
- A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems
- Preprocessed GMRES for fast solution of linear equations
- On randomized explicit block Kaczmarz method for solving large linear systems
- Acceleration and restart for the randomized Bregman-Kaczmarz method
- A stochastic Kaczmarz algorithm for network tomography
- Randomized Kaczmarz algorithm with averaging and block projection
- A greedy randomized extended block average Kaczmarz algorithm for solving least squares solutions
- Block-iterative algorithm with row projection for consistent linear system
- Stochastic dual coordinate descent with adaptive heavy ball momentum for linearly constrained convex optimization
- On maximum residual block and two-step Gauss-Seidel algorithms for linear least-squares problems
- Randomized double and triple Kaczmarz for solving extended normal equations
- Minibatch stochastic subgradient-based projection algorithms for feasibility problems with convex inequalities
- Greedy Kaczmarz algorithm using optimal intermediate projection technique for coherent linear systems
- On the relaxed greedy deterministic row and column iterative methods
- Randomized approximate class-specific kernel spectral regression analysis for large-scale face verification
- On pseudoinverse-free randomized methods for linear systems: unified framework and acceleration
- The quaternion relaxed greedy randomized Kaczmarz method with adaptive parameters for solving quaternion matrix equation
- On block Gaussian sketching for the Kaczmarz method
- A doubly stochastic block Gauss-Seidel algorithm for solving linear equations
- Convergence and semi-convergence of a class of constrained block iterative methods
- Stochastic block projection algorithms with extrapolation for convex feasibility problems
- Reflective block Kaczmarz algorithms for least squares
- On averaged block nonlinear Kaczmarz method with adaptive step size for solving systems of nonlinear equations
- Maximal residual coordinate descent method with k-means clustering for solving large linear least-squares problems
- Randomized Kaczmarz with tail averaging
- Nonlinear Kaczmarz algorithms and their convergence
- An improved deterministic block Kaczmarz method for solving linear matrix equation AXB = C
- A unified convergence analysis of random sketch methods for rank deficient linear systems
- On fast deterministic two-row block Kaczmarz method for solving consistent linear systems
- On convergence of the partially randomized extended Kaczmarz method
- On the adaptive deterministic block Kaczmarz method with momentum for solving large-scale consistent linear systems
- On weighted average fast block Kaczmarz methods for solving large consistent linear systems
- Randomized Kaczmarz with geometrically smoothed momentum
- On block accelerations of quantile randomized Kaczmarz for corrupted systems of linear equations
- A Kaczmarz Algorithm for Solving Tree Based Distributed Systems of Equations
- Randomized extended average block Kaczmarz method for inconsistent tensor equations under t-product
- Block Kaczmarz method with inequalities
- Efficient randomized block Kaczmarz method for linear feasibility
- On fast greedy block Kaczmarz methods for solving large consistent linear systems
- An accelerated surrogate hyperplane Kaczmarz method based on two-dimensional search
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Power of _1-norm regularized Kaczmarz algorithms for high-order tensor recovery
- Splitting-based randomized iterative methods for solving indefinite least squares problem
- The randomized Kaczmarz algorithm with the probability distribution depending on the angle
- Randomized block subsampling Kaczmarz-Motzkin method
- A surrogate hyperplane Kaczmarz method for solving consistent linear equations
- RidgeSketch: a fast sketching based solver for large scale ridge regression
- A semi-randomized block Kaczmarz method with simple random sampling for large-scale consistent linear systems
- Faster Deterministic Pseudoinverse-Free Block Extension of Motzkin Method for Large Consistent Linear Systems
- Block sampling Kaczmarz-Motzkin methods for consistent linear systems
- Randomized iterative methods for generalized absolute value equations: solvability and error bounds
- A greedy average block sparse Kaczmarz method for sparse solutions of linear systems
- K-means clustering based maximal residual (block) Kaczmarz methods for solving large scale system of linear equations
- A surrogate hyperplane Kaczmarz method with oblique projection for solving linear systems
This page was built for publication: Faster randomized block Kaczmarz algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5203967)
