Block Kaczmarz method with inequalities
From MaRDI portal
Publication:890093
DOI10.1007/S10851-014-0539-7zbMATH Open1327.65057arXiv1406.7339OpenAlexW2098196222MaRDI QIDQ890093FDOQ890093
Authors: Jonathan Briskman, D. Needell 
Publication date: 9 November 2015
Published in: Journal of Mathematical Imaging and Vision (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1406.7339
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
iterative algorithmconvergencenumerical examplessystems of linear equationsrandomized Kaczmarz methodsystems of mixed equalities and inequalities
Cites Work
- A randomized Kaczmarz algorithm with exponential convergence
- Fundamentals of Computerized Tomography
- Title not available (Why is that?)
- User-friendly tail bounds for sums of random matrices
- Row-Action Methods for Huge and Sparse Systems and Their Applications
- Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
- The mathematics of computerized tomography
- Title not available (Why is that?)
- Applied iterative methods.
- The random paving property for uniformly bounded matrices
- Randomized methods for linear constraints: convergence rates and conditioning
- The method of alternating projections and the method of subspace corrections in Hilbert space
- Improved analysis of the subsampled randomized Hadamard transform
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Strong underrelaxation in Kaczmarz's method for inconsistent systems
- Projection method for solving a singular system of linear equations and its applications
- Randomized extended Kaczmarz for solving least squares
- Randomized Kaczmarz solver for noisy linear systems
- Iterative algorithms for large partitioned linear systems, with applications to image reconstruction
- A Kaczmarz-Kovarik algorithm for symmetric ill-conditioned matrices
- Invertibility of random submatrices via tail-decoupling and a matrix Chernoff inequality
- Block-iterative methods for consistent and inconsistent linear equations
- The angles between the null spaces of X rays
- Almost sure convergence of the Kaczmarz algorithm with random measurements
- Column subset selection, matrix factorization, and eigenvalue optimization
- John's decompositions: Selecting a large part
- On the acceleration of Kaczmarz's method for inconsistent linear systems
- Block-projections algorithms with blocks containing mutually orthogonal rows and columns
- A fast Kaczmarz-Kovarik algorithm for consistent least-squares problems
- Random sets of isomorphism of linear operators on Hilbert space
- Randomized block Kaczmarz method with projection for solving least squares
- Two Algorithms Related to the Method of Steepest Descent
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 block accelerations of quantile randomized Kaczmarz for corrupted systems of linear equations
- On the error estimate of the randomized double block Kaczmarz method
- 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)
