  We study a version of the randomized Kaczmarz algorithm for solving systems
of linear equations where the iterates are confined to the solution space of a
selected subsystem. We show that the subspace constraint leads to an
accelerated convergence rate, especially when the system has approximately
low-rank structure. On Gaussian-like random data, we show that it results in a
form of dimension reduction that effectively increases the aspect ratio of the
system. Furthermore, this method serves as a building block for a second,
quantile-based algorithm for solving linear systems with arbitrary sparse
corruptions, which is able to efficiently utilize external knowledge about
corruption-free equations and achieve convergence in difficult settings.
Numerical experiments on synthetic and realistic data support our theoretical
results and demonstrate the validity of the proposed methods for even more
general data models than guaranteed by the theory.
