  Randomized linear system solvers have become popular as they have the
potential to reduce floating point complexity while still achieving desirable
convergence rates. One particularly promising class of methods, random
sketching solvers, has achieved the best known computational complexity bounds
in theory, but is blunted by two practical considerations: there is no clear
way of choosing the size of the sketching matrix apriori; and there is a
nontrivial storage cost of the sketched system. In this work, we make progress
towards addressing these issues by implicitly generating the sketched system
and solving it simultaneously through an iterative procedure. As a result, we
replace the question of the size of the sketching matrix with determining
appropriate stopping criteria; we also avoid the costs of explicitly
representing the sketched linear system; and our implicit representation also
solves the system at the same time, which controls the per-iteration
computational costs.
  Additionally, our approach allows us to generate a connection between random
sketching methods and randomized iterative solvers (e.g., randomized Kaczmarz
method, randomized Gauss-Seidel). As a consequence, we exploit this connection
to (1) produce a stronger, more precise convergence theory for such randomized
iterative solvers under arbitrary sampling schemes (i.i.d., adaptive,
permutation, dependent, etc.), and (2) improve the rates of convergence of
randomized iterative solvers at the expense of a user-determined increases in
per-iteration computational and storage costs. We demonstrate these concepts on
numerical examples on forty-nine distinct linear systems.
