  In this technical report we present a Projection onto Convex Sets (POCS) type
algorithm for solving systems of linear equations. POCS methods have found many
applications ranging from computer tomography to digital signal and image
processing. The Kaczmarz method is one of the most popular solvers for
overdetermined systems of linear equations due to its speed and simplicity.
Here we introduce and analyze an extension of the Kaczmarz method which
iteratively projects the estimate onto a solution space given from two randomly
selected rows. We show that this projection algorithm provides exponential
convergence to the solution in expectation. The convergence rate significantly
improves upon that of the standard randomized Kaczmarz method when the system
has coherent rows. We also show that the method is robust to noise, and
converges exponentially in expectation to the noise floor. Experimental results
are provided which confirm that in the coherent case our method significantly
outperforms the randomized Kaczmarz method.
