Determining Optimal Rates for Communication for Omniscience

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

10 Scopus Citations
View graph of relations

Author(s)

  • Ni Ding
  • Chung Chan
  • Qiaoqiao Zhou
  • Rodney A. Kennedy
  • Parastoo Sadeghi

Detail(s)

Original languageEnglish
Pages (from-to)1919-1944
Journal / PublicationIEEE Transactions on Information Theory
Volume64
Issue number3
Online published9 Oct 2017
Publication statusPublished - Mar 2018
Externally publishedYes

Abstract

This paper considers the communication for omniscience problem: a set of users observe a discrete memoryless multiple source and want to recover the entire multiple source via noise-free broadcast communications. We study the problem of how to determine an optimal rate vector that attains omniscience with the minimum sum rate, the total number of communications. The results cover both asymptotic and non-asymptotic models where the transmission rates are real and integral, respectively. We propose a modified decomposition algorithm (MDA) and a sum-rate increment algorithm (SIA) for the asymptotic and non-asymptotic models, respectively, both of which determine the value of the minimum sum rate and a corresponding optimal rate vector in polynomial time. For the coordinate saturation capacity algorithm, a nesting algorithm in MDA and SIA, we propose to implement it by a fusion method and show by experimental results that this fusion method contributes to a reduction in computation complexity. Finally, we show that the separable convex minimization problem over the optimal rate vector set in the asymptotic model can be decomposed by the fundamental partition, the optimal partition of the user set that determines the minimum sum rate, so that the problem can be solved more efficiently.

Research Area(s)

  • Communication for omniscience, Dilworth truncation, mutual dependence, submodularity

Citation Format(s)

Determining Optimal Rates for Communication for Omniscience. / Ding, Ni; Chan, Chung; Zhou, Qiaoqiao; Kennedy, Rodney A.; Sadeghi, Parastoo.

In: IEEE Transactions on Information Theory, Vol. 64, No. 3, 03.2018, p. 1919-1944.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review