Randomized Kaczmarz converges along small singular vectors

Randomized Kaczmarz is a simple iterative method for finding solutions of linear systems Ax = b. We point out that the arising sequence (xk)k=1∞ tends to converge to the solution x in an interesting way: generically, as k rightarrow ∞, xk - x tends to the singular vector of A corresponding to the smallest singular value. This has interesting consequences: in particular, the error analysis of Strohmer & Vershynin is optimal. It also quantifies the `pre-convergence' phenomenon where the method initially seems to converge faster. This fact also allows for a fast computation of vectors x for which the Rayleigh quotient |Ax|/|x| is small: solve Ax = 0 via Randomized Kaczmarz.