Topology for Distributed Inference on Graphs

DOI10.1109/TSP.2008.923536MaRDI QIDQ4568759zbMATH OpenOpenAlexFDO

Authors Soummya Kar, Saeed A. Aldosari, José M. F. Moura

Publication date 27 June 2018

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0606052

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Let $N$ local decision makers in a sensor network communicate with their neighbors to reach a decision emph{consensus}. Communication is local, among neighboring sensors only, through noiseless or noisy links. We study the design of the network topology that optimizes the rate of convergence of the iterative decision consensus algorithm. We reformulate the topology design problem as a spectral graph design problem, namely, maximizing the eigenratio~$gamma$ of two eigenvalues of the graph Laplacian~$L$, a matrix that is naturally associated with the interconnectivity pattern of the network. This reformulation avoids costly Monte Carlo simulations and leads to the class of non-bipartite Ramanujan graphs for which we find a lower bound on~$gamma$. For Ramanujan topologies and noiseless links, the local probability of error converges much faster to the overall global probability of error than for structured graphs, random graphs, or graphs exhibiting small-world characteristics. With noisy links, we determine the optimal number of iterations before calling a decision. Finally, we introduce a new class of random graphs that are easy to construct, can be designed with arbitrary number of sensors, and whose spectral and convergence properties make them practically equivalent to Ramanujan topologies.

Cited in

(5)

• Coordination of discrete-time multi-agent systems via relative output feedback
• scientific article; zbMATH DE number 1305408 (Why is no real title available?)
• Distributed estimation over complex networks
• Efficient, Decentralized Computation of the Topology of Spatial Regions
• Spectrum of random d‐regular graphs up to the edge

This page was built for publication: Topology for Distributed Inference on Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4568759)