Randomized Extended Average Block Kaczmarz for Solving Least Squares

DOI10.1137/20M1312629zbMath1457.65020arXiv2001.04179OpenAlexW3096719568MaRDI QIDQ5146686

Xiaohui Sun, Wu-Tao Si, Kui Du

Publication date: 26 January 2021

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2001.04179

zbMATH Keywords

exponential convergenceminimum norm least squares solutiongeneral linear systemsblock Kaczmarz algorithm

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Iterative numerical methods for linear systems (65F10)

Related Items (44)

Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection ⋮ On greedy randomized average block Kaczmarz method for solving large linear systems ⋮ On block accelerations of quantile randomized Kaczmarz for corrupted systems of linear equations ⋮ A Fast Block Coordinate Descent Method for Solving Linear Least-Squares Problems ⋮ On Convergence of the Partially Randomized Extended Kaczmarz Method ⋮ Quantile-Based Iterative Methods for Corrupted Systems of Linear Equations ⋮ On the relaxed greedy deterministic row and column iterative methods ⋮ Extended randomized Kaczmarz method for sparse least squares and impulsive noise problems ⋮ A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems ⋮ Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems ⋮ Accelerated greedy randomized augmented Kaczmarz algorithm for inconsistent linear systems ⋮ On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations ⋮ Faster randomized block sparse Kaczmarz by averaging ⋮ 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 ⋮ Splitting-based randomized iterative methods for solving indefinite least squares problem ⋮ Randomized block subsampling Kaczmarz-Motzkin method ⋮ Block sampling Kaczmarz-Motzkin methods for consistent linear systems ⋮ A class of pseudoinverse-free greedy block nonlinear Kaczmarz methods for nonlinear systems of equations ⋮ On averaging block Kaczmarz methods for solving nonlinear systems of equations ⋮ On adaptive stochastic heavy ball momentum for solving linear systems ⋮ Acceleration and restart for the randomized Bregman-Kaczmarz method ⋮ A randomized block extended Kaczmarz method with hybrid partitions for solving large inconsistent linear systems ⋮ A randomized sparse Kaczmarz solver for sparse signal recovery via minimax-concave penalty ⋮ A modified partially randomized extended Kaczmarz iteration method ⋮ Convergence analyses based on frequency decomposition for the randomized row iterative method ⋮ Tensor randomized extended Kaczmarz methods for large inconsistent tensor linear equations with t-product ⋮ Average block column action methods for solving least squares problems ⋮ A randomized block Douglas-Rachford method for solving linear matrix equation ⋮ 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 ⋮ Randomized double and triple Kaczmarz for solving extended normal equations ⋮ A quantile-based block Kaczmarz algorithm for solving large consistent linear systems ⋮ 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 ⋮ On the randomized block Kaczmarz algorithms for solving matrix equation \(A X B = C\) ⋮ Research on Kaczmarz algorithm based on residual drive ⋮ Multi-step greedy Kaczmarz algorithms with simple random sampling for solving large linear systems ⋮ Solving the system of nonsingular tensor equations via randomized Kaczmarz-like method ⋮ Greedy Kaczmarz Algorithm Using Optimal Intermediate Projection Technique for Coherent Linear Systems ⋮ On a fast deterministic block Kaczmarz method for solving large-scale linear systems

Uses Software

• SparseMatrix

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Single projection Kaczmarz extended algorithms
• Randomized block Kaczmarz method with projection for solving least squares
• Partitioning strategies for the block Cimmino algorithm
• Block-iterative methods for consistent and inconsistent linear equations
• On the relation between the randomized extended Kaczmarz algorithm and coordinate descent
• Randomized Kaczmarz solver for noisy linear systems
• A randomized Kaczmarz algorithm with exponential convergence
• Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems
• On convergence rate of the randomized Kaczmarz method
• On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems
• A new greedy Kaczmarz algorithm for the solution of very large linear systems
• Generalized inverses. Theory and applications.
• On Motzkin's method for inconsistent linear systems
• Variant of greedy randomized Kaczmarz for ridge regression
• On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems
• Convergence rates for Kaczmarz-type algorithms
• A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• The Mathematics of Computerized Tomography
• Fundamentals of Computerized Tomography
• Randomized Extended Kaczmarz for Solving Least Squares
• The university of Florida sparse matrix collection
• Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
• An accelerated randomized Kaczmarz algorithm
• Convergence Properties of the Randomized Extended Gauss--Seidel and Kaczmarz Methods
• Randomized Iterative Methods for Linear Systems
• Image reconstruction from a small number of projections
• A Block Projection Method for Sparse Matrices
• Row Projection Methods for Large Nonsymmetric Linear Systems
• A unified treatment of some iterative algorithms in signal processing and image reconstruction
• A Novel Partitioning Method for Accelerating the Block Cimmino Algorithm
• On Greedy Randomized Kaczmarz Method for Solving Large Sparse Linear Systems
• Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory
• Faster Randomized Block Kaczmarz Algorithms
• A New Theoretical Estimate for the Convergence Rate of the Maximal Weighted Residual Kaczmarz Algorithm
• Tight upper bounds for the convergence of the randomized extended Kaczmarz and Gauss–Seidel algorithms
• On greedy randomized coordinate descent methods for solving large linear least‐squares problems
• Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions
• Randomized Projection Methods for Convex Feasibility: Conditioning and Convergence Rates
• The Augmented Block Cimmino Distributed Method
• A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility
• Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression
• Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm

This page was built for publication: Randomized Extended Average Block Kaczmarz for Solving Least Squares