Randomized block Kaczmarz method with projection for solving least squares
From MaRDI portal
Abstract: The Kaczmarz method is an iterative method for solving overcomplete linear systems of equations Ax=b. The randomized version of the Kaczmarz method put forth by Strohmer and Vershynin iteratively projects onto a randomly chosen solution space given by a single row of the matrix A and converges exponentially in expectation to the solution of a consistent system. In this paper we analyze two block versions of the method each with a randomized projection, that converge in expectation to the least squares solution of inconsistent systems. Our approach utilizes a paving of the matrix A to guarantee exponential convergence, and suggests that paving yields a significant improvement in performance in certain regimes. The proposed method is an extension of the block Kaczmarz method analyzed by Needell and Tropp and the Randomized Extended Kaczmarz method of Zouzias and Freris. The contribution is thus two-fold; unlike the standard Kaczmarz method, our methods converge to the least-squares solution of inconsistent systems, and by using appropriate blocks of the matrix this convergence can be significantly accelerated. Numerical experiments suggest that the proposed algorithm can indeed lead to advantages in practice.
Recommendations
- Randomized extended average block Kaczmarz for solving least squares
- Projected randomized Kaczmarz methods
- Randomized extended Kaczmarz for solving least squares
- On randomized partial block Kaczmarz method for solving huge linear algebraic systems
- On greedy randomized block Kaczmarz method for consistent linear systems
- Randomized block Krylov methods for approximating extreme eigenvalues
- Randomized block Kaczmarz methods with \(k\)-means clustering for solving large linear systems
- An accelerated randomized Kaczmarz method via low-rank approximation
- On Kaczmarz's projection iteration as a direct solver for linear least squares problems
- On greedy randomized average block Kaczmarz method for solving large linear systems
Cites work
- scientific article; zbMATH DE number 4205183 (Why is no real title available?)
- scientific article; zbMATH DE number 4215266 (Why is no real title available?)
- scientific article; zbMATH DE number 3919670 (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 Randomized Solver for Linear Systems with Exponential Convergence
- A fast Kaczmarz-Kovarik algorithm for consistent least-squares problems
- A randomized Kaczmarz algorithm with exponential convergence
- Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
- An elementary proof of the restricted invertibility theorem
- Applied iterative methods.
- Block Kaczmarz method with inequalities
- 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
- Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems
- Fundamentals of Computerized Tomography
- 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
- Norms of random submatrices and sparse approximation
- On Kaczmarz's projection iteration as a direct solver for linear least squares problems
- On the acceleration of Kaczmarz's method for inconsistent linear systems
- On the rate of convergence of the alternating projection method in finite dimensional spaces
- 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 extended Kaczmarz for solving least squares
- Randomized methods for linear constraints: convergence rates and conditioning
- Regularization tools version \(4.0\) for matlab \(7.3\)
- 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
- The rate of convergence for the method of alternating projections. II
- Two Algorithms Related to the Method of Steepest Descent
- Two-subspace projection method for coherent overdetermined systems
Cited in
(88)- On the generally randomized extended Gauss-Seidel method
- Convergence analysis of inexact randomized iterative methods
- 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
- On the relaxed greedy deterministic row and column iterative methods
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- Randomized approximate class-specific kernel spectral regression analysis for large-scale face verification
- Single projection Kaczmarz extended algorithms
- Convergence analyses based on frequency decomposition for the randomized row iterative method
- Convergence of a randomized Douglas-Rachford method for linear system
- On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems
- Faster randomized block Kaczmarz algorithms
- On a fast deterministic block Kaczmarz method for solving large-scale linear systems
- Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
- A weighted randomized Kaczmarz method for solving linear systems
- The extensions of convergence rates of Kaczmarz-type methods
- A greedy block Kaczmarz algorithm for solving large-scale linear systems
- On greedy randomized block Kaczmarz method for consistent linear systems
- On the regularization effect of stochastic gradient descent applied to least-squares
- Sampled limited memory methods for massive linear inverse problems
- On greedy randomized average block Kaczmarz method for solving large linear systems
- A fast block coordinate descent method for solving linear least-squares problems
- Accelerating the distributed Kaczmarz algorithm by strong over-relaxation
- On convergence of the partially randomized extended Kaczmarz method
- Randomized Kaczmarz Converges Along Small Singular Vectors
- Surrounding the solution of a linear system of equations from all sides
- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems
- A Deterministic Kaczmarz Algorithm for Solving Linear Systems
- On randomized partial block Kaczmarz method for solving huge linear algebraic systems
- Block sampling Kaczmarz-Motzkin methods for consistent linear systems
- Enhancement of the Kaczmarz algorithm with projection adjustment
- On multi-step randomized extended Kaczmarz method for solving large sparse inconsistent linear systems
- On Adaptive Sketch-and-Project for Solving Linear Systems
- Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
- The row-oriented form of the regularized Kaczmarz's method
- On the Convergence of Stochastic Gradient Descent for Linear Inverse Problems in Banach Spaces
- A Kaczmarz Algorithm for Solving Tree Based Distributed Systems of Equations
- On block Gaussian sketching for the Kaczmarz method
- On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations
- Randomized extended average block Kaczmarz for solving least squares
- On the error estimate of the randomized double block Kaczmarz method
- Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection
- Randomized extended Kaczmarz for solving least squares
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Randomized Block Adaptive Linear System Solvers
- On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems
- Block Kaczmarz method with inequalities
- A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems
- Regularized Kaczmarz Algorithms for Tensor Recovery
- A doubly stochastic block Gauss-Seidel algorithm for solving linear equations
- Approximate Solutions of Linear Systems at a Universal Rate
- Randomized sparse block Kaczmarz as randomized dual block-coordinate descent
- Stability of the Kaczmarz reconstruction for stationary sequences
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- Randomized iterative methods for linear systems
- Extended randomized Kaczmarz method for sparse least squares and impulsive noise problems
- Randomized Kaczmarz with geometrically smoothed momentum
- Faster Deterministic Pseudoinverse-Free Block Extension of Motzkin Method for Large Consistent Linear Systems
- Randomized Kaczmarz algorithm with averaging and block projection
- Choosing relaxation parameter in randomized Kaczmarz method
- On the adaptive deterministic block Kaczmarz method with momentum for solving large-scale consistent linear systems
- The randomized circumcentered-reflection iteration method for solving consistent linear equations
- On weighted average fast block Kaczmarz methods for solving large consistent linear systems
- A two-dimensional randomized extended Gauss-Seidel algorithm for solving least squares problems
- A surrogate hyperplane Kaczmarz method for solving consistent linear equations
- Greedy block extended Kaczmarz method for solving the least squares problems
- Tensor randomized extended Kaczmarz methods for large inconsistent tensor linear equations with t-product
- A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
- Average block column action methods for solving least squares problems
- On block accelerations of quantile randomized Kaczmarz for corrupted systems of linear equations
- The accelerated tensor Kaczmarz algorithm with adaptive parameters for solving tensor systems
- On adaptive block coordinate descent methods for ridge regression
- PLSS: A Projected Linear Systems Solver
- A randomized block extended Kaczmarz method with hybrid partitions for solving large inconsistent linear systems
- Three double multi-step randomized extended Kaczmarz methods for solving large sparse inconsistent linear systems
- A residual-based surrogate hyperplane extended Kaczmarz algorithm for large least squares problems
- On multi-step extended maximum residual Kaczmarz method for solving large inconsistent linear systems
- Greedy Kaczmarz algorithm using optimal intermediate projection technique for coherent linear systems
- An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm
- A class of pseudoinverse-free greedy block nonlinear Kaczmarz methods for nonlinear systems of equations
- A modified partially randomized extended Kaczmarz iteration method
- The standard forms and convergence theory of the Kaczmarz-Tanabe type methods for solving linear systems
- Reflective block Kaczmarz algorithms for least squares
- On constrained Kaczmarz algorithm with momentum for image reconstruction
- On the randomized block Kaczmarz algorithms for solving matrix equation \(A X B = C\)
- Research on Kaczmarz algorithm based on residual drive
- An almost-maximal residual tensor block Kaczmarz method for large tensor linear systems
This page was built for publication: Randomized block Kaczmarz method with projection for solving least squares
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q491121)
