Chebyshev Polynomials in Distributed Consensus Applications

• Published in: IEEE transactions on signal processing 2013-02, Vol.61 (3), p.693-706
• Main Authors: Montijano, E., Montijano, J. I., Sagues, C.
• Format: Article
• Language: English
• Subjects: Algorithms; Applied sciences; Approximation; Approximation algorithms; Chebyshev approximation; Chebyshev polynomials; Convergence; convergence rate; Detection, estimation, filtering, equalization, prediction; distributed consensus; Eigenvalues and eigenfunctions; Exact sciences and technology; Information, signal and communications theory; Mathematical analysis; Network topology; Networks; Polynomials; Signal and communications theory; Signal, noise; Studies; Telecommunications and information theory; Topology; Transaction processing
• ISSN: 1053-587X; 1941-0476
• DOI: 10.1109/TSP.2012.2226173

In this paper we analyze the use of Chebyshev polynomials in distributed consensus applications. It is well known that the use of polynomials speeds up the convergence to the consensus in a significant way. However, existing solutions only work for low degree polynomials and require the topology of the network to be fixed and known. We propose a distributed algorithm based on the second order difference equation that describes the Chebyshev polynomials of first kind. The contributions of our algorithm are three: (i) Since the evaluation of Chebyshev polynomials is stable, there is no limitation in the degree of the polynomial. (ii) Instead of the knowledge of the whole network topology, it only requires a partial knowledge or an approximation to it. (iii) It can be applied to time varying topologies. In the paper we characterize the main properties of the algorithm for both fixed and time-varying communication topologies. Theoretical results, as well as experiments with synthetic data, show the benefits of using our algorithm compared to existing methods.