  We develop a novel, fundamental and surprisingly simple randomized iterative
method for solving consistent linear systems. Our method has six different but
equivalent interpretations: sketch-and-project, constrain-and-approximate,
random intersect, random linear solve, random update and random fixed point. By
varying its two parameters$-$a positive definite matrix (defining geometry),
and a random matrix (sampled in an independently and identically distributed
fashion in each iteration)$-$we recover a comprehensive array of well-known
algorithms as special cases, including the randomized Kaczmarz method,
randomized Newton method, randomized coordinate descent method and random
Gaussian pursuit. We naturally also obtain variants of all these methods using
blocks and importance sampling. However, our method allows for a much wider
selection of these two parameters, which leads to a number of new specific
methods. We prove exponential convergence of the expected norm of the error in
a single theorem, from which existing complexity results for known variants can
be obtained. However, we also give an exact formula for the evolution of the
expected iterates, which allows us to give lower bounds on the convergence
rate.
