Solving A System Of Linear Equations By Randomized Orthogonal Projectors

Randomization has been shown to be beneficial to iterative methods for solving large-scale systems of linear equations, notably the Kaczmarz algorithm. We analyze the convergence of a broad class of pursuit algorithms that at each step pick $n$ members at random, from a system of linear equations, and update the iterate using the orthogonal projection to the intersection of the hyperplanes they represent. We identify, in this context, a specific degree-$n$ polynomial that non-linearly transforms the singular values of the system. This transformation to singular values and the corresponding condition number then characterizes the convergence rate, in expectation, of the pursuit. 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.