Kaczmarz Kac Walk

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 ${\sigma }_{\mathrm{\ell }}(A^{(k)})\sim \exp (k\mathrm{/}{n}^2)\cdot {\sigma }_{\mathrm{\ell }}(A)$.