Randomized iterative methods for linear systems: Generalization and acceleration
Speaker: Prof.Deren Han
Topic: Randomized iterative methods for linear systems: Generalization and acceleration
Time & Date: on April 03 (Monday) 10:00-11:00 (Beijing Time)
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.
韩德仁：教授，博士生导师，现任北京航空航天大学数学科学学院院长、教育部数学类专业教指委秘书长。2002年获南京大学计算数学博士学位。从事大规模优化问题、变分不等式问题的数值方法的研究工作，以及优化和变分不等式问题在交通规划、磁共振成像中的应用，发表多篇学术论文。曾获中国运筹学会青年科技奖，江苏省科技进步奖等奖项;主持国家自然科学基金杰出青年基金等多项项目。担任中国运筹学会常务理事；《数值计算与计算机应用》、《Journal of the Operations Research Society of China》、《Journal of Global Optimization》编委。