Preasymptotic convergence of randomized Kaczmarz method
From MaRDI portal
Publication:4601433
DOI10.1088/1361-6420/AA8E82zbMATH Open1382.65087arXiv1706.08459OpenAlexW3100274236MaRDI QIDQ4601433FDOQ4601433
Bangti Jin, Xiliang Lu, Yu Ling Jiao
Publication date: 16 January 2018
Published in: Inverse Problems (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1706.08459
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 (26)
- Choosing relaxation parameter in randomized Kaczmarz method
- Convergence analyses based on frequency decomposition for the randomized row iterative method
- Faster randomized block sparse Kaczmarz by averaging
- Surrounding the solution of a linear system of equations from all sides
- On the Convergence of Stochastic Gradient Descent for Nonlinear Ill-Posed Problems
- Linearly convergent adjoint free solution of least squares problems by random descent
- On the regularizing property of stochastic gradient 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
- The extensions of convergence rates of Kaczmarz-type methods
- 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
- Title not available (Why is that?)
- A randomized Kaczmarz algorithm with exponential convergence
- Splitting-based randomized iterative methods for solving indefinite least squares problem
- Randomized block subsampling Kaczmarz-Motzkin method
- Linear convergence of the randomized sparse Kaczmarz method
- Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency
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)
