A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility
From MaRDI portal
Publication:5372620
DOI10.1137/16M1073807zbMath1373.90070arXiv1605.01418OpenAlexW2962890513WikidataQ114978705 ScholiaQ114978705MaRDI QIDQ5372620
Jesús A. De Loera, Deanna Needell, Jamie Haddock
Publication date: 27 October 2017
Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1605.01418
linear programmingrandomizationiterative methodsKaczmarz methoditerated projectionsMotzkin's relaxation method
Convex programming (90C25) Linear programming (90C05) Linear inequalities of matrices (15A39) Iterative numerical methods for linear systems (65F10) Randomized algorithms (68W20)
Related Items
Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection, On greedy randomized average block Kaczmarz method for solving large linear systems, On the Kaczmarz methods based on relaxed greedy selection for solving matrix equation \(A X B = C\), Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration, Quantile-Based Iterative Methods for Corrupted Systems of Linear Equations, On greedy randomized block Kaczmarz method for consistent linear systems, Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem, RidgeSketch: A Fast Sketching Based Solver for Large Scale Ridge Regression, A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems, On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations, A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems, Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency, 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, Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition, Enhancement of the Kaczmarz algorithm with projection adjustment, On sampling Kaczmarz-Motzkin methods for solving large-scale nonlinear systems, Splitting-based randomized iterative methods for solving indefinite least squares problem, Randomized block subsampling Kaczmarz-Motzkin method, On block Gaussian sketching for the Kaczmarz method, Block sampling Kaczmarz-Motzkin methods for consistent linear systems, Randomized Extended Average Block Kaczmarz for Solving Least Squares, On Motzkin's method for inconsistent linear systems, Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions, On Adaptive Sketch-and-Project for Solving Linear Systems, Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin, Multi-step greedy Kaczmarz algorithms with simple random sampling for solving large linear systems, Kaczmarz method with oblique projection, Greedy Kaczmarz Algorithm Using Optimal Intermediate Projection Technique for Coherent Linear Systems, Randomized Kaczmarz for tensor linear systems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Single projection Kaczmarz extended algorithms
- Greedy and randomized versions of the multiplicative Schwarz method
- Two-subspace projection method for coherent overdetermined systems
- Randomized block Kaczmarz method with projection for solving least squares
- Random reordering in SOR-type methods
- Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
- On Kaczmarz's projection iteration as a direct solver for linear least squares problems
- Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem
- A strongly polynomial algorithm for linear systems having a binary solution
- Block-iterative methods for consistent and inconsistent linear equations
- Block Kaczmarz method with inequalities
- On the acceleration of Kaczmarz's method for inconsistent linear systems
- Randomized Kaczmarz solver for noisy linear systems
- A randomized Kaczmarz algorithm with exponential convergence
- The angles between the null spaces of X rays
- Iterative algorithms for large partitioned linear systems, with applications to image reconstruction
- On relaxation methods for systems of linear inequalities
- Strong underrelaxation in Kaczmarz's method for inconsistent systems
- A polynomial projection-type algorithm for linear programming
- Almost sure convergence of the Kaczmarz algorithm with random measurements
- Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Projection method for solving a singular system of linear equations and its applications
- The Mathematics of Computerized Tomography
- Randomized Extended Kaczmarz for Solving Least Squares
- A Dynamic Near-Optimal Algorithm for Online Linear Programming
- On Chubanov's Method for Linear Programming
- Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
- Revisiting Asynchronous Linear Solvers
- An accelerated randomized Kaczmarz algorithm
- Parallelism in Matrix Computations
- Convergence Properties of the Randomized Extended Gauss--Seidel and Kaczmarz Methods
- Randomized Iterative Methods for Linear Systems
- The Relaxation Method for Solving Systems of Linear Inequalities
- Row-Action Methods for Huge and Sparse Systems and Their Applications
- On the non-polynomiality of the relaxation method for systems of linear inequalities
- The method of alternating projections and the method of subspace corrections in Hilbert space
- Polynomial algorithms for a class of linear programs
- Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression
- Boundedness Theorems for the Relaxation Method
- Two Algorithms Related to the Method of Steepest Descent
- Computational Experience in Solving Linear Programs
- The Relaxation Method for Linear Inequalities
- The Relaxation Method for Linear Inequalities
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
