  Randomization has shown catalyzing effects in linear algebra with promising
perspectives for tackling computational challenges in large-scale problems. For
solving a system of linear equations, we demonstrate the convergence of a broad
class of algorithms that at each step pick a subset of $n$ equations at random
and update the iterate with the orthogonal projection to the subspace those
equations represent. We identify, in this context, a specific degree-$n$
polynomial that non-linearly transforms the singular values of the system
towards equalization. This transformation to singular values and the
corresponding condition number then characterizes the expected convergence rate
of iterations. As a consequence, our results specify the convergence rate of
the stochastic gradient descent algorithm, in terms of the mini-batch size $n$,
when used for solving systems of linear equations.
