best365网页版登录学术报告

A Semi-Randomized Augmented Kaczmarz Method with Simple Random Sampling

for Solving Large-Scale Inconsistent Linear Systems

吴钢

（中国矿业大学 数学学院）

报告时间：2023年6月15日 星期四 上午9:00-10:00

报告地点：#腾讯会议：819-424-764 会议密码：0615

报告摘要：The randomized extended Kaczmarz (REK) method is an efficient iterative method for solving inconsistent linear systems, in which one has to solve two linear systems by using the randomized Kaczmarz method in each iteration. However, the REK method may converge slowly if one of the iteration sequences does so. Recently, a greedy randomized augmented Kaczmarz (GRAK) method was proposed, which is based on an appropriate balance between the updates about the two iteration vectors. The key is first transforming the inconsistent linear system of size $m$-by-$n$ into a consistent augmented linear system of size $(m+n)$-by-$(m+n)$, and then applying the greedy randomized Kaczmarz method to the augmented linear system. However, one has to compute the residual vector and construct an index set in each iteration, and the GRAK method may suffer from heavily computational overhead for big data problems. Specifically, the convergence rate of GRAK will be negatively affected when the chosen row indexes are between $m+1$ and $m+n$. The contributions of this work are as follows. First, to the best of our knowledge, it seems that there is no practical stopping criterion for all the randomized Kaczmarz-type method hitherto. In this work, we introduce a practical stopping criterion for GRAK and show its rationality from a theoretical point of view. Second, we consider how to update the two iteration vectors in GRAK efficiently, and propose an accelerated greedy randomized augmented Kaczmarz method. Third, we apply the semi-randomized Kaczmarz method to the augmented linear system, and propose a semi-randomized augmented Kaczmarz method with simple random sampling. In this method, there is no need to compute the residual vector of the linear system nor to construct an index set in each iteration. Thus, unlike the GRAK method, there is no need to access all the information of the data matrix in this method. The convergence of the proposed methods are established. Numerical results are performed on both real-world and synthetic data sets, which demonstrate the effectiveness of the proposed strategies, and show that the new methods are often superior to some state-of-the-art Kaczmarz methods for large-scale inconsistent linear systems.

报告人简介：吴钢，博士、中国矿业大学数学学院教授、博士生导师；江苏省“333 工程” 中青年科学技术带头人，江苏省“青蓝工程”中青年学术带头人，江苏省计算数学学会副理事长。主要研究方向：数值代数、机器学习与数据挖掘、大数据与人工智能中的快速算法等。主持国家自然科学基金项目、省自然科学基金项目、市厅重点研发计划等多项，在国际知名杂志，如：SIAM Journal on Numerical Analysis, SIAM Journal on Matrix Analysis and Applications, SIAM Journal on Scientific Computing, IMA Journal of Numerical Analysis, IEEE Transactions on Knowledge and Data Engineering, Pattern Recognition, Machine Learning, ACM Transactions on Information Systems 等期刊发表学术论文多篇。

邀请人： 谢家新