Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma (Q639988)

To solve the system \(Ax=b\), \(A\in{\mathbb R}^{m\times n}\), the Kaczmarz algorithm updates in iteration \(k\) the vector \(x\) by projecting it orthogonally onto the hyperplane \(a_i^Tx=b_i\) where \(a_i\) is the \(i\)th row of \(A\). Hereby \(i\) changes cyclically. In the randomized version, \(i\) is chosen with a probability proportional to the relative norm of \(a_i\) [see \textit{T. Strohmer} and \textit{R. Vershynin}, J. Fourier Anal. Appl. 15, No.~2, 262--278 (2009; Zbl 1169.68052)]. In this paper the same idea is generalized by projecting the rows of \(A\) onto a lower dimensional subspace (Johnson-Lindenstrauss technique), which makes it more efficient to compute the optimal choice of \(i\). It is proved that the convergence rate is expected to be at least as fast as the classical randomized Kaczmarz method and it is experimentally shown to be much faster in most cases [cf. \textit{S. Kaczmarz}, Bull. Int. Acad. Polon. Sci. A 1937, 355--357 (1937; Zbl 0017.31703)].