Preasymptotic convergence of randomized Kaczmarz method
From MaRDI portal
(Redirected from Publication:4601433)
Abstract: Kaczmarz method is one popular iterative method for solving inverse problems, especially in computed tomography. Recently, it was established that a randomized version of the method enjoys an exponential convergence for well-posed problems, and the convergence rate is determined by a variant of the condition number. In this work, we analyze the preasymptotic convergence behavior of the randomized Kaczmarz method, and show that the low-frequency error (with respect to the right singular vectors) decays faster during first iterations than the high-frequency error. Under the assumption that the inverse solution is smooth (e.g., sourcewise representation), the result explains the fast empirical convergence behavior, thereby shedding new insights into the excellent performance of the randomized Kaczmarz method in practice. Further, we propose a simple strategy to stabilize the asymptotic convergence of the iteration by means of variance reduction. We provide extensive numerical experiments to confirm the analysis and to elucidate the behavior of the algorithms.
Recommendations
- On convergence rate of the randomized Kaczmarz method
- A note on convergence rate of randomized Kaczmarz method
- On the error estimate of the randomized double block Kaczmarz method
- An accelerated randomized Kaczmarz method via low-rank approximation
- A randomized Kaczmarz algorithm with exponential convergence
Cited in
(33)- Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency
- Choosing relaxation parameter in randomized Kaczmarz method
- Stochastic gradient descent method with convex penalty for ill-posed problems in Banach spaces
- On the triple-parameter least squares progressive iterative approximation and its convergence analysis
- On the block Kaczmarz-Tanabe methods with relaxation parameters for solving linear systems
- Convergence analyses based on frequency decomposition for the randomized row iterative method
- Surrounding the solution of a linear system of equations from all sides
- Faster randomized block sparse Kaczmarz by averaging
- On the Convergence of Stochastic Gradient Descent for Nonlinear Ill-Posed Problems
- On the regularizing property of stochastic gradient descent
- Linearly convergent adjoint free solution of least squares problems by random descent
- Projected randomized Kaczmarz methods
- Sampled limited memory methods for massive linear inverse problems
- Randomized Kaczmarz Converges Along Small Singular Vectors
- On convergence rate of the randomized Kaczmarz method
- Stochastic mirror descent method for linear ill-posed problems in Banach spaces
- Adaptive Bregman-Kaczmarz: an approach to solve linear inverse problems with independent noise exactly
- Randomized Kaczmarz method for single particle X-ray image phase retrieval
- Convergence rates of the Kaczmarz-Tanabe method for linear systems
- A Deterministic Kaczmarz Algorithm for Solving Linear Systems
- On randomized explicit block Kaczmarz method for solving large linear systems
- The extensions of convergence rates of Kaczmarz-type methods
- On pseudoinverse-free randomized methods for linear systems: unified framework and acceleration
- Approximate Solutions of Linear Systems at a Universal Rate
- On the generally randomized extended Gauss-Seidel method
- On the regularization effect of stochastic gradient descent applied to least-squares
- scientific article; zbMATH DE number 5116799 (Why is no real title available?)
- On fast deterministic two-row block Kaczmarz method for solving consistent linear systems
- A randomized Kaczmarz algorithm with exponential convergence
- Splitting-based randomized iterative methods for solving indefinite least squares problem
- Randomized block subsampling Kaczmarz-Motzkin method
- Stochastic variance reduced gradient method for linear ill-posed inverse problems
- Linear convergence of the randomized sparse Kaczmarz method
This page was built for publication: Preasymptotic convergence of randomized Kaczmarz method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601433)
