The Kaczmarz method is an algorithm for finding the solution to an
overdetermined system of linear equations Ax=b by iteratively projecting onto
the solution spaces. The randomized version put forth by Strohmer and Vershynin
yields provably exponential convergence in expectation, which for highly
overdetermined systems even outperforms the conjugate gradient method. In this
article we present a modified version of the randomized Kaczmarz method which
at each iteration selects the optimal projection from a randomly chosen set,
which in most cases significantly improves the convergence rate. We utilize a
Johnson-Lindenstrauss dimension reduction technique to keep the runtime on the
same order as the original randomized version, adding only extra preprocessing
time. We present a series of empirical studies which demonstrate the remarkable
acceleration in convergence to the solution using this modified approach.