Acceleration of Cooperative Least Mean Square via Chebyshev Periodical Successive Over-Relaxation

A distributed algorithm for least mean square (LMS) can be used in distributed signal estimation and in distributed training for multivariate regression models. The convergence speed of an algorithm is a critical factor because a faster algorithm requires less communications overhead and it results in a narrower network bandwidth. The goal of this paper is to present that use of Chebyshev periodical successive over-relaxation (PSOR) can accelerate distributed LMS algorithms in a naturally manner. The basic idea of Chbyshev PSOR is to introduce index-dependent PSOR factors that control the spectral radius of a matrix governing the convergence behavior of the modified fixed-point iteration. Accelerations of convergence speed are empirically confirmed in a wide range of networks, such as known small graphs (e.g., Karate graph), and random graphs, such as Erdos-Renyi (ER) random graphs and Barabasi-Albert random graphs.