Kaczmarz Kac Walk

Abstract

The Kaczmarz method is a way to iteratively solve a linear system of equations $Ax=b$. One interprets the solution $x$ as the point where hyperplanes intersect and then iteratively projects an approximate solution onto these hyperplanes to get better and better approximations. We note a somewhat related idea: one could take two random hyperplanes and project one into the orthogonal complement of the other. This leads to a sequence of linear systems $A^{(k)}x=b^{(k)}$ which is fast to compute, preserves the original solution and whose small singular values grow like $\ddot{I}{ƒ}_{\ell }(A^{(k)})\sim \exp (k/n^2)\cdot \ddot{I}{ƒ}_{\ell }(A)$.