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)- A randomized Kaczmarz algorithm with exponential convergence
- On convergence rate of the randomized Kaczmarz method
- Linear convergence of the randomized sparse Kaczmarz method
- Convergence rates of the Kaczmarz-Tanabe method for linear systems
- On the regularization effect of stochastic gradient descent applied to least-squares
- On the generally randomized extended Gauss-Seidel method
- The extensions of convergence rates of Kaczmarz-type methods
- Projected randomized Kaczmarz methods
- Splitting-based randomized iterative methods for solving indefinite least squares problem
- Randomized block subsampling Kaczmarz-Motzkin method
- scientific article; zbMATH DE number 5116799 (Why is no real title available?)
- On the regularizing property of stochastic gradient descent
- Convergence analyses based on frequency decomposition for the randomized row iterative method
- Randomized Kaczmarz Converges Along Small Singular Vectors
- Surrounding the solution of a linear system of equations from all sides
- Sampled limited memory methods for massive linear inverse problems
- On the Convergence of Stochastic Gradient Descent for Nonlinear Ill-Posed Problems
- A Deterministic Kaczmarz Algorithm for Solving Linear Systems
- Approximate Solutions of Linear Systems at a Universal Rate
- Stochastic mirror descent method for linear ill-posed problems in Banach spaces
- Faster randomized block sparse Kaczmarz by averaging
- Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency
- Linearly convergent adjoint free solution of least squares problems by random descent
- Choosing relaxation parameter in randomized Kaczmarz method
- 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
- On pseudoinverse-free randomized methods for linear systems: unified framework and acceleration
- 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
- Stochastic variance reduced gradient method for linear ill-posed inverse problems
- Stochastic gradient descent method with convex penalty for ill-posed problems in Banach spaces
- On randomized explicit block Kaczmarz method for solving large linear systems
- On fast deterministic two-row block Kaczmarz method for solving consistent linear systems
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)
