An accelerated randomized extended Kaczmarz algorithm

7th International Conference on Applied Physics and Mathematics

物理学;数学

Xiang, Xu^1 ; Liu, Xu^1 ; Tan, Wentang^1 ; Dai, Xiang^1

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;   

Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/814/1/012017/pdf
DOI  :  10.1088/1742-6596/814/1/012017

来源: IOP

【 摘 要 】

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.