An Arrow-Hurwicz-Uzawa Type Flow as Least Squares Solver for Network Linear Equations
It provides a distributed algorithm for solving linear equations over networks with provable exponential convergence, which is incremental as it extends existing optimization flows to a new problem setting.
This paper develops a continuous-time distributed least squares solver for network linear equations using an Arrow-Hurwicz-Uzawa type flow, achieving exponential convergence under a necessary and sufficient condition on the graph Laplacian. A discrete-time version via Euler's method also converges exponentially with suitable step size, and switching networks at high frequencies can approximate least squares solvers even when individual graphs cannot.
We study the approach to obtaining least squares solutions to systems of linear algebraic equations over networks by using distributed algorithms. Each node has access to one of the linear equations and holds a dynamic state. The aim for the node states is to reach a consensus as a least squares solution of the linear equations by exchanging their states with neighbors over an underlying interaction graph. A continuous-time distributed least squares solver over networks is developed in the form of the famous Arrow-Hurwicz-Uzawa flow. A necessary and sufficient condition is established on the graph Laplacian for the continuous-time distributed algorithm to give the least squares solution in the limit, with an exponentially fast convergence rate. The feasibility of different fundamental graphs is discussed including path graph, star graph, etc. Moreover, a discrete-time distributed algorithm is developed by Euler's method, converging exponentially to the least squares solution at the node states with suitable step size and graph conditions. The exponential convergence rate for both the continuous-time and discrete-time algorithms under the established conditions is confirmed by numerical examples. Finally, we investigate the performance of the proposed flow under switching networks, and surprisingly, switching networks at high switching frequencies can lead to approximate least square solvers even if all graphs in the switching signal fail to do so in the absence of structure switching.