Distributed Inference Over Directed Networks: Performance Limits and Optimal Design

DOI10.1109/TSP.2016.2543209zbMATH Open1414.94051arXiv1504.07526OpenAlexW1809903287MaRDI QIDQ4619633FDOQ4619633

Bruno Sinopoli, João Xavier, Dragana Bajović, José M. F. Moura

Publication date: 7 February 2019

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

Abstract: We find large deviations rates for consensus-based distributed inference for directed networks. When the topology is deterministic, we establish the large deviations principle and find exactly the corresponding rate function, equal at all nodes. We show that the dependence of the rate function on the stochastic weight matrix associated with the network is fully captured by its left eigenvector corresponding to the unit eigenvalue. Further, when the sensors' observations are Gaussian, the rate function admits a closed form expression. Motivated by these observations, we formulate the optimal network design problem of finding the left eigenvector which achieves the highest value of the rate function, for a given target accuracy. This eigenvector therefore minimizes the time that the inference algorithm needs to reach the desired accuracy. For Gaussian observations, we show that the network design problem can be formulated as a semidefinite (convex) program, and hence can be solved efficiently. When observations are identically distributed across agents, the system exhibits an interesting property: the graph of the rate function always lies between the graphs of the rate function of an isolated node and the rate function of a fusion center that has access to all observations. We prove that this fundamental property holds even when the topology and the associated system matrices change randomly over time, with arbitrary distribution. Due to generality of its assumptions, the latter result requires more subtle techniques than the standard large deviations tools, contributing to the general theory of large deviations.

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

Recommendations

• DISTRIBUTED INFERENCE IN BAYESIAN NETWORKS
• Structured Variational Methods for Distributed Inference in Networked Systems: Design and Analysis
• Efficient design and inference in distributed Bayesian networks: an overview
• Distributed estimation over complex networks
• Distributed Inference With Sparse and Quantized Communication
• Distributed inference in wireless sensor networks
• Distributed Inference in Tree Networks Using Coding Theory
• Distributed Stochastic Approximation: Weak Convergence and Network Design
• Distributed Optimization Over Dependent Random Networks
• Distributed estimation of algebraic connectivity of directed networks

Mathematics Subject Classification ID

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

Cited In (1)

• Dense limit of the Dawid–Skene model for crowdsourcing and regions of sub-optimality of message passing algorithms

This page was built for publication: Distributed Inference Over Directed Networks: Performance Limits and Optimal Design

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