@conference {208966,
	title = {Randomized Kaczmarz algorithms: Exact MSE analysis and optimal sampling probabilities},
	booktitle = {IEEE Global Conference on Signal and Information Processing (GlobalSIP)},
	year = {2014},
	note = {(This paper received the Best Student Paper Award of GlobalSIP)},
	month = {Dec.},
	address = {Atlanta, GA},
	abstract = {The Kaczmarz method, or the algebraic reconstruction technique\&nbsp;(ART), is a popular method for solving large-scale overdetermined\&nbsp;systems of equations. Recently, Strohmer et al. proposed the randomized\&nbsp;Kaczmarz algorithm, an improvement that guarantees exponential\&nbsp;convergence to the solution. This has spurred much interest\&nbsp;in the algorithm and its extensions. We provide in this paper an exact\&nbsp;formula for the mean squared error (MSE) in the value reconstructed\&nbsp;by the algorithm. We also compute the exponential decay rate of\&nbsp;the MSE, which we call the {\textquotedblleft}annealed{\textquotedblright} error exponent. We show\&nbsp;that the typical performance of the algorithm is far better than the\&nbsp;average performance. We define the {\textquotedblleft}quenched{\textquotedblright} error exponent to\&nbsp;characterize the typical performance. This is far harder to compute\&nbsp;than the annealed error exponent, but we provide an approximation\&nbsp;that matches empirical results. We also explore optimizing the\&nbsp;algorithm{\textquoteright}s row-selection probabilities to speed up the algorithm{\textquoteright}s\&nbsp;convergence.},
	author = {Agaskar, A. and C Wang and Lu, Y.M.}
}
