An accelerated randomized extended Kaczmarz algorithm

[摘要] The randomized Kaczmarz(RK) is a useful algorithm for solving consistent linear system A x = b (A ∈m×n, b ∈ ). It was proved that for inconsistent linear system, with randomized orthogonal projection, the randomized extended Kaczmarz(REK) method converges with an expected exponential rate. We describe an accelerated randomized extended Kaczmarz algorithm(AREK) with Nesterov's accelerated procedure. The analysis shows that AREK converges better than REK when A is dense and the smallest singular value of ATA is small.

[发布机构] Southwest Electronics and Telecommunication Technology Research Institute, Chengdu, Sichuan; 610041, China^1

[效力级别] 数学

[关键词] Algorithm for solving;Exponential rates;Inconsistent linear systems;Kaczmarz;Kaczmarz algorithm;Orthogonal projection;Singular values