Search

We study common randomness generation problems where $n$ players aim to generate same sequences of random coin flips where some subsets of the players share an independent common coin which can be tossed multiple times, and there is a publicly seen blackboard through which the players communicate with each other. We provide a tight representation of the optimal communication rates via linear programming, and more importantly, propose explicit algorithms for the optimal distributed simulation for a wide class of hypergraphs. In particular, the optimal communication rate in complete hypergraphs is still achievable in sparser hypergraphs containing a path-connected cycle-free cluster of topologically connected components. Some key steps in analyzing the upper bounds rely on two different definitions of connectivity in hypergraphs, which may be of independent interest. [ABSTRACT FROM AUTHOR]

Fundamental relations between information and estimation have been established in the literature for the continuous time Gaussian and Poisson channels. In this paper, we demonstrate that such relations hold for a much larger family of continuous-time channels. We introduce the family of semi-martingale channels where the channel output is a semi-martingale stochastic process, and the channel input modulates the characteristics of the semi-martingale. For these channels, which includes as a special case the continuous time Gaussian and Poisson models, we establish new representations relating the mutual information between the channel input and output to an optimal causal filtering loss, thereby unifying and considerably extending results from the Gaussian and Poisson settings. Extensions to the setting of mismatched estimation are also presented where the relative entropy between the laws governing the output of the channel under two different input distributions is equal to the cumulative difference between the estimation loss incurred by using the mismatched and optimal causal filters, respectively. The main tool underlying these results is the Doob–Meyer decomposition of a class of sub-martingales. The results in this paper can be viewed as the continuous-time analogues of recent generalizations for relations between information and estimation for discrete-time Lévy channels. [ABSTRACT FROM AUTHOR]

Fundamental relations between information and estimation have been established in the literature for the discrete-time Gaussian and Poisson channels. In this paper, we demonstrate that such relations hold for a much larger class of observation models. We introduce the natural family of discrete-time Lévy channels where the distribution of the output conditioned on the input is infinitely divisible. For Lévy channels, we establish new representations relating the mutual information between the channel input and output to an optimal expected estimation loss, thereby unifying and considerably extending results from the Gaussian and Poisson settings. We demonstrate the richness of our results by working out two examples of Lévy channels, namely the gamma channel and the negative binomial channel, with corresponding relations between information and estimation. Extensions to the setting of mismatched estimation are also presented. [ABSTRACT FROM AUTHOR]

We consider a natural measure of relevance: the reduction in optimal prediction risk in the presence of side information. For any given loss function, this relevance measure captures the benefit of side information for performing inference on a random variable under this loss function. When such a measure satisfies a natural data processing property, and the random variable of interest has alphabet size greater than two, we show that it is uniquely characterized by the mutual information, and the corresponding loss function coincides with logarithmic loss. In doing so, our work provides a new characterization of mutual information, and justifies its use as a measure of relevance. When the alphabet is binary, we characterize the only admissible forms the measure of relevance can assume while obeying the specified data processing property. Our results naturally extend to measuring the causal influence between stochastic processes, where we unify different causality measures in the literature as instantiations of directed information. [ABSTRACT FROM PUBLISHER]

The problem of performing similarity queries on compressed data is considered. We focus on the quadratic similarity measure, and study the fundamental tradeoff between compression rate, sequence length, and reliability of queries performed on the compressed data. For a Gaussian source, we show that the queries can be answered reliably if and only if the compression rate exceeds a given threshold—the identification rate—which we explicitly characterize. Moreover, when compression is performed at a rate greater than the identification rate, responses to queries on the compressed data can be made exponentially reliable. We give a complete characterization of this exponent, which is analogous to the error and excess-distortion exponents in channel and source coding, respectively. For a general source, we prove that, as with classical compression, the Gaussian source requires the largest compression rate among sources with a given variance. Moreover, a robust scheme is described that attains this maximal rate for any source distribution. [ABSTRACT FROM AUTHOR]

We consider the classical two-encoder multiterminal source coding problem where distortion is measured under logarithmic loss. We provide a single-letter description of the achievable rate distortion region for all discrete memoryless sources with finite alphabets. By doing so, we also give the rate distortion region for the m-encoder CEO problem (also under logarithmic loss). Several applications and examples are given. [ABSTRACT FROM PUBLISHER]

We consider the problem of estimating a signal corrupted by independent interference with the assistance of a cost-constrained helper who knows the interference causally or noncausally. When the interference is known causally, we characterize the minimum distortion incurred in estimating the desired signal. In the noncausal case, we present a general achievable scheme for discrete memoryless systems and novel lower bounds on the distortion for the binary and Gaussian settings. Our Gaussian setting coincides with that of assisted interference suppression introduced by Grover and Sahai. Our lower bound for this setting is based on the relation recently established by Verdú between divergence and minimum mean squared error. We illustrate with a few examples that this lower bound can improve on those previously developed. Our bounds also allow us to characterize the optimal distortion in several interesting regimes. Moreover, we show that causal and noncausal estimation are not equivalent for this problem. Finally, we consider the case where the desired signal is also available at the helper. We develop new lower bounds for this setting that improve on those previously developed, and characterize the optimal distortion up to a constant multiplicative factor for some regimes of interest. [ABSTRACT FROM AUTHOR]

Many of the classical and recent relations between information and estimation in the presence of Gaussian noise can be viewed as identities between expectations of random quantities. These include the relationship between mutual information and minimum mean square error (I-MMSE) of Guo ; the relative entropy and mismatched estimation relationship of Verdú; the relationship between causal estimation and mutual information of Duncan, and its extension to the presence of feedback by Kadota ; the relationship between causal and non-casual estimation of Guo , and its mismatched version of Weissman. We dispense with the expectations and explore the nature of the pointwise relations between the respective random quantities. The pointwise relations that we find are as succinctly stated as—and give considerable insight into—the original expectation identities. As an illustration of our results, consider Duncan's 1970 discovery that the mutual information is equal to the causal MMSE in the additive white Gaussian noise channel, which can equivalently be expressed saying that the difference between the input–output information density and half the causal estimation error is a zero-mean random variable (regardless of the distribution of the channel input). We characterize this random variable explicitly, rather than merely its expectation. Classical estimation and information theoretic quantities emerge with new and surprising roles. For example, the variance of this random variable turns out to be given by the causal MMSE (which, in turn, is equal to twice the mutual information by Duncan's result). [ABSTRACT FROM PUBLISHER]

Let X be a nonnegative random variable and let the conditional distribution of a random variable Y, given X, be Poisson (\gamma\cdot X), for a parameter \gamma\geq 0. We identify a natural loss function such that: 1) the derivative of the mutual information between X and Y with respect to \gamma is equal to the minimum mean loss in estimating X based on Y, regardless of the distribution of X; 2) when X\sim P is estimated based on Y by a mismatched estimator that would have minimized the expected loss had X\sim Q, the integral over all values of \gamma of the excess mean loss is equal to the relative entropy between P and Q. For a continuous time setting where X is a nonnegative stochastic process and the conditional law of Y, given X, is that of a non-homogeneous Poisson process with intensity function \gamma\cdot X, under the same loss function: 1) the minimum mean loss in causal filtering when \gamma=\gamma0 is equal to the expected value of the minimum mean loss in noncausal filtering (smoothing) achieved with a channel whose parameter \gamma is uniformly distributed between 0 and \gamma0. Bridging the two quantities is the mutual information between X and Y; 2) this relationship between the mean losses in causal and noncausal filtering holds also in the case where the filters employed are mismatched, i.e., optimized assuming a law on X which is not the true one. Bridging the two quantities in this case is the sum of the mutual information and the relative entropy between the true and the mismatched distribution of Y. Thus, relative entropy quantifies the excess estimation loss due to mismatch in this setting. These results are parallel to those recently found for the Gaussian channel: the I-MMSE relationship of Guo , the relative entropy and mismatched estimation relationship of Verdú, and the relationship between causal and noncasual mismatched estimation of Weissman. [ABSTRACT FROM AUTHOR]

In this paper, we consider the cascade and triangular rate-distortion problems where the same side information is available at the source node and user 1, and the side information available at user 2 is a degraded version of the side information at the source node and user 1. We characterize the rate-distortion region for these problems. For the cascade setup, we show that, at user 1, decoding and rebinning the codeword sent by the source node for user 2 is optimum. We then extend our results to the two-way cascade and triangular setting, where the source node is interested in lossy reconstruction of the side information at user 2 via a rate limited link from user 2 to the source node. We characterize the rate-distortion regions for these settings. Complete explicit characterizations for all settings are given in the quadratic Gaussian case. We conclude with two further extensions: a triangular source coding problem with a helper, and an extension of our two-way cascade setting in the quadratic Gaussian case. [ABSTRACT FROM PUBLISHER]

We study source coding in the presence of side information, when the system can take actions that affect the availability, quality, or nature of the side information. We begin by extending the Wyner-Ziv problem of source coding with decoder side information to the case where the decoder is allowed to choose actions affecting the side information. We then consider the setting where actions are taken by the encoder, based on its observation of the source. Actions may have costs that are commensurate with the quality of the side information they yield, and an overall per-symbol cost constraint may be imposed. We characterize the achievable tradeoffs between rate, distortion, and cost in some of these problem settings. Among our findings is the fact that even in the absence of a cost constraint, greedily choosing the action associated with the “best” side information is, in general, suboptimal. A few examples are worked out. [ABSTRACT FROM AUTHOR]

We study the best exponential decay in the blocklength of the probability of error that can be achieved in the transmission of a single bit over the Gaussian channel with an active noisy Gaussian feedback link. We impose an expected block power constraint on the forward link and study both almost-sure and expected block power constraints on the feedback link. In both cases the best achievable error exponents are finite and grow approximately proportionally to the larger between the signal-to-noise ratios on the forward and feedback links. The error exponents under almost-sure block power constraints are typically strictly smaller than under expected constraints. Some of the results extend to communication at arbitrary rates below capacity and to general discrete memoryless channels. [ABSTRACT FROM PUBLISHER]