Weight Optimization for Consensus Algorithms with Correlated Switching Topology

Abstract

We design the weights in consensus algorithms with spatially correlated random topologies. These arise with: 1) networks with spatially correlated random link failures and 2) networks with randomized averaging protocols. We show that the weight optimization problem is convex for both symmetric and asymmetric random graphs. With symmetric random networks, we choose the consensus mean squared error (MSE) convergence rate as optimization criterion and explicitly express this rate as a function of the link formation probabilities, the link formation spatial correlations, and the consensus weights. We prove that the MSE convergence rate is a convex, nonsmooth function of the weights, enabling global optimization of the weights for arbitrary link formation probabilities and link correlation structures. We extend our results to the case of asymmetric random links. We adopt as optimization criterion the mean squared deviation (MSdev) of the nodes states from the current average state. We prove that MSdev is a convex function of the weights. Simulations show that significant performance gain is achieved with our weight design method when compared with methods available in the literature.

30 pages, 5 figures, submitted to IEEE Transactions On Signal Processing

References in corpus (1)

• Sensor Networks with Random Links: Topology Design for Distributed Consensus

Cited by in corpus (16)

• Gossip Algorithms for Distributed Signal Processing
• Diffusion Strategies Outperform Consensus Strategies for Distributed Estimation over Adaptive Networks
• Convergence Rate Analysis of Distributed Gossip (Linear Parameter) Estimation: Fundamental Limits and Tradeoffs
• Diffusion Adaptation over Networks under Imperfect Information Exchange and Non-stationary Data
• Distributed Detection over Noisy Networks: Large Deviations Analysis
• Large Deviations Performance of Consensus+Innovations Distributed Detection with Non-Gaussian Observations
• Convergence Rates of Distributed Nesterov-like Gradient Methods on Random Networks
• Quantized Consensus by the ADMM: Probabilistic versus Deterministic Quantizers
• Diffusion Adaptation over Multi-Agent Networks with Wireless Link Impairments
• Consensus and Products of Random Stochastic Matrices: Exact Rate for Convergence in Probability
• Asynchronous adaptive networks
• Asynchronous Adaptation and Learning over Networks --- Part I: Modeling and Stability Analysis
• Distributed Detection over Random Networks: Large Deviations Performance Analysis
• Minimizing Convergence Error in Multi-Agent Systems via Leader Selection: A Supermodular Optimization Approach
• Parameter Optimization of Multi-Agent Formations based on LQR Design
• Convergence Rate of Accelerated Average Consensus with Local Node Memory: Optimization and Analytic Solutions