Abstract: The randomized Kaczmarz method is an iterative algorithm that solves overdetermined systems of linear equations. Recently, the method was extended to systems of equalities and inequalities by Leventhal and Lewis. Even more recently, Needell and Tropp provided an analysis of a block version of the method for systems of linear equations. This paper considers the use of a block type method for systems of mixed equalities and inequalities, bridging these two bodies of work. We show that utilizing a matrix paving over the equalities of the system can lead to significantly improved convergence, and prove a linear convergence rate as in the standard block method. We also demonstrate that using blocks of inequalities offers similar improvement only when the system satisfies a certain geometric property. We support the theoretical analysis with several experimental results.
Recommendations
- Randomized block Kaczmarz method with projection for solving least squares
- Faster randomized block Kaczmarz algorithms
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- A weighted randomized Kaczmarz method for solving linear systems
Cites work
- scientific article; zbMATH DE number 4205183 (Why is no real title available?)
- scientific article; zbMATH DE number 3027894 (Why is no real title available?)
- A Kaczmarz-Kovarik algorithm for symmetric ill-conditioned matrices
- A fast Kaczmarz-Kovarik algorithm for consistent least-squares problems
- A randomized Kaczmarz algorithm with exponential convergence
- Almost sure convergence of the Kaczmarz algorithm with random measurements
- Applied iterative methods.
- Block-iterative methods for consistent and inconsistent linear equations
- Block-projections algorithms with blocks containing mutually orthogonal rows and columns
- Column subset selection, matrix factorization, and eigenvalue optimization
- Fundamentals of Computerized Tomography
- Improved analysis of the subsampled randomized Hadamard transform
- Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
- Invertibility of random submatrices via tail-decoupling and a matrix Chernoff inequality
- Iterative algorithms for large partitioned linear systems, with applications to image reconstruction
- John's decompositions: Selecting a large part
- On the acceleration of Kaczmarz's method for inconsistent linear systems
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Projection method for solving a singular system of linear equations and its applications
- Random sets of isomorphism of linear operators on Hilbert space
- Randomized Kaczmarz solver for noisy linear systems
- Randomized block Kaczmarz method with projection for solving least squares
- Randomized extended Kaczmarz for solving least squares
- Randomized methods for linear constraints: convergence rates and conditioning
- Row-Action Methods for Huge and Sparse Systems and Their Applications
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
- Strong underrelaxation in Kaczmarz's method for inconsistent systems
- The angles between the null spaces of X rays
- The mathematics of computerized tomography
- The method of alternating projections and the method of subspace corrections in Hilbert space
- The random paving property for uniformly bounded matrices
- Two Algorithms Related to the Method of Steepest Descent
- User-friendly tail bounds for sums of random matrices
Cited in
(15)- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- On Adaptive Sketch-and-Project for Solving Linear Systems
- A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
- On the Meany inequality with applications to convergence analysis of several row-action iteration methods
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- Faster randomized block Kaczmarz algorithms
- Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition
- Randomized block Kaczmarz method with projection for solving least squares
- On the error estimate of the randomized double block Kaczmarz method
- On block accelerations of quantile randomized Kaczmarz for corrupted systems of linear equations
- Efficient randomized block Kaczmarz method for linear feasibility
- Sparse sampling Kaczmarz–Motzkin method with linear convergence
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Randomized block subsampling Kaczmarz-Motzkin method
- Linear convergence of the randomized sparse Kaczmarz method
This page was built for publication: Block Kaczmarz method with inequalities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q890093)
