Distributed algorithms with finite data rates that solve linear equations

Abstract

In this paper, we study network linear equations subject to digital communications with a finite data rate, where each node is associated with one equation from a system of linear equations. Each node holds a dynamic state and interacts with its neighbors through an undirected connected graph, where along each link the pair of nodes share information. Due to the data rate constraint, each node builds an encoder/decoder pair, with which it produces transmitted messages with a zooming-in finite-level uniform quantizer and also generates estimates of its neighbors' states from the received signals. We then propose a distributed quantized algorithm and show that when the network linear equations admit a unique solution, each node's state is driven to that solution exponentially fast. We further analyze the asymptotic rate of convergence and show that a larger number of quantization levels leads to a faster convergence rate although the rate is still fundamentally bounded by the inherent network structure and the linear equations. In addition, we establish a bound on the total number of communication bits required to obtain a solution with a prescribed accuracy. When a unique least-squares solution exists, we show that the algorithm can compute such a solution with a suitably selected time-varying step-size inherited from the encoder and zooming-in quantizer dynamics. In both cases, a minimal data rate is shown to be enough for guaranteeing the desired convergence when the algorithm parameters are properly chosen. These results ensure the applicability of various network linear equation solvers when peer-to-peer communication is digital. Show more