Distributed average consensus with deterministic quantization

An ADMM approach

Shengyu Zhu, Biao Chen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

This paper develops efficient algorithms for distributed average consensus with quantized communication using the alternating direction method of multipliers (ADMM). When rounding quantization is employed, a distributed ADMM algorithm is shown to converge to a consensus within 3 + log1+δ ω iterations where δ > 0 depends on the network topology and O is a polynomial of 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. To minimize the consensus error, our final algorithm uses dithered quantization to obtain a good starting point and then adopts rounding quantization to reach a consensus. Simulations show that the consensus error of this algorithm is typically less than one quantization resolution for all connected networks with agents' data of arbitrary magnitudes.

Original languageEnglish (US)
Title of host publication2015 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages692-696
Number of pages5
ISBN (Print)9781479975914
DOIs
StatePublished - Feb 23 2016
EventIEEE Global Conference on Signal and Information Processing, GlobalSIP 2015 - Orlando, United States
Duration: Dec 13 2015Dec 16 2015

Other

OtherIEEE Global Conference on Signal and Information Processing, GlobalSIP 2015
CountryUnited States
CityOrlando
Period12/13/1512/16/15

Fingerprint

Topology
Polynomials
Communication

Keywords

  • alternating direction method of multipliers
  • deterministic quantization
  • Quantized consensus

ASJC Scopus subject areas

  • Information Systems
  • Signal Processing

Cite this

Zhu, S., & Chen, B. (2016). Distributed average consensus with deterministic quantization: An ADMM approach. In 2015 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2015 (pp. 692-696). [7418285] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/GlobalSIP.2015.7418285

Distributed average consensus with deterministic quantization : An ADMM approach. / Zhu, Shengyu; Chen, Biao.

2015 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2015. Institute of Electrical and Electronics Engineers Inc., 2016. p. 692-696 7418285.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Zhu, S & Chen, B 2016, Distributed average consensus with deterministic quantization: An ADMM approach. in 2015 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2015., 7418285, Institute of Electrical and Electronics Engineers Inc., pp. 692-696, IEEE Global Conference on Signal and Information Processing, GlobalSIP 2015, Orlando, United States, 12/13/15. https://doi.org/10.1109/GlobalSIP.2015.7418285
Zhu S, Chen B. Distributed average consensus with deterministic quantization: An ADMM approach. In 2015 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2015. Institute of Electrical and Electronics Engineers Inc. 2016. p. 692-696. 7418285 https://doi.org/10.1109/GlobalSIP.2015.7418285
Zhu, Shengyu ; Chen, Biao. / Distributed average consensus with deterministic quantization : An ADMM approach. 2015 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2015. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 692-696
@inproceedings{401fbc73052144769325e0d28afa65c0,
title = "Distributed average consensus with deterministic quantization: An ADMM approach",
abstract = "This paper develops efficient algorithms for distributed average consensus with quantized communication using the alternating direction method of multipliers (ADMM). When rounding quantization is employed, a distributed ADMM algorithm is shown to converge to a consensus within 3 + log1+δ ω iterations where δ > 0 depends on the network topology and O is a polynomial of 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. To minimize the consensus error, our final algorithm uses dithered quantization to obtain a good starting point and then adopts rounding quantization to reach a consensus. Simulations show that the consensus error of this algorithm is typically less than one quantization resolution for all connected networks with agents' data of arbitrary magnitudes.",
keywords = "alternating direction method of multipliers, deterministic quantization, Quantized consensus",
author = "Shengyu Zhu and Biao Chen",
year = "2016",
month = "2",
day = "23",
doi = "10.1109/GlobalSIP.2015.7418285",
language = "English (US)",
isbn = "9781479975914",
pages = "692--696",
booktitle = "2015 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2015",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - GEN

T1 - Distributed average consensus with deterministic quantization

T2 - An ADMM approach

AU - Zhu, Shengyu

AU - Chen, Biao

PY - 2016/2/23

Y1 - 2016/2/23

N2 - This paper develops efficient algorithms for distributed average consensus with quantized communication using the alternating direction method of multipliers (ADMM). When rounding quantization is employed, a distributed ADMM algorithm is shown to converge to a consensus within 3 + log1+δ ω iterations where δ > 0 depends on the network topology and O is a polynomial of 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. To minimize the consensus error, our final algorithm uses dithered quantization to obtain a good starting point and then adopts rounding quantization to reach a consensus. Simulations show that the consensus error of this algorithm is typically less than one quantization resolution for all connected networks with agents' data of arbitrary magnitudes.

AB - This paper develops efficient algorithms for distributed average consensus with quantized communication using the alternating direction method of multipliers (ADMM). When rounding quantization is employed, a distributed ADMM algorithm is shown to converge to a consensus within 3 + log1+δ ω iterations where δ > 0 depends on the network topology and O is a polynomial of 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. To minimize the consensus error, our final algorithm uses dithered quantization to obtain a good starting point and then adopts rounding quantization to reach a consensus. Simulations show that the consensus error of this algorithm is typically less than one quantization resolution for all connected networks with agents' data of arbitrary magnitudes.

KW - alternating direction method of multipliers

KW - deterministic quantization

KW - Quantized consensus

UR - http://www.scopus.com/inward/record.url?scp=84964758643&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84964758643&partnerID=8YFLogxK

U2 - 10.1109/GlobalSIP.2015.7418285

DO - 10.1109/GlobalSIP.2015.7418285

M3 - Conference contribution

SN - 9781479975914

SP - 692

EP - 696

BT - 2015 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2015

PB - Institute of Electrical and Electronics Engineers Inc.

ER -