Randomized Kaczmarz algorithms: Exact MSE analysis and optimal sampling probabilities

DSpace/Manakin Repository

Randomized Kaczmarz algorithms: Exact MSE analysis and optimal sampling probabilities

Citable link to this page

 

 
Title: Randomized Kaczmarz algorithms: Exact MSE analysis and optimal sampling probabilities
Author: Agaskar, Ameya; Wang, Chuang; Lu, Yue

Note: Order does not necessarily reflect citation order of authors.

Citation: Agaskar, A., Wang, C., and Y. M. Lu. 2014. “Randomized Kaczmarz algorithms: Exact MSE analysis and optimal sampling probabilities” In the Proceedings of the 2014 IEEE Global Conference on Signal and Information Processing (GlobalSIP), Atlanta, GA, December 3-5: 389-393.
Full Text & Related Files:
Abstract: 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 computethan 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.
Published Version: doi:10.1109/globalsip.2014.7032145
Other Sources: http://lu.seas.harvard.edu/files/yuelu/files/randkac_globalsip14.pdf
Terms of Use: This article is made available under the terms and conditions applicable to Open Access Policy Articles, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#OAP
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:25482691
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)

 
 

Search DASH


Advanced Search
 
 

Submitters