Randomized extended average block Kaczmarz for solving least squares
From MaRDI portal
Abstract: Randomized iterative algorithms have recently been proposed to solve large-scale linear systems. In this paper, we present a simple randomized extended block Kaczmarz algorithm that exponentially converges in the mean square to the unique minimum -norm least squares solution of a given linear system of equations. The proposed algorithm is pseudoinverse-free and therefore different from the projection-based randomized double block Kaczmarz algorithm of Needell, Zhao, and Zouzias. We emphasize that our method works for all types of linear systems (consistent or inconsistent, overdetermined or underdetermined, full-rank or rank-deficient). Moreover, our approach can utilize efficient implementations on distributed computing units, yielding remarkable improvements in computational time. Numerical examples are given to show the efficiency of the new algorithm.
Recommendations
- Randomized extended Kaczmarz for solving least squares
- Randomized block Kaczmarz method with projection for solving least squares
- Randomized double and triple Kaczmarz for solving extended normal equations
- Single projection Kaczmarz extended algorithms
- On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems
Cites work
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- scientific article; zbMATH DE number 3313108 (Why is no real title available?)
- A Block Projection Method for Sparse Matrices
- A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems
- A new greedy Kaczmarz algorithm for the solution of very large linear systems
- A new theoretical estimate for the convergence rate of the maximal weighted residual Kaczmarz algorithm
- A novel partitioning method for accelerating the block Cimmino algorithm
- A randomized Kaczmarz algorithm with exponential convergence
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- A unified treatment of some iterative algorithms in signal processing and image reconstruction
- An accelerated randomized Kaczmarz algorithm
- Block-iterative methods for consistent and inconsistent linear equations
- Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
- Convergence rates for Kaczmarz-type algorithms
- Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems
- Faster randomized block Kaczmarz algorithms
- Fundamentals of Computerized Tomography
- Generalized inverses. Theory and applications.
- Image reconstruction from a small number of projections
- On Motzkin's method for inconsistent linear systems
- On convergence rate of the randomized Kaczmarz method
- On greedy randomized Kaczmarz method for solving large sparse linear systems
- On greedy randomized coordinate descent methods for solving large linear least-squares problems.
- On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems
- On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems
- On the relation between the randomized extended Kaczmarz algorithm and coordinate descent
- Partitioning strategies for the block Cimmino algorithm
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Principles of computerized tomography imaging
- Randomized Kaczmarz solver for noisy linear systems
- Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions
- 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
- Row Projection Methods for Large Nonsymmetric Linear Systems
- Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression
- Single projection Kaczmarz extended algorithms
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
- Stochastic reformulations of linear systems: algorithms and convergence theory
- The University of Florida sparse matrix collection
- The augmented block Cimmino distributed method
- The mathematics of computerized tomography
- Tight upper bounds for the convergence of the randomized extended Kaczmarz and Gauss-Seidel algorithms.
- Variant of greedy randomized Kaczmarz for ridge regression
Cited in
(76)- A fast block nonlinear Bregman-Kaczmarz method with averaging for nonlinear sparse signal recovery
- Mismatched adjoint random Kaczmarz with averaging
- Regularized randomized iterative algorithms for factorized linear systems
- Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency
- On extended randomized Kaczmarz algorithm for solving Tikhonov regularization problem
- 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
- A modified partially randomized extended Kaczmarz iteration method
- 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
- A fast block coordinate descent method for solving linear least-squares problems
- On averaging block Kaczmarz methods for solving nonlinear systems of equations
- Quantile-based iterative methods for corrupted systems of linear equations
- Randomized extended Kaczmarz for solving least squares
- Tensor randomized extended Kaczmarz methods for large inconsistent tensor linear equations with t-product
- Average block column action methods for solving least squares problems
- Randomized sparse block Kaczmarz as randomized dual block-coordinate descent
- Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection
- A randomized block Douglas-Rachford method for solving linear matrix equation
- The equivalence of the randomized extended Gauss-Seidel and randomized extended Kaczmarz methods
- Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems
- On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations
- 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
- 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
- On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations
- A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems
- On randomized explicit block Kaczmarz method for solving large linear systems
- Acceleration and restart for the randomized Bregman-Kaczmarz method
- Randomized Kaczmarz algorithm with averaging and block projection
- A greedy randomized extended block average Kaczmarz algorithm for solving least squares solutions
- scientific article; zbMATH DE number 7708789 (Why is no real title available?)
- Randomized double and triple Kaczmarz for solving extended normal equations
- Greedy Kaczmarz algorithm using optimal intermediate projection technique for coherent linear systems
- On the relaxed greedy deterministic row and column iterative methods
- On pseudoinverse-free randomized methods for linear systems: unified framework and acceleration
- On the generally randomized extended Gauss-Seidel method
- Reflective block Kaczmarz algorithms for least squares
- On averaged block nonlinear Kaczmarz method with adaptive step size for solving systems of nonlinear equations
- Extended randomized Kaczmarz method for sparse least squares and impulsive noise problems
- On the relation between the randomized extended Kaczmarz algorithm and coordinate descent
- Single projection Kaczmarz extended algorithms
- Accelerated greedy randomized augmented Kaczmarz algorithm for inconsistent linear systems
- A quantile-based block Kaczmarz algorithm for solving large consistent linear systems
- An improved deterministic block Kaczmarz method for solving linear matrix equation AXB = C
- Randomized block Kaczmarz method with projection for solving least squares
- On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems
- 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
- Two accelerated residual-based iterative methods and their convergence analyses
- Randomized Kaczmarz methods for t-product tensor linear systems with factorized operators
- On block accelerations of quantile randomized Kaczmarz for corrupted systems of linear equations
- On the randomized multiple row-action methods for solving linear least-squares problems
- Randomized extended average block Kaczmarz method for inconsistent tensor equations under t-product
- An accelerated surrogate hyperplane Kaczmarz method based on two-dimensional search
- On the randomized block Kaczmarz algorithms for solving matrix equation \(A X B = C\)
- Research on Kaczmarz algorithm based on residual drive
- Splitting-based randomized iterative methods for solving indefinite least squares problem
- Randomized block subsampling Kaczmarz-Motzkin method
- Multi-step greedy Kaczmarz algorithms with simple random sampling for solving large linear systems
- A randomized block extended Kaczmarz method with hybrid partitions for solving large inconsistent linear systems
- A semi-randomized block Kaczmarz method with simple random sampling for large-scale consistent linear systems
- On cyclic block coordinate descent method for solving large inconsistent 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
- On greedy partially randomized extended Kaczmarz method for solving large sparse inconsistent linear systems
- Randomized iterative methods for generalized absolute value equations: solvability and error bounds
- Solving the system of nonsingular tensor equations via randomized Kaczmarz-like method
This page was built for publication: Randomized extended average block Kaczmarz for solving least squares
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5146686)
