Randomized Kaczmarz with tail averaging
This interesting paper relates to the randmomized Kaczmarz method with tail averaging. To set the scene, the overdetermined linear least-squares problem is given as \(\min_{x\in \mathbb R^d}||b-Ax||^2\) where \(A\in R^{n\times d}\), \(b\in \mathbb R^n\) and \(n>d\). The problem is classical in that it has vast applications in many areas for example statistics, scientific computation, machine learning and many others. It is also well known that when the number of rows is large, computing the solution by direct means is memory-intensive. In the consistent case \(b=Ax^*\), row-acess methods, for example randomized Kaczmarz, yield exponential convergence. However, in the inconsistent case where \(b\neq Ax*\), randomized Kaczmarz converges up to a finite horizon. The point of this paper is to show that by combining randomized Kaczmarz with a certain tail averaging overcomes this horizon convergence barrier. \N\NThe paper is well written with a good set of references.
- A Kaczmarz Algorithm for Solving Tree Based Distributed Systems of Equations
- A Kaczmarz-inspired approach to accelerate the optimization of neural network wavefunctions
- A randomized Kaczmarz algorithm with exponential convergence
- Acceleration of Stochastic Approximation by Averaging
- Active linear regression for _p norms and beyond
- Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
- Convex optimization: algorithms and complexity
- Deep learning
- Equation of state calculations by fast computing machines
- Faster randomized block Kaczmarz algorithms
- Kaczmarz algorithm for Tikhonov regularization problem
- Learning theory of randomized Kaczmarz algorithm
- Parallelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Randomized extended Kaczmarz for solving least squares
- Randomized Kaczmarz with averaging
- Reverse iterative volume sampling for linear regression
- Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression
- Semi-Infinite Linear Regression and Its Applications
- Sketching as a tool for numerical linear algebra
- Strong underrelaxation in Kaczmarz's method for inconsistent systems
- A unified convergence analysis of random sketch methods for rank deficient linear systems
- Randomized Kaczmarz methods with beyond-Krylov convergence
- Subspace-constrained randomized coordinate descent for linear systems with good low-rank matrix approximations
- Relaxed greedy randomized Kaczmarz with signal averaging for solving doubly-noisy linear systems
This page was built for publication: Randomized Kaczmarz with tail averaging
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6892560)
