UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Preasymptotic convergence of randomized Kaczmarz method

Jiao, Y; Jin, B; Lu, X; (2017) Preasymptotic convergence of randomized Kaczmarz method. Inverse Problems , 33 (12) , Article 125012. 10.1088/1361-6420/aa8e82. Green open access

[img]
Preview
Text
rkm_revise3.pdf - ["content_typename_Accepted version" not defined]

Download (4MB) | Preview

Abstract

Kaczmarz method is one popular iterative method for solving inverse problems, especially in computed tomography. Recently, it was established that a randomized version of the method enjoys an exponential convergence for well-posed problems, and the convergence rate is determined by a variant of the condition number. In this work, we analyze the preasymptotic convergence behavior of the randomized Kaczmarz method, and show that the low-frequency error (with respect to the right singular vectors) decays faster during first iterations than the high-frequency error. Under the assumption that the inverse solution is smooth (e.g., sourcewise representation), the result explains the fast empirical convergence behavior, thereby shedding new insights into the excellent performance of the randomized Kaczmarz method in practice. Further, we propose a simple strategy to stabilize the asymptotic convergence of the iteration by means of variance reduction. We provide extensive numerical experiments to confirm the analysis and to elucidate the behavior of the algorithms.

Type: Article
Title: Preasymptotic convergence of randomized Kaczmarz method
Open access status: An open access version is available from UCL Discovery
DOI: 10.1088/1361-6420/aa8e82
Publisher version: http://doi.org/10.1088/1361-6420/aa8e82
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: Randomized Kaczmarz method; preasymptotic convergence; smoothness; error estimates; variance reduction
UCL classification: UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: http://discovery.ucl.ac.uk/id/eprint/1575724
Downloads since deposit
31Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item