  We propose iterative projection methods for solving square or rectangular
consistent linear systems Ax = b. Existing projection methods use sketching
matrices (possibly randomized) to generate a sequence of small projected
subproblems, but even the smaller systems can be costly. We develop a process
that appends one column to the sketching matrix each iteration and converges in
a finite number of iterations whether the sketch is random or deterministic. In
general, our process generates orthogonal updates to the approximate solution
xk. By choosing the sketch to be the set of all previous residuals, we obtain a
simple recursive update and convergence in at most rank(A) iterations (in exact
arithmetic). By choosing a sequence of identity columns for the sketch, we
develop a generalization of the Kaczmarz method. In experiments on large sparse
systems, our method (PLSS) with residual sketches is competitive with LSQR and
LSMR, and with residual and identity sketches compares favorably with
state-of-the-art randomized methods.
