  We provide a complete characterization of the randomized Kaczmarz algorithm
(RKA) for inconsistent linear systems. The Kaczmarz algorithm, known in some
fields as the algebraic reconstruction technique, is a classical method for
solving large-scale overdetermined linear systems through a sequence of
projection operators; the randomized Kaczmarz algorithm is a recent proposal by
Strohmer and Vershynin to randomize the sequence of projections in order to
guarantee exponential convergence (in mean square) to the solutions. A flurry
of work followed this development, with renewed interest in the algorithm, its
extensions, and various bounds on their performance. Earlier, we studied the
special case of consistent linear systems and provided an exact formula for the
mean squared error (MSE) in the value reconstructed by RKA, as well as a simple
way to compute the exact decay rate of the error. In this work, we consider the
case of inconsistent linear systems, which is a more relevant scenario for most
applications. First, by using a "lifting trick", we derive an exact formula for
the MSE given a fixed noise vector added to the measurements. Then we show how
to average over the noise when it is drawn from a distribution with known first
and second-order statistics. Finally, we demonstrate the accuracy of our exact
MSE formulas through numerical simulations, which also illustrate that previous
upper bounds in the literature may be several orders of magnitude too high.
