Unifying Random-Asynchronous Algorithms for Numerical Methods, Using Switching Systems Theory

Abstract

Randomized variants of iterative techniques such as Kaczmarz method, Gauss-Seidel method and asynchronous fixed-point iterations have been of interest in recent years. Due to their randomized nature, these techniques are better suited for processing of large scale and distributed data. Despite their effectiveness, their theoretical analysis has been of interest only in recent years. In the mean-time, control theory literature has studied switching systems rigorously in order to understand the behavior of systems whose dynamics change over time. This paper shows that randomized iterative algorithms can be represented as switching systems. Thus, convergence properties of such randomized algorithms follow directly from the stability theory already developed for switching systems. As an example, alternative proofs are provided for the mean-squared and almost sure convergence of randomized Kaczmarz and Gauss-Seidel methods. The necessary and sufficient condition for the mean-squared convergence of random asynchronous fixed-point iterations is also provided.

Additional details