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
- 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
- scientific article; zbMATH DE number 3027894 (Why is no real title available?)
- 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
(only showing first 100 items - show all)- 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
- Nonlinear Kaczmarz algorithms and their convergence
- On a fast deterministic block Kaczmarz method for solving large-scale linear systems
- Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection
- On greedy randomized average block Kaczmarz method for solving large 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 block Gaussian sketching for the Kaczmarz method
- Accelerating the distributed Kaczmarz algorithm by strong over-relaxation
- Block sampling Kaczmarz-Motzkin methods for consistent linear systems
- A doubly stochastic block Gauss-Seidel algorithm for solving linear equations
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Randomized Kaczmarz with averaging
- Randomized block Kaczmarz methods with k-means clustering for solving large linear systems
- On fast greedy block Kaczmarz methods for solving large consistent linear systems
- 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
- Block-iterative algorithm with row projection for consistent linear system
- An accelerated randomized Kaczmarz algorithm
- A stochastic Kaczmarz algorithm for network tomography
- Convergence analyses based on frequency decomposition for the randomized row iterative method
- On Adaptive Sketch-and-Project for Solving Linear Systems
- A Kaczmarz Algorithm for Solving Tree Based Distributed Systems of Equations
- Stochastic block projection algorithms with extrapolation for convex feasibility problems
- On block accelerations of quantile randomized Kaczmarz for corrupted systems of linear equations
- On convergence of the partially randomized extended Kaczmarz method
- RidgeSketch: a fast sketching based solver for large scale ridge regression
- Randomized extended average block Kaczmarz for solving least squares
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- The block Kaczmarz algorithm based on solving linear systems with arrowhead matrices
- Convergence and semi-convergence of a class of constrained block iterative methods
- Greedy Kaczmarz algorithm using optimal intermediate projection technique for coherent linear systems
- Generalized Gearhart-Koshy acceleration for the Kaczmarz method
- A Deterministic Kaczmarz Algorithm for Solving Linear Systems
- An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm
- A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems
- An almost-maximal residual tensor block Kaczmarz method for large tensor linear systems
- On adaptive block coordinate descent methods for ridge regression
- Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems
- Randomized Block Adaptive Linear System Solvers
- On convergence rates of Kaczmarz-type methods with different selection rules of working rows
- Faster randomized block sparse Kaczmarz by averaging
- A surrogate hyperplane Kaczmarz method for solving consistent linear equations
- Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency
- Faster Deterministic Pseudoinverse-Free Block Extension of Motzkin Method for Large Consistent Linear Systems
- On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations
- Randomized Kaczmarz algorithm with averaging and block projection
- A greedy average block sparse Kaczmarz method for sparse solutions of linear systems
- A randomized sparse Kaczmarz solver for sparse signal recovery via minimax-concave penalty
- Solving, tracking and stopping streaming linear inverse problems
- 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
- The accelerated tensor Kaczmarz algorithm with adaptive parameters for solving tensor systems
- Stochastic iterative methods for online rank aggregation from pairwise comparisons
- On averaging block Kaczmarz methods for solving nonlinear systems of equations
- Average block column action methods for solving least squares problems
- A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
- 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
- Greedy block extended Kaczmarz method for solving the least squares problems
- Acceleration and restart for the randomized Bregman-Kaczmarz method
- Reflective block Kaczmarz algorithms for least squares
- 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
- Efficient randomized block Kaczmarz method for linear feasibility
- Stochastic dual coordinate descent with adaptive heavy ball momentum for linearly constrained convex optimization
- On pseudoinverse-free randomized methods for linear systems: unified framework and acceleration
- A greedy randomized average block projection method for linear feasibility problems
- The quaternion relaxed greedy randomized Kaczmarz method with adaptive parameters for solving quaternion matrix equation
- Maximal residual coordinate descent method with k-means clustering for solving large linear least-squares problems
- Preprocessed GMRES for fast solution of linear equations
- 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
- Randomized Kaczmarz with tail averaging
- Randomized extended average block Kaczmarz method for inconsistent tensor equations under t-product
- An accelerated surrogate hyperplane Kaczmarz method based on two-dimensional search
- Power of _1-norm regularized Kaczmarz algorithms for high-order tensor recovery
- A semi-randomized block Kaczmarz method with simple random sampling for large-scale consistent linear systems
- Randomized iterative methods for generalized absolute value equations: solvability and error bounds
- 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
- A fast block nonlinear Bregman-Kaczmarz method with averaging for nonlinear sparse signal recovery
- On greedy double block extended Kaczmarz algorithm for solving large inconsistent linear systems
- Quantile-based random sparse Kaczmarz for corrupted and noisy linear systems
- On randomized explicit block Kaczmarz method for solving large linear systems
- A greedy randomized extended block average Kaczmarz algorithm for solving least squares solutions
- On averaged block nonlinear Kaczmarz method with adaptive step size for solving systems of nonlinear equations
- On fast deterministic two-row block Kaczmarz method for solving consistent linear systems
- On a deterministic block Kaczmarz-type method and its acceleration for the solution of large-scale linear systems
- On column-block enhanced randomized extended Kaczmarz method for solving inconsistent linear systems
- On greedy randomized average block sparse Kaczmarz method for solving sparse solutions to linear problems
- Several improved nonlinear deterministic block Kaczmarz methods for solving nonlinear equations
- Residual-based surrogate hyperplane double and triple Kaczmarz algorithms for solving extended normal equations
- Log-sum regularized Kaczmarz algorithms for high-order tensor recovery
- Randomized average block coordinate descent method with heavy-ball momentum for tensor least squares problem under the t-product
- Generalized Gearhart-Koshy acceleration is a Krylov subspace method
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)
