Distributed Finite time Least Squares Solver for Network Linear Equations
In this paper, we study the problem of finding the least square solutions of over determined linear algebraic equations over networks in a distributed manner. Each node has access to one of the linear equations and holds a dynamic state. We first propose a distributed least square solver over undirected interaction graphs, for which we establish the conditions on the interaction graphs and the step size under which the proposed algorithm exponentially converges to the least square solution. Next, we develop a finite time least square solver by equipping the proposed algorithm with a finite time decentralized computation mechanism. The proposed finite time computation mechanism enables an arbitrarily chosen node to compute the least square solution in a finite number of time steps, by using its own local successive state values obtained from the underlying algorithm. Finally, we discuss how to extend the proposed algorithm to directed interaction graphs and how the finite time computation mechanism computes the least square solution even when the underlying algorithms diverge. The theoretical findings are validated and illustrated by numerical simulation examples.