科学研究
报告题目:

A Kaczmarz Method with Simple Random Sampling for Solving Large Linear Systems

报告人:

吴钢 教授(中国矿业大学)

报告时间:

报告地点:

腾讯会议 ID:408 520 583 会议密码:1031

报告摘要:

The Kaczmarz method is a popular iterative scheme for solving large, consistent system of over-determined linear equations. It may converge very slowly in practice. The randomized Kaczmarz method (RK) can greatly improve the convergence rate, which is further improved by a greedy randomized Kaczmarz method (GRK). However, the greedy Kaczmarz method may suffer from heavily computational cost when the size of the matrix is large, and the overhead will be prohibitively large for big data problems. Our main contributions include the following three aspects. First, from the probability significance point of view, we present a partially randomized Kaczmarz method to reduce the computational overhead needed in GRK. Second, based on Chebyshev's law of large numbers and Z-test, we apply a simple sampling approach to the partially randomized Kaczmarz method, and propose a randomized Kaczmarz method with simple random sampling for large linear systems. The convergence of the proposed method is established. Third, we apply the new strategy to the ridge regression problem, and propose a new probability criterion that can capture larger entries of the residual vector at each iteration step.