报告题目：Randomized Iterative Methods for Linear Systems: Generalization and Acceleration

报告时间：2022-09-09  20:00 - 21:00

报告人：韩德仁 教授  北京航空航天大学

腾讯会议ID：170-708-501

Abstract：We present a new framework for the analysis and design of randomized algorithms for solving various types of linear systems, including consistent or inconsistent, full rank or rank-defificient. Our method is formulated with four randomized sampling parameters, which allows the method to cover many existing randomization algorithms within a unified framework, including the doubly stochastic Gauss-Seidel, randomized Kaczmarz method, randomized coordinate descent method, and Gaussian Kaczmarz 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 introduced in our framework for improving the convergence behavior of the method. We prove the global linear convergence rates of our method as well as an accelerated linear rate for the case of the norm of expected iterates.