Inertial randomized Kaczmarz algorithms for solving coherent linear systems
This paper is about an alternated inertial randomized Kaczmarz (AIRK) algorithm, an iterative method for solving a consistent linear system \(Ax=b\) with \(A\in\mathbb{R}^{I\times J}\) and full row rank. The classical method has the form \(x^{k+1}=\Psi(x^k)\) where in the original algorithm [\textit{S. Kaczmarz}, Bull. Int. Acad. Polon. Sci. A 1937, 355--357 (1937; Zbl 0017.31703)] \(\Psi\) is a projection on the hyperplane \(H_{i_k}\) defined by a cyclically selected equation \(i_k\) of the system. In the randomized version, the selection of \(i_k\) is random. In the two-subspace Kaczmarz (TSK) method of [\textit{D. Needell} and \textit{R. Ward}, J. Fourier Anal. Appl. 19, No. 2, 256--269 (2013; Zbl 1306.65190)] two different rows \(i_k,j_k\) are randomly selected according to an optimal probability and orthogonalization is used in order to reduce correlation. In the inertial version, the update is based on 2 previous steps: \(x^{k+1}=\Psi(x^k+\alpha_k(x^k-x^{k-1}))\) for reasonable scalars \(\alpha_k\), that can be optimized to speed up convergence which results in a practical iteration formula. It is shown that the proposed AIRK is equivalent with the TSK method, but with a better error estimate under mild conditions. The two indices per iteration explain the `alternated' in its name. In a multistep version (MIRK), \(j_k\) is replaced by \(i_{k-1}\) and an optimal parameter is used to minimize the error for every choice of \(i_k\) (hence no alternation). Several numerical examples illustrate the performance for the different methods.\N\NThe paper is quite accessible introducing the successive complications step by step.
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A randomized Kaczmarz algorithm with exponential convergence
- Angenäherte Auflösung von Systemen linearer Gleichungen.
- Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
- Fast alternating direction optimization methods
- scientific article; zbMATH DE number 3853749 (Why is no real title available?)
- scientific article; zbMATH DE number 6252408 (Why is no real title available?)
- MiKM: multi-step inertial Krasnosel'skiǐ-Mann algorithm and its applications
- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- Numerical analysis of non-uniform sampling problem
- On greedy randomized Kaczmarz method for solving large sparse linear systems
- On the proximal gradient algorithm with alternated inertia
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Projection methods with alternating inertial steps for variational inequalities: weak and linear convergence
- Realization of the hybrid method for Mann iterations
- RidgeSketch: a fast sketching based solver for large scale ridge regression
- Row-Action Methods for Huge and Sparse Systems and Their Applications
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- Some methods of speeding up the convergence of iteration methods
- The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k^2
- Two-subspace projection method for coherent overdetermined systems
This page was built for publication: Inertial randomized Kaczmarz algorithms for solving coherent linear systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6992068)
