On pseudoinverse-free randomized methods for linear systems: unified framework and acceleration
Deren Han, Jiaxin Xie
Abstract
This paper presents a novel framework for the analysis and design of randomized algorithms for solving linear systems, including consistent or inconsistent, full rank or rank-deficient. The framework is formulated with four randomized sampling parameters, which allows for the unification of existing randomization algorithms, such as the doubly stochastic Gauss-Seidel (DSGS) method, randomized Kaczmarz (RK) method, and randomized coordinate descent (RCD) method. Compared with the projection-based block algorithms where a pseudoinverse for solving a least-squares problem is utilized at each iteration, our design is pseudoinverse-free. Furthermore, the flexibility of the new approach also enables the design of a number of new methods as special cases. Polyak's heavy ball momentum technique is also incorporated into the framework to improve the convergence behaviour of the method. An alternative convergence analysis of momentum variants of randomized iterative methods is proposed, where smaller convergence factors for RK and RCD with momentum are obtained. Additionally, an accelerated linear rate for the case of the norm of expected iterates is proven. Finally, numerical experiments are provided to confirm our results.