RANDOMIZED KACZMARZ ALGORITHMS: EXACT MSE ANALYSIS AND OPTIMAL SAMPLING PROBABILITIES | |
Agaskar, A4; Wang, C1,3; Lu, YM | |
2014 | |
会议日期 | DEC 03-05, 2014 |
会议地点 | Atlanta, GA |
关键词 | ALGEBRAIC RECONSTRUCTION TECHNIQUES |
页码 | 389-393 |
英文摘要 | The Kaczmarz method, or the algebraic reconstruction technique (ART), is a popular method for solving large-scale overdetermined systems of equations. Recently, Strohmer et al. proposed the randomized Kaczmarz algorithm, an improvement that guarantees exponential convergence to the solution. This has spurred much interest in the algorithm and its extensions. We provide in this paper an exact formula for the mean squared error (MSE) in the value reconstructed by the algorithm. We also compute the exponential decay rate of the MSE, which we call the "annealed" error exponent. We show that the typical performance of the algorithm is far better than the average performance. We define the "quenched" error exponent to characterize the typical performance. This is far harder to compute than the annealed error exponent, but we provide an approximation that matches empirical results. We also explore optimizing the algorithm's row-selection probabilities to speed up the algorithm's convergence. |
会议录 | 2014 IEEE GLOBAL CONFERENCE ON SIGNAL AND INFORMATION PROCESSING (GLOBALSIP)
![]() |
会议录出版者 | IEEE |
会议录出版地 | NEW YORK |
语种 | 英语 |
ISBN号 | 978-1-4799-7088-9 |
WOS研究方向 | Computer Science ; Engineering |
内容类型 | 会议论文 |
源URL | [http://ir.itp.ac.cn/handle/311006/23599] ![]() |
专题 | SCI会议论文 |
作者单位 | 1.MIT Lincoln Lab, Lexington, MA 02420 USA 2.Univ Chinese Acad Sci, Beijing 100049, Peoples R China 3.Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China 4.[Agaskar, Ameya; Lu, Yue M.] Harvard Univ, Cambridge, MA 02138 USA |
推荐引用方式 GB/T 7714 | Agaskar, A,Wang, C,Lu, YM. RANDOMIZED KACZMARZ ALGORITHMS: EXACT MSE ANALYSIS AND OPTIMAL SAMPLING PROBABILITIES[C]. 见:. Atlanta, GA. DEC 03-05, 2014. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论