Randomized Kaczmarz algorithm

We propose and analyze a randomized iterative variant of the popular Kaczmarz algorithm for solving large-scale linear systems. The scheme features exponential convergence in the m.s to the minimum-norm least-squares solution of a given linear system of equations. The expected number of arithmetic operations is proportional to the squared condition number of the system multiplied by the number of non-zero entries of the input matrix. We experimentally test the performance against the vastly mature literature of state-of-art linear solvers and showcase improvements. In sensor networks, we study the problem of estimation from noisy relative measurements, i.e., differences of nodal values across edges. We use Randomized Kaczmarz to design and analyze a new class of distributed asynchronous consensus algorithms, and analyze the convergence rate depending solely on properties of the network topology. Inspired by the analytical insights, we propose Randomized Kaczmarz Over-smoothing (RKO), which has demonstrated, in both theory and simulations, improvement over existing protocols in terms of both convergence speed-up and energy savings.