Quantized Consensus by the ADMM: Probabilistic Versus Deterministic Quantizers

Shengyu Zhu, Biao Chen

Research output: Contribution to journalArticle

18 Scopus citations

Abstract

This paper develops efficient algorithms for distributed average consensus with quantized communication using the alternating direction method of multipliers (ADMM). We first study the effects of probabilistic and deterministic quantizations on a distributed ADMM algorithm. With probabilistic quantization, this algorithm yields linear convergence to the desired average in the mean sense with a bounded variance. When deterministic quantization is employed, the distributed ADMM converges to a consensus within 3 + [log1+δΩ] iterations where δ > 0 depends on the network topology and Ω is a polynomial fraction depending on the quantization resolution, the agents' data, and the network topology. A tight upper bound on the consensus error is also obtained, which depends only on the quantization resolution and the average degree of the graph. This bound is much preferred in large scale networks over existing algorithms whose consensus errors are increasing in the range of agents' data, the quantization resolution, and the number of agents. We finally propose our algorithm which combines both probabilistic and deterministic quantizations. Simulations show that the consensus error of our algorithm is typically less than one quantization resolution for all connected networks where agents' data can be of arbitrary magnitudes.

Original languageEnglish (US)
Article number7339710
Pages (from-to)1700-1713
Number of pages14
JournalIEEE Transactions on Signal Processing
Volume64
Issue number7
DOIs
StatePublished - Apr 1 2016

Keywords

  • Alternating direction method of multipliers
  • deterministic quantization
  • dither
  • linear convergence
  • probabilistic quantization
  • quantized consensus

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Signal Processing

Fingerprint Dive into the research topics of 'Quantized Consensus by the ADMM: Probabilistic Versus Deterministic Quantizers'. Together they form a unique fingerprint.

  • Cite this