期刊
NUMERICAL ALGORITHMS
卷 58, 期 2, 页码 163-177出版社
SPRINGER
DOI: 10.1007/s11075-011-9451-z
关键词
Kaczmarz method; Randomized Kaczmarz method; Computer tomography; Signal processing
资金
- NSF
- Israel Science Foundation [1081/07]
The Kaczmarz method is an algorithm for finding the solution to an overdetermined consistent system of linear equations Ax = b by iteratively projecting onto the solution spaces. The randomized version put forth by Strohmer and Vershynin yields provably exponential convergence in expectation, which for highly overdetermined systems even outperforms the conjugate gradient method. In this article we present a modified version of the randomized Kaczmarz method which at each iteration selects the optimal projection from a randomly chosen set, which in most cases significantly improves the convergence rate. We utilize a Johnson-Lindenstrauss dimension reduction technique to keep the runtime on the same order as the original randomized version, adding only extra preprocessing time. We present a series of empirical studies which demonstrate the remarkable acceleration in convergence to the solution using this modified approach.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据