A weighted randomized Kaczmarz method for solving linear systems

DOI10.1090/MCOM/3644MaRDI QIDQ4956926zbMATH OpenOpenAlexFDO

Authors Stefan Steinerberger

Publication date 2 September 2021

Published in Mathematics of Computation (Search for Journal in Brave)

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

zbMATH Keywords

Kaczmarz methodARTsingular vectorprojection onto convex setsrandomized Kaczmarz methodalgebraic reconstruction techniquePOCS

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10)

Abstract: The Kaczmarz method for solving a linear system $Ax=b$ interprets such a system as a collection of equations $leftlangle{a}_i,xightangle=b_i$, where $a_i$ is the $i-$th row of $A$, then picks such an equation and corrects $x_{k+1}=x_k+lambda{a}_i$ where $lambda$ is chosen so that the $i-$th equation is satisfied. Convergence rates are difficult to establish. Assuming the rows to be normalized, $|a_i{|}_{el{l}^2}=1$, Strohmer & Vershynin established that if the order of equations is chosen at random, $mathbbE|x_k-x{|}_{el{l}^2}$ converges exponentially. We prove that if the $i-$th row is selected with likelihood proportional to $left|leftlangle{a}_i,x_{k}ightangle-b_{i}ight{|}^p$, where $0<p<infty$, then $mathbbE|x_k-x{|}_{el{l}^2}$ converges faster than the purely random method. As $pightarrowinfty$, the method de-randomizes and explains, among other things, why the maximal correction method works well. We empirically observe that the method computes approximations of small singular vectors of $A$ as a byproduct.

Recommendations

• A weighted randomized sparse Kaczmarz method for solving linear systems
• The randomized Kaczmarz method with a new random selection rule
• A Randomized Solver for Linear Systems with Exponential Convergence
• Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
• Randomized Kaczmarz solver for noisy linear systems

Cites work

• scientific article; zbMATH DE number 3856876 (Why is no real title available?)
• scientific article; zbMATH DE number 3919670 (Why is no real title available?)
• scientific article; zbMATH DE number 4001918 (Why is no real title available?)
• scientific article; zbMATH DE number 4021000 (Why is no real title available?)
• A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates
• 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 randomized Kaczmarz algorithm with exponential convergence
• Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
• An accelerated randomized Kaczmarz algorithm
• Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
• Convergence rates for Kaczmarz-type algorithms
• Coordinatewise descent methods for leading eigenvalue problem
• Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
• On Adaptive Sketch-and-Project for Solving Linear Systems
• 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 relaxed greedy randomized Kaczmarz methods for solving large sparse 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
• Phase retrieval via randomized Kaczmarz: theoretical guarantees
• Randomized Kaczmarz Converges Along Small Singular Vectors
• Randomized Kaczmarz solver for noisy linear systems
• Randomized Kaczmarz with averaging
• 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
• Semi-convergence properties of Kaczmarz's method
• Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
• The Relaxation Method for Linear Inequalities
• The conjugate gradient regularization method in computed tomography problems
• The rate of convergence for the method of alternating projections. II
• Two-subspace projection method for coherent overdetermined systems

Cited in

(38)

• Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency
• A weighted randomized sparse Kaczmarz method for solving linear systems
• The randomized Kaczmarz method with mismatched adjoint
• The equivalence of the randomized extended Gauss-Seidel and randomized extended Kaczmarz methods
• Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems
• Randomized Block Adaptive Linear System Solvers
• Generalized Gearhart-Koshy acceleration for the Kaczmarz method
• Quantile-based Random Kaczmarz for corrupted linear systems of equations
• Adaptive Bregman-Kaczmarz: an approach to solve linear inverse problems with independent noise exactly
• On convergence rates of Kaczmarz-type methods with different selection rules of working rows
• A greedy randomized average block projection method for linear feasibility problems
• A Deterministic Kaczmarz Algorithm for Solving Linear Systems
• A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems
• Linear discriminant analysis with the randomized Kaczmarz method
• On randomized explicit block Kaczmarz method for solving large linear systems
• Randomized Kaczmarz algorithm with averaging and block projection
• On the convergence of randomized and greedy relaxation schemes for solving nonsingular linear systems of equations
• Greedy Kaczmarz algorithm using optimal intermediate projection technique for coherent linear systems
• On pseudoinverse-free randomized methods for linear systems: unified framework and acceleration
• Approximate Solutions of Linear Systems at a Universal Rate
• The global block Kaczmarz method using double greedy strategy
• On the regularization effect of stochastic gradient descent applied to least-squares
• A new theoretical estimate for the convergence rate of the maximal weighted residual Kaczmarz algorithm
• Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
• On fast deterministic two-row block Kaczmarz method for solving consistent linear systems
• The randomized circumcentered-reflection iteration method for solving consistent linear equations
• Randomized iterative methods for linear systems
• Kaczmarz's anomaly: a surprising feature of Kaczmarz's method
• Randomized Kaczmarz solver for noisy linear systems
• Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study
• On block accelerations of quantile randomized Kaczmarz for corrupted systems of linear equations
• The randomized Kaczmarz method with a new random selection rule
• A note on convergence rate of randomized Kaczmarz method
• Block Kaczmarz method with inequalities
• A surrogate hyperplane Kaczmarz method for solving consistent linear equations
• A semi-randomized block Kaczmarz method with simple random sampling for large-scale consistent linear systems
• A count sketch maximal weighted residual Kaczmarz method for solving highly overdetermined linear systems
• Kaczmarz Kac walk

This page was built for publication: A weighted randomized Kaczmarz method for solving linear systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4956926)