In many resource allocation problems, a centralized controller needs to award some resource to a user selected from a collection of distributed users with the goal of maximizing the utility the user would receive from the resource. This can be modeled as the controller computing an extremum of the distributed users’ utilities. The overhead rate necessary to enable the controller to reproduce the users’ local state can be prohibitively high. An approach to reduce this overhead is interactive communication wherein rate savings are achieved by tolerating an increase in delay. In this paper, we consider the design of a simple achievable scheme based on successive refinements of scalar quantization at each user. The optimal quantization policy is computed via a dynamic program and we demonstrate that tolerating a small increase in delay can yield significant rate savings. We then consider two simpler quantization policies to investigate the scaling properties of the rate-delay tradeoffs. Using a combination of these simpler policies, the performance of the optimal policy can be closely approximated with lower computational costs.
Kaspi determined the two party information theoretic limit for lossy compression via interactive communication @cite_30 . This line of research was continued by Ma and Ishwar, who showed (by an example) that the minimum rate for a given distortion constraint can be arbitrarily smaller than the non-interactive minimum rate obtaining the same distortion @cite_23 . In follow up work, Ma and Ishwar showed (by an example) that for the DFC problem, the minimum sum-rate for losslessly computing a function can be smaller than the non-interactive rate; even infinitely-many rounds of interaction may still improve the rate-region @cite_28 .
@cite_30 @cite_28 @cite_23
2056521209 2068143054 1999453492 1976853087
In 1985 Kaspi provided a single-letter characterization of the sum-rate-distortion function for a two-way lossy source coding problem in which two terminals send multiple messages back and forth with the goal of reproducing each other's sources. Yet, the question remained whether more messages can strictly improve the sum-rate-distortion function. Viewing the sum-rate as a functional of the distortions and the joint source distribution and leveraging its convex-geometric properties, we construct an example which shows that two messages can strictly improve the one-message (Wyner-Ziv) rate-distortion function. The example also shows that the ratio of the one-message rate to the two-message sum-rate can be arbitrarily large and simultaneously the ratio of the backward rate to the forward rate in the two-message sum-rate can be arbitrarily small. We consider a new problem in multiterminal source coding motivated by the following decentralized communication estimation task. A firm's Chief Executive Officer (CEO) is interested in the data sequence X(t) sub t=1 sup spl infin which cannot be observed directly, perhaps because it represents tactical decisions by a competing firm. The CEO deploys a team of L agents who observe independently corrupted versions of X(t) sub t=1 sup spl infin . Because X(t) is only one among many pressing matters to which the CEO must attend, the combined data rate at which the agents may communicate information about their observations to the CEO is limited to, say, R bits per second. If the agents were permitted to confer and pool their data, then in the limit as L spl rarr spl infin they usually would be able to smooth out their independent observation noises entirely. Then they could use their R bits per second to provide the CEO with a representation of X(t) with fidelity D(R), where D( spl middot ) is the distortion-rate function of X(t) . In particular, with such data pooling D can be made arbitrarily small if R exceeds the entropy rate H of X(t) . Suppose, however, that the agents are not permitted to convene, Agent i having to send data based solely on his own noisy observations Y sub i (t) . We show that then there does not exist a finite value of R for which even infinitely many agents can make D arbitrarily small. Furthermore, in this isolated-agents case we determine the asymptotic behavior of the minimal error frequency in the limit as L and then R tend to infinity. This paper shows new general nonasymptotic achievability and converse bounds and performs their dispersion analysis for the lossy compression problem in which the compressor observes the source through a noisy channel. While this problem is asymptotically equivalent to a noiseless lossy source coding problem with a modified distortion function, nonasymptotically there is a difference in how fast their minimum achievable coding rates approach the rate-distortion function, providing yet another example where at finite blocklengths one must put aside traditional asymptotic thinking. We study the generation of a secret key of maximum rate by a pair of terminals observing correlated sources and with the means to communicate over a noiseless public communication channel. Our main result establishes a structural equivalence between the generation of a maximum rate secret key and the generation of a common randomness that renders the observations of the two terminals conditionally independent. The minimum rate of such common randomness, termed interactive common information, is related to Wyner's notion of common information, and serves to characterize the minimum rate of interactive public communication required to generate an optimum rate secret key. This characterization yields a single-letter expression for the aforementioned communication rate when the number of rounds of interaction are bounded. An application of our results shows that interaction does not reduce this rate for binary symmetric sources. Further, we provide an example for which interaction does reduce the minimum rate of communication. Also, certain invariance properties of common information quantities are established that may be of independent interest.