Fast Decentralized Linear Functions Via Successive Graph Shift Operators

Decentralized signal processing performs learning tasks on data distributed over a multi-node network which can be represented by a graph. Implementing linear transformations emerges as a key task in a number of applications of decentralized signal processing. Recently, some decentralized methods have been proposed to accomplish that task by leveraging the notion of graph shift operator, which captures the local structure of the graph. However, existing approaches have some drawbacks such as considering special instances of linear transformations, or reducing the family of transformations by assuming that a shift matrix is given such that a subset of its eigenvectors spans the subspace of interest. In contrast, this paper develops a decentralized method to compute linear transformations in a small number of iterations. To this end, a set of successive graph shift operators is designed. Hence, a new optimization problem is proposed whose goal is to compute the desired transformation as fast as possible.