  The randomized Kaczmarz (RK) method is an iterative method for approximating
the least-squares solution of large linear systems of equations. The standard
RK method uses sequential updates, making parallel computation difficult. Here,
we study a parallel version of RK where a weighted average of independent
updates is used. We analyze the convergence of RK with averaging and
demonstrate its performance empirically. We show that as the number of threads
increases, the rate of convergence improves and the convergence horizon for
inconsistent systems decreases.
