Worst-case Asymmetric Distributed Source Coding

Abstract

We consider a worst-case asymmetric distributed source coding problem where an information sink communicates with $N$ correlated information sources to gather their data. A data-vector $\bar{x}=(x_1,...,x_N)\sim \mathcal{P}$ is derived from a discrete and finite joint probability distribution $\mathcal{P}=p(x_1,...,x_N)$ and component $x_i$ is revealed to the $i^{\text{th}}$ source, $1\le i\le N$. We consider an asymmetric communication scenario where only the sink is assumed to know distribution $\mathcal{P}$. We are interested in computing the minimum number of bits that the sources must send, in the worst-case, to enable the sink to losslessly learn any $\bar{x}$ revealed to the sources. We propose a novel information measure called information ambiguity to perform the worst-case information-theoretic analysis and prove its various properties. Then, we provide interactive communication protocols to solve the above problem in two different communication scenarios. We also investigate the role of block-coding in the worst-case analysis of distributed compression problem and prove that it offers almost no compression advantage compared to the scenarios where this problem is addressed, as in this paper, with only a single instance of data-vector.

22 pages, 10 figures