Recently, a class of algorithms combining classical fixed-point iterations with repeated random sparsification of approximate solution vectors has been successfully applied to eigenproblems with matrices as large as . So far, a complete mathematical explanation for this success has proven elusive. The family of methods has not yet been extended to the important case of linear system solves. In this paper, we propose a new scheme based on repeated random sparsification that is capable of solving sparse linear systems in arbitrarily high dimensions. We provide a complete mathematical analysis of this new algorithm. Our analysis establishes a faster-than-Monte Carlo convergence rate and justifies use of the scheme even when the solution is too large to store as a dense vector.