期刊
LINEAR ALGEBRA AND ITS APPLICATIONS
卷 441, 期 -, 页码 199-221出版社
ELSEVIER SCIENCE INC
DOI: 10.1016/j.laa.2012.12.022
关键词
Block Kaczmarz; Projections onto convex sets; Algebraic reconstruction technique; Matrix paving
资金
- ONR award [N00014-08-1-0883, N00014-11-1002]
- AFOSR award [FA9550-09-1-0643]
- DARPA award [N66001-08-1-2065]
- Sloan Research Fellowship
The block Kaczmarz method is an iterative scheme for solving overdetermined least-squares problems. At each step, the algorithm projects the current iterate onto the solution space of a subset of the constraints. This paper describes a block Kaczmarz algorithm that uses a randomized control scheme to choose the subset at each step. This algorithm is the first block Kaczmarz method with an (expected) linear rate of convergence that can be expressed in terms of the geometric properties of the matrix and its submatrices. The analysis reveals that the algorithm is most effective when it is given a good row paving of the matrix, a partition of the rows into well-conditioned blocks. The operator theory literature provides detailed information about the existence and construction of good row pavings. Together, these results yield an efficient block Kaczmarz scheme that applies to many overdetermined least-squares problem. (C) 2013 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据