Determining Optimal Rates for Communication for Omniscience

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

    Research output: Contribution to journalArticlepeer-review

    10 Citations (Scopus)


    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.

    Original languageEnglish
    Pages (from-to)1919-1944
    Number of pages26
    JournalIEEE Transactions on Information Theory
    Issue number3
    Publication statusPublished - Mar 2018


    Dive into the research topics of 'Determining Optimal Rates for Communication for Omniscience'. Together they form a unique fingerprint.

    Cite this