A Distributed Newton Method for Processing Signals Defined on the Large-Scale Networks

In the graph signal processing (GSP) framework, distributed algorithms are highly desirable in processing signals defined on large-scale networks. However, in most existing distributed algorithms, all nodes homogeneously perform the local computation, which calls for heavy computational and communication costs. Moreover, in many real-world networks, such as those with straggling nodes, the homogeneous manner may result in serious delay or even failure. To this end, we propose active network decomposition algorithms to select non-straggling nodes (normal nodes) that perform the main computation and communication across the network. To accommodate the decomposition in different kinds of networks, two different approaches are developed, one is centralized decomposition that leverages the adjacency of the network and the other is distributed decomposition that employs the indicator message transmission between neighboring nodes, which constitutes the main contribution of this paper. By incorporating the active decomposition scheme, a distributed Newton method is employed to solve the least squares problem in GSP, where the Hessian inverse is approximately evaluated by patching a series of inverses of local Hessian matrices each of which is governed by one normal node. The proposed algorithm inherits the fast convergence of the second-order algorithms while maintains low computational and communication cost. Numerical examples demonstrate the effectiveness of the proposed algorithm.