Search

We introduce a fundamental lemma called the Poisson matching lemma, and apply it to prove one-shot achievability results for various settings, namely channels with state information at the encoder, lossy source coding with side information at the decoder, joint source-channel coding, broadcast channels, distributed lossy source coding, multiple access channels and channel resolvability. Our one-shot bounds improve upon the best known one-shot bounds in most of the aforementioned settings (except multiple access channels and channel resolvability, where we recover bounds comparable to the best known bounds), with shorter proofs in some settings even when compared to the conventional asymptotic approach using typicality. The Poisson matching lemma replaces both the packing and covering lemmas, greatly simplifying the error analysis. This paper extends the work of Li and El Gamal on Poisson functional representation, which mainly considered variable-length source coding settings, whereas this paper studies fixed-length settings, and is not limited to source coding, showing that the Poisson functional representation is a viable alternative to typicality for most problems in network information theory. [ABSTRACT FROM AUTHOR]

One of the important unsolved problems in information theory is the conjecture that the undirected multiple-unicast network information capacity is the same as the routing capacity. This conjecture is verified only for a handful of networks and network classes. Moreover, only two explicit upper bounds on information capacity are known for general undirected networks: the sparsest cut bound and the linear programming bound. In this paper, we present an information-theoretic upper bound, called the partition bound, on the capacity of general undirected multiple-unicast networks. We show that a decision version problem of computing the bound is NP-complete. We present two classes of undirected multiple-unicast networks such that the partition bound is achievable by routing. Thus, the conjecture is proved for these classes of networks. Recently, the conjecture was proved for a new class of networks defined by properties relating to cut-set and source-sink paths. We show the existence of a network outside of this new class of networks such that the partition bound is achievable by routing. [ABSTRACT FROM AUTHOR]

This paper deals with two typical random number generation problems in information theory. One is the source resolvability problem (resolvability problem for short) and the other is the intrinsic randomness problem. In the literature, optimum achievable rates in these two problems with respect to the variational distance as well as the Kullback-Leibler (KL) divergence have already been analyzed. On the other hand, in this study we consider these two problems with respect to $f$ -divergences. The $f$ -divergence is a general non-negative measure between two probabilistic distributions on the basis of a convex function $f$. The class of $f$ -divergences includes several important measures such as the variational distance, the KL divergence, the Hellinger distance and so on. Hence, it is meaningful to consider the random number generation problems with respect to $f$ -divergences. In this paper, we impose some conditions on the function $f$ so as to simplify the analysis, that is, we consider a subclass of $f$ -divergences. Then, we first derive general formulas of the first-order optimum achievable rates with respect to $f$ -divergences. Next, we particularize our general formulas to several specified functions $f$. As a result, we reveal that it is easy to derive optimum achievable rates for several important measures from our general formulas. The second-order optimum achievable rates and optimistic optimum achievable rates have also been investigated. [ABSTRACT FROM AUTHOR]

This paper presents explicit solutions for two related non-convex information extremization problems due to Gray and Wyner in the Gaussian case. The first problem is the Gray-Wyner network subject to a sum-rate constraint on the two private links. Here, our argument establishes the optimality of Gaussian codebooks and hence, a closed-form formula for the optimal rate region. The second problem is Wyner’s common information and a generalization thereof, where conditional independence is generalized to a limit on the conditional mutual information. We present full explicit solutions for the scalar as well as the vector case. [ABSTRACT FROM AUTHOR]

Information-theoretic quantities like entropy and mutual information have found numerous uses in machine learning. It is well known that there is a strong connection between these entropic quantities and submodularity since entropy over a set of random variables is submodular. In this paper, we study combinatorial information measures that generalize independence, (conditional) entropy, (conditional) mutual information, and total correlation defined over sets of (not necessarily random) variables. These measures strictly generalize the corresponding entropic measures since they are all parameterized via submodular functions that themselves strictly generalize entropy. Critically, we show that, unlike entropic mutual information in general, the submodular mutual information is actually submodular in one argument, holding the other fixed, for a large class of submodular functions whose third-order partial derivatives satisfy a non-negativity property. This turns out to include a number of practically useful cases such as the facility location and set-cover functions. We study specific instantiations of the submodular information measures on these, as well as the probabilistic coverage, graph-cut, log-determinants, and saturated coverage functions and see that they all have mathematically intuitive and practically useful expressions. Finally, we also study generalized independence between subsets of datapoints (random variables in the entropic case), and connect the independence characterizations to independence in log-submodular distributions. Regarding applications, we connect the maximization of submodular (conditional) mutual information to problems such as mutual-information-based, query-based, and privacy preserving summarization—and we connect optimizing the multi-set submodular mutual information to clustering and robust partitioning. We perform real world as well as synthetic experiments on various data summarization tasks. [ABSTRACT FROM AUTHOR]

The $r$ -parallel set of a set $A \subseteq {\mathbb {R}} ^{d}$ is the set of all points whose distance from $A$ is less than $r$. In this paper, we show that the surface area of an $r$ -parallel set in ${\mathbb {R}}^{d}$ with volume at most $V$ is upper-bounded by $e^{\Theta (d)}V/r$ , whereas its Gaussian surface area is upper-bounded by $\max (e^{\Theta (d)}, e^{\Theta (d)}/r)$. We also derive a reverse form of the Brunn-Minkowski inequality for $r$ -parallel sets, and as an aside a reverse entropy power inequality for Gaussian-smoothed random variables. We apply our results to two problems in theoretical machine learning: (1) bounding the computational complexity of learning $r$ -parallel sets under a Gaussian distribution; and (2) bounding the sample complexity of estimating robust risk, which is a notion of risk in the adversarial machine learning literature that is analogous to the Bayes risk in hypothesis testing. [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]

We consider the problem of multiple descriptions (MDs) source coding and propose new coding strategies involving both unstructured and structured coding layers. Previously, the most general achievable rate-distortion (RD) region for the $l$ -descriptions problem was the combinatorial message sharing with binning (CMSB) region. The CMSB scheme utilizes unstructured quantizers and unstructured binning. In the first part of the paper, we show that this strategy can be improved upon using more general unstructured quantizers and a more general unstructured binning method. In the second part, structured coding strategies are considered. First, structured coding strategies are developed by considering the specific MD examples involving three or more descriptions. We show that the application of structured quantizers results in strict RD improvements when there are more than two descriptions. Furthermore, we show that a structured binning also yields improvements. These improvements are in addition to the ones derived in the first part of the paper. This suggests that structured coding is essential when coding over more than two descriptions. Using the ideas developed through these examples, we provide a new unified coding strategy by considering several structured coding layers. Finally, we characterize its performance in the form of an inner bound to the optimal RD region using computable single-letter information quantities. The new RD region strictly contains all of the previous known achievable regions. [ABSTRACT FROM PUBLISHER]

Algebraic network information theory is an emerging facet of network information theory, studying the achievable rates of random code ensembles that have algebraic structure, such as random linear codes. A distinguishing feature is that linear combinations of codewords can sometimes be decoded more efficiently than codewords themselves. The present work further develops this framework by studying the simultaneous decoding of multiple messages. Specifically, consider a receiver in a multi-user network that wishes to decode several messages. Simultaneous joint typicality decoding is one of the most powerful techniques for determining the fundamental limits at which reliable decoding is possible. This technique has historically been used in conjunction with random i.i.d. codebooks to establish achievable rate regions for networks. Recently, it has been shown that, in certain scenarios, nested linear codebooks in conjunction with “single-user” or sequential decoding can yield better achievable rates. For instance, the compute–forward problem examines the scenario of recovering $L \le K$ linear combinations of transmitted codewords over a $K$ -user multiple-access channel (MAC), and it is well established that linear codebooks can yield higher rates. This paper develops bounds for simultaneous joint typicality decoding used in conjunction with nested linear codebooks, and applies them to obtain a larger achievable region for compute–forward over a $K$ -user discrete memoryless MAC. The key technical challenge is that competing codeword tuples that are linearly dependent on the true codeword tuple introduce statistical dependencies, which requires careful partitioning of the associated error events. [ABSTRACT FROM AUTHOR]

Proving or disproving an information inequality is a crucial step in establishing the converse results in coding theorems. However, an information inequality involving more than a few random variables is difficult to be proved or disproved manually. In 1997, Yeung developed a framework that uses linear programming for verifying linear information inequalities. Under the framework, this paper considers a few other problems that can be solved by using Lagrange duality and convex approximation. We will demonstrate how linear programming can be used to find an analytic proof of an information inequality or an analytic counterexample to disprove it if the inequality is not true in general. The way to automatically find a shortest proof or a smallest counterexample is explored. When a given information inequality cannot be proved, the sufficient conditions for a counterexample to disprove the information inequality are found by linear programming. Lastly, we propose a scalable algorithmic framework based on the alternating direction method of multipliers to accelerate solving a multitude of user-specific problems whose overall computational cost can be amortized with the number of users, and present its publicly-available software implementation for large-scale problems. [ABSTRACT FROM AUTHOR]

Classical multiuser information theory studies the fundamental limits of models with a fixed (often small) number of users as the coding blocklength goes to infinity. This paper proposes a new paradigm, referred to as many-user information theory, where the number of users is allowed to grow with the blocklength. This paradigm is motivated by emerging systems with a massive number of users in an area, such as the Internet of Things. The focus of this paper is the many-access channel model, which consists of a single receiver and many transmitters, whose number increases unboundedly with the blocklength. Moreover, an unknown subset of transmitters may transmit in a given block and need to be identified as well as decoded by the receiver. A new notion of capacity is introduced and characterized for the Gaussian many-access channel with random user activities. The capacity can be achieved by first detecting the set of active users and then decoding their messages. The minimum cost of identifying the active users is also quantified. [ABSTRACT FROM AUTHOR]

This paper investigates the relation between three different notions of privacy: identifiability, differential privacy, and mutual-information privacy. Under a unified privacy-distortion framework, where the distortion is defined to be the expected Hamming distance between the input and output databases, we establish some fundamental connections between these three privacy notions. Given a maximum allowable distortion D , we define the privacy-distortion functions \epsilon _{\mathrm{ i}}^{*}(D) , \epsilon _{\mathrm{ d}}^{*}(D) , and \epsilon \mathrm{ m}^{*}(D) to be the smallest (most private/best) identifiability level, differential privacy level, and mutual information between the input and the output, respectively. We characterize \epsilon \mathrm{ i}^{*}(D) and \epsilon \mathrm{ d}^{*}(D) , and prove that \epsilon \mathrm{ i}^{*}(D)-\epsilon X\le \epsilon \mathrm{ d}^{*}(D)\le \epsilon \mathrm{ i}^{*}(D) for D within certain range, where \epsilon _{X} is a constant determined by the prior distribution of the original database X , and diminishes to zero when X is uniformly distributed. Furthermore, we show that \epsilon _{\mathrm{ i}}^{*}(D) and \epsilon _{\mathrm{ m}}^{*}(D)$ can be achieved by the same mechanism for D$ within certain range, i.e., there is a mechanism that simultaneously minimizes the identifiability level and achieves the best mutual-information privacy. Based on these two connections, we prove that this mutual-information optimal mechanism satisfies \epsilon $ -differential privacy with . The results in this paper reveal some consistency between two worst case notions of privacy, namely, identifiability and differential privacy, and an average notion of privacy, mutual-information privacy. [ABSTRACT FROM PUBLISHER]

Calculating the Shannon entropy for symbolic sequences has been widely considered in many fields. For descriptive statistical problems such as estimating the N-gram entropy of English language text, a common approach is to use as much data as possible to obtain progressively more accurate estimates. However, in some instances, only short sequences may be available. This gives rise to the question of how many samples are needed to compute entropy. In this paper, we examine this problem and propose a method for estimating the number of samples required to compute Shannon entropy for a set of ranked symbolic “natural” events. The result is developed using a modified Zipf-Mandelbrot law and the Dvoretzky–Kiefer–Wolfowitz inequality, and we propose an approximation which yields an estimate for the minimum number of samples required to obtain an estimate of entropy with a given confidence level and degree of accuracy. [ABSTRACT FROM AUTHOR]

Mathematical tools that are widely employed for the distribution-free analysis of the finite-sample performance of empirical estimators—like Efron-Stein’s inequality, or Azuma’s martingale inequality and derivatives—rely on the provision of tight bounds for the Lipschitz constants of the estimators. Lipschitz constants can be easily derived for simple functionals of the empirical measures, such as the Shannon or the Tsallis entropy. However, obtaining tight bounds for more generalized entropy functionals which cannot be decomposed into sums of identical terms is much more involved. The goal in this paper is the derivation of (empirical) Lipschitz constants for the maximum likelihood estimator of the family of Renyi entropies of order $\lambda >0$ , $\lambda \neq 1$. Analytic solutions for the optimal constants are obtained for the most important special cases; namely, for $0 < \lambda < 1$ , for $1 < \lambda < 2$ as well as for $\lambda =2$ (collision entropy) and $\lambda = 3$. For the remaining cases where no analytic solution is obtained (i.e., $\lambda > 2$ , $\lambda \neq 3$), an efficient way to compute the optimal constants is derived by reducing the complexity of the underlying optimization problem from exponential ${\varOmega}(n^{\| \mathcal {A} \|-1})$ to linear $\mathcal {O}(n)$ , where $n$ the number of available samples and $\| \mathcal {A} \| \geq 2$ the number of symbols of the source (with the assumption $\| \mathcal {A} \|$ does not grow with $n$). The optimal constants are subsequently used for the distribution-free performance analysis of the maximum likelihood estimator of Renyi entropy; this includes variance and concentration bounds, both under the assumption of independence as well as under strong mixing conditions. [ABSTRACT FROM AUTHOR]

Suppose $M$ records are replicated in $N$ servers (each storing all $M$ records), a user wants to privately retrieve one record by accessing the servers such that the identity of the retrieved record is secret against any up to $T$ servers. A scheme designed for this purpose is called a $T$ -private information retrieval (PIR) scheme. In practice, capacity-achieving and small sub-packetization are both desired for PIR schemes, because the former implies the highest download rate and the latter means simple realization. Meanwhile, sub-packetization is the key technique for achieving capacity. In this paper, we characterize the optimal sub-packetization for linear capacity-achieving $T$ -PIR schemes. First, a lower bound on the sub-packetization $L$ for linear capacity-achieving $T$ -PIR schemes is proved, i.e., $L\geq dn^{M-1}$ , where $d={\mathrm{ gcd}}(N,T)$ and $n=N/d$. Then, for general values of $M$ and $N>T\geq 1$ , a linear capacity-achieving $T$ -PIR scheme with sub-packetization $dn^{M-1}$ is designed. Comparing with the first capacity-achieving $T$ -PIR scheme given by Sun and Jafar in 2016, our scheme reduces the sub-packetization from $N^{M}$ to the optimal and further reduces the field size by a factor of $Nd^{M-2}$. [ABSTRACT FROM AUTHOR]

This paper shows that for any random variables $X$ and $Y$ , it is possible to represent $Y$ as a function of $(X,Z)$ such that $Z$ is independent of $X$ and $I(X;Z|Y)\le \log (I(X;Y)+1)+4$ bits. We use this strong functional representation lemma (SFRL) to establish a bound on the rate needed for one-shot exact channel simulation for general (discrete or continuous) random variables, strengthening the results by Harsha et al. and Braverman and Garg, and to establish new and simple achievability results for one-shot variable-length lossy source coding, multiple description coding, and Gray–Wyner system. We also show that the SFRL can be used to reduce the channel with state noncausally known at the encoder to a point-to-point channel, which provides a simple achievability proof of the Gelfand–Pinsker theorem. [ABSTRACT FROM AUTHOR]

Network systems often rely on distributed algorithms to achieve a global computation goal with iterative local information exchanges between neighbor nodes. To preserve data privacy, a node may add a random noise to its original data for information exchange at each iteration. Nevertheless, an eavesdropping node can estimate other’s original data based on the information it received. The estimation accuracy and data privacy can be measured in terms of $(\epsilon, \delta)$ -data-privacy, defined as the probability of $\epsilon $ -accurate estimate (the difference of an estimation and the original data is within $\epsilon $ ) is no larger than $\delta $ (the disclosure probability). How to optimize the estimation and analyze data privacy is a critical and open issue. In this paper, a theoretical framework is developed to investigate how to optimize the estimation of neighbor’s original data using the local information received, named optimal distributed estimation. Then, we study the disclosure probability under the optimal estimation for data privacy analysis. We further apply the developed framework to analyze the data privacy of the privacy-preserving average consensus algorithm and identify the optimal noises for the algorithm. [ABSTRACT FROM AUTHOR]

Estimating mutual information from independent identically distributed samples drawn from an unknown joint density function is a basic statistical problem of broad interest with multitudinous applications. The most popular estimator is the one proposed by Kraskov, Stögbauer, and Grassberger (KSG) in 2004 and is nonparametric and based on the distances of each sample to its $k^{\mathrm{ th}}$ nearest neighboring sample, where $k$ is a fixed small integer. Despite of its widespread use (part of scientific software packages), theoretical properties of this estimator have been largely unexplored. In this paper, we demonstrate that the estimator is consistent and also identify an upper bound on the rate of convergence of the $\ell _{2}$ error as a function of a number of samples. We argue that the performance benefits of the KSG estimator stems from a curious “correlation boosting” effect and build on this intuition to modify the KSG estimator in novel ways to construct a superior estimator. As a by-product of our investigations, we obtain nearly tight rates of convergence of the $\ell _{2}$ error of the well-known fixed $k$ -nearest neighbor estimator of differential entropy by Kozachenko and Leonenko. [ABSTRACT FROM AUTHOR]

In this paper, we study a security problem on a simple wiretap network, consisting of a source node S, a destination node D, and an intermediate node R. The intermediate node connects the source and the destination nodes via a set of noiseless parallel channels, with sizes n1 and n2 , respectively. A message $M$ is to be sent from S to D. The information in the network may be eavesdropped by a set of wiretappers. The wiretappers cannot communicate with one another. Each wiretapper can access a subset of channels, called a wiretap set. All the chosen wiretap sets form a wiretap pattern. A random key $K$ is generated at S, and a coding scheme on $(M, K)$ is employed to protect $M$ . We define two decoding classes at D. In Class-I, only $M$ is required to be recovered, and in Class-II, both $M$ and $K$ are required to be recovered. The objective is to minimize $H(K)/H(M)$ for a given wiretap pattern under the perfect secrecy constraint. The first question we address is whether routing is optimal on this simple network. By enumerating all the wiretap patterns on the Class-I/II (3, 3) networks and harnessing the power of Shannon-type inequalities, we find that gaps exist between the bounds implied by routing and the bounds implied by Shannon-type inequalities for a small fraction (<2%) of all the wiretap patterns. The second question we investigate is the following: What is $\min H(K)/H(M)$ for the remaining wiretap patterns where gaps exist? We study some simple wiretap patterns and find that their Shannon bounds (i.e., the lower bound induced by Shannon-type inequalities) can be achieved by linear codes, which means routing is not sufficient even for the (3, 3) network. For some complicated wiretap patterns, we study the structures of linear coding schemes under the assumption that they can achieve the corresponding Shannon bounds. This paper indicates that the determination of the entropic region of six linear vector spaces cannot be sidestepped. Some subtle issues on the network models are discussed, and interesting observations are stated. [ABSTRACT FROM AUTHOR]

The linear model, in which a set of observations is assumed to be given by a linear combination of columns of a matrix (often termed a dictionary), has long been the mainstay of the statistics and signal processing literature. One particular challenge for inference under linear models is understanding the conditions on the dictionary under which reliable inference is possible. This challenge has attracted renewed attention in recent years, since many modern inference problems (e.g., high-dimensional statistics and compressed sensing) deal with the underdetermined setting, in which the number of observations is much smaller than the number of columns in the dictionary. This paper makes several contributions for this setting when the set of observations is given by a linear combination of a small number of groups of columns of the dictionary, termed the block-sparse case. First, it specifies conditions on the dictionary under which most block submatrices of the dictionary (often termed block subdictionaries) are well conditioned. This result is fundamentally different from prior work on block-sparse inference because: 1) it provides conditions that can be explicitly computed in polynomial time; 2) the given conditions translate into near-optimal scaling of the number of columns of the block subdictionaries as a function of the number of observations for a large class of dictionaries; and 3) it suggests that the spectral norm, rather than the column/block coherences of the dictionary, fundamentally limits the scaling of dimensions of the well-conditioned block subdictionaries. Second, in order to help understand the significance of this result in the context of block-sparse inference, this paper investigates the problems of block-sparse recovery and block-sparse regression in underdetermined settings. In both of these problems, this paper utilizes its result concerning conditioning of block subdictionaries and establishes that near-optimal block-sparse recovery and block-sparse regression is possible for a large class of dictionaries as long as the dictionary satisfies easily computable conditions and the coefficients describing the linear combination of groups of columns can be modeled through a mild statistical prior. Third, the paper reports extensive numerical experiments that highlight the effects of different measures of the dictionary in block-sparse inference problems. [ABSTRACT FROM PUBLISHER]

In multiuser information theory, it is often assumed that every node in the network possesses all codebooks used in the network. This assumption may be impractical in distributed ad hoc, cognitive, or heterogeneous networks. This paper considers the two-user interference channel with one oblivious receiver (IC-OR), i.e., one receiver lacks knowledge of the interfering cookbook, whereas the other receiver knows both codebooks. This paper asks whether, and if so how much, the channel capacity of the IC-OR is reduced compared with that of the classical IC where both receivers know all codebooks. A novel outer bound is derived and shown to be achievable to within a gap for the class of injective semideterministic IC-ORs; the gap is shown to be zero for injective fully deterministic IC-ORs. An exact capacity result is shown for the general memoryless IC-OR when the nonoblivious receiver experiences very strong interference. For the linear deterministic IC-OR that models the Gaussian noise channel at high SNR, nonindependent identically distributed. Bernoulli(1/2) input bits are shown to achieve points not achievable by i.i.d. Bernoulli(1/2) input bits used in the same achievability scheme. For the real-valued Gaussian IC-OR, the gap is shown to be at most 1/2 bit per channel use, even though the set of optimal input distributions for the derived outer bound could not be determined. Toward understanding the Gaussian IC-OR, an achievability strategy is evaluated in which the input alphabets at the nonoblivious transmitter are a mixture of discrete and Gaussian random variables, where the cardinality of the discrete part is appropriately chosen as a function of the channel parameters. Surprisingly, as the oblivious receiver intuitively should not be able to jointly decode the intended and interfering messages (whose codebook is unavailable), it is shown that with this choice of input, the capacity region of the symmetric Gaussian IC-OR is to within 1/2\log \left (12\pi \mathrm e \right )\approx 3.34 bits (per channel use per user) of an outer bound for the classical Gaussian IC with full codebook knowledge at both receivers. [ABSTRACT FROM PUBLISHER]

This paper introduces a new and ubiquitous framework for establishing achievability results in network information theory problems. The framework uses random binning arguments and is based on a duality between channel and source coding problems. Furthermore, the framework uses pmf approximation arguments instead of counting and typicality. This allows for proving coordination and strong secrecy problems, where certain statistical conditions on the distribution of random variables need to be satisfied. These statistical conditions include independence between messages and eavesdropper’s observations in secrecy problems and closeness to a certain distribution (usually, i.i.d. distribution) in coordination problems. One important feature of the framework is to enable one to add an eavesdropper and obtain a result on the secrecy rates for free. We make a case for generality of the framework by studying examples in a variety of settings including channel coding, lossy source coding, joint source-channel coding, coordination, strong secrecy, feedback, and relaying. In particular, by investigating the framework for the lossy source coding problem over broadcast channel, it is shown that the new framework provides a simple alternative scheme to the hybrid coding scheme. In addition, new results on secrecy rate region (under strong secrecy criterion) of wiretap broadcast channel and wiretap relay channel are derived. In a set of accompanied papers, we have shown the usefulness of the framework to establish achievability results for coordination problems, including interactive channel simulation, coordination via relay and channel simulation via another channel. [ABSTRACT FROM PUBLISHER]

The entropy of a random variable is well-known to equal the exponential growth rate of the volumes of its typical sets. In this paper, we show that for any log-concave random variable X , the sequence of the \lfloor n\theta \rfloor ^{\text {th}} intrinsic volumes of the typical sets of X in dimensions n \geq 1 grows exponentially with a well-defined rate. We denote this rate by h_{X}(\theta ) , and call it the \theta ^{\text {th}} intrinsic entropy of X . We show that h_{X}(\theta ) is a continuous function of \theta $ over the range [0, 1], thereby providing a smooth interpolation between the values 0 and $h(X)$ at the endpoints 0 and 1, respectively. [ABSTRACT FROM PUBLISHER]

Over the past few years, a family of interesting new inequalities for the entropies of sums and differences of random variables has been developed by Ruzsa, Tao, and others, motivated by analogous results in additive combinatorics. This paper extends these earlier results to the case of random variables taking values in \mathbb R^n or, more generally, in arbitrary locally compact and Polish abelian groups. We isolate and study a key quantity, the Ruzsa divergence between two probability distributions, and we show that its properties can be used to extend the earlier inequalities to the present general setting. The new results established include several variations on the theme that the entropies of the sum and the difference of two independent random variables severely constrain each other. Although the setting is quite general, the results are already of interest (and new) for random vectors in \mathbb R^n . In that special case, we discuss quantitative bounds for the stability of the equality conditions in the entropy power inequality, a reverse entropy power inequality for log-concave random vectors, an information-theoretic analog of the Rogers–Shephard inequality for convex bodies, and consequences of some of our results to determinant inequalities for sums of positive-definite matrices. Moreover, by considering various multiplicative subgroups of the complex plane, one obtains new inequalities for the differential entropies of products and ratios of nonzero, complex-valued random variables. [ABSTRACT FROM PUBLISHER]

Impulsive noise features in many modern communication systems—ranging from wireless to molecular—and is often modeled by the $\alpha $ -stable distribution. At present, the capacity of $\alpha $ -stable noise channels is not well understood, with the exception of Cauchy noise ( $\alpha = 1$ ) with a logarithmic constraint and Gaussian noise ( $\alpha = 2$ ) with a power constraint. In this paper, we consider additive symmetric $\alpha $ -stable noise channels with $\alpha \in (1,2]$ . We derive bounds for the capacity with an absolute moment constraint. We then compare our bounds with a numerical approximation via the Blahut–Arimoto algorithm, which provides insight into the effect of noise parameters on the bounds. In particular, we find that our lower bound is in good agreement with the numerical approximation for $\alpha $ near 2. [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]

Characterising the capacity region for a network can be extremely difficult. Even with independent sources, determining the capacity region can be as hard as the open problem of characterising all information inequalities. The majority of computable outer bounds in the literature are relaxations of the linear programming bound, which involves entropy functions of random variables related to the sources and link messages. When sources are not independent, the problem is even more complicated. Extension of linear programming bounds to networks with correlated sources is largely open. Source dependence is usually specified through a joint probability distribution, and one of the main challenges in extending linear program bounds is the difficulty (or impossibility) of characterising arbitrary dependences via entropy functions. This paper tackles the problem by answering the question of how well entropy functions can characterise correlation among sources. We show that by using carefully chosen auxiliary random variables, the characterisation can be fairly “accurate”. Using such auxiliary random variables, we also give implicit and explicit outer bounds on the capacity of networks with correlated sources. The characterisation of correlation or joint distribution via Shannon entropy functions is also applicable to other information measures, such as Rényi entropy and Tsallis entropy. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of simulating a discrete memoryless channel (DMC) from another DMC under an average-case and an exact model. We present several achievability and infeasibility results, with tight characterizations in special cases. In particular, for the exact model, we fully characterize when a binary symmetric channel can be simulated from a binary erasure channel when there is no shared randomness. We also provide infeasibility and achievability results for the simulation of a binary channel from another binary channel in the case of no shared randomness. To do this, we use the properties of Rényi capacity of a given order. We also introduce a notion of “channel diameter” which is shown to be additive and satisfy a data processing inequality. [ABSTRACT FROM PUBLISHER]

This paper gives improved Rényi entropy power inequalities (R-EPIs). Consider a sum Sn = \sum k=1^{n} Xk of n independent continuous random vectors taking values on {\mathbb {R}}^{d} , and let \alpha \in [1, \infty ] . An R-EPI provides a lower bound on the order- \alpha Rényi entropy power of S_{n} that, up to a multiplicative constant (which may depend in general on n, \alpha , d$ ), is equal to the sum of the order- \alpha $ Rényi entropy powers of the n$ random vectors . For $\alpha =1$ , the R-EPI coincides with the well-known entropy power inequality by Shannon. The first improved R-EPI is obtained by tightening the recent R-EPI by Bobkov and Chistyakov, which relies on the sharpened Young’s inequality. A further improvement of the R-EPI also relies on convex optimization and results on rank-one modification of a real-valued diagonal matrix. [ABSTRACT FROM PUBLISHER]

Unveiling a fundamental link between information theory and estimation theory, the I-MMSE relationship by Guo et al., together with its numerous extensions, has great theoretical significance and various practical applications. On the other hand, its influences to date have been restricted to channels without feedback or memory, due to the absence of its extensions to such channels. In this paper, we propose the extensions of the I-MMSE relationship to discrete-time and continuous-time Gaussian channels with feedback and/or memory. Our approach is based on a very simple observation, which can be applied to other scenarios, such as a simple and direct proof of the classical de Bruijn’s identity. [ABSTRACT FROM AUTHOR]

This paper establishes that the strong converse holds for some classes of discrete memoryless multimessage multicast networks (DM-MMNs) whose corresponding cut-set bounds are tight, i.e., coincide with the corresponding sets of achievable rate tuples. Our strong converse result implies that for any DM-MMN of these classes, the average error probabilities of any sequence of codes operated at a rate tuple belonging to the exterior of the cut-set bound must tend to one (and are not simply bounded away from zero) as the block length grows. Examples in the classes of DM-MMNs include wireless erasure networks, DM-MMNs consisting of independent discrete memoryless channels (DMCs) as well as single-destination DM-MMNs consisting of independent DMCs with destination feedback. Our elementary proof technique leverages properties of the Rényi divergence. [ABSTRACT FROM PUBLISHER]

In recent years, solutions to various hypothesis testing problems in the asymptotic setting have been proposed using the results from large deviation theory. Such tests are optimal in terms of appropriately defined error exponents. For the practitioner, however, error probabilities in the finite sample size setting are more important. In this paper, we show how results on weak convergence of the test statistic can be used to obtain better approximations for the error probabilities in the finite sample size setting. While this technique is popular among statisticians for common tests, we demonstrate its applicability for several recently proposed asymptotically optimal tests, including tests for robust goodness of fit, homogeneity tests, outlier hypothesis testing, and graphical model estimation. [ABSTRACT FROM PUBLISHER]

Recently, $\varepsilon $ -almost dual universal2 hash functions have been proposed as a new and wider class of hash functions. Using this class of hash functions, several efficient hash functions were proposed. This paper evaluates the security performance when we apply this kind of hash functions. We evaluate the security in several kinds of setting based on the L_{1} distinguishability criterion and the modified mutual information criterion. The obtained evaluation is based on smoothing of Rényi entropy of order 2 and/or min entropy. We clarify the difference between these two methods. [ABSTRACT FROM AUTHOR]

In this paper, we investigate problems of communication over physically degraded, state-dependent broadcast channels (BCs) with cooperating decoders. Two different setups are considered, and their capacity regions are characterized. First, we study a setting in which one decoder can use a finite capacity link to send the other decoder information regarding the messages or the channel states. In this scenario, we analyze two cases: one, where noncausal state information, is available to the encoder and the strong decoder, and the other, where state information, is available only to the encoder in a causal manner. Second, we examine a setting in which the cooperation between the decoders is limited to taking place before the outputs of the channel are given. In this case, one decoder, which is informed of the state sequence noncausally, can cooperate only to send the other decoder rate-limited information about the state sequence. The proofs of the capacity regions introduce a new idea of coding for channels with cooperation between different users, where we exploit the link between the decoders for multiple binnings. Finally, we discuss the optimality of using rate-splitting techniques when coding for cooperative BCs. In particular, we show that rate splitting is not necessarily optimal when coding for cooperative BCs by solving an example in which our method of coding outperforms rate splitting. [ABSTRACT FROM AUTHOR]

Hilberg’s conjecture about natural language states that the mutual information between two adjacent long blocks of text grows like a power of the block length. The exponent in this statement can be upper bounded using the pointwise mutual information estimate computed for a carefully chosen code. The bound is the better, the lower the compression rate is, but there is a requirement that the code be universal. So as to improve a received upper bound for Hilberg’s exponent, in this paper, we introduce two novel universal codes, called the plain switch distribution and the preadapted switch distribution. Generally speaking, switch distributions are certain mixtures of adaptive Markov chains of varying orders with some additional communication to avoid the so-called catch-up phenomenon. The advantage of these distributions is that they both achieve a low compression rate and are guaranteed to be universal. Using the switch distributions, we obtain that a sample of a text in English is non-Markovian with Hilberg’s exponent being ≤0.83, which improves over the previous bound ≤0.94 obtained using the Lempel–Ziv code. [ABSTRACT FROM PUBLISHER]

This paper studies a decentralized wireless network of asynchronous transmitter–receiver pairs with burst transmissions. Each receiver learns about the number of active users, channel coefficients, and mutual delays based on locally available measurements. The estimates for the mutual delays are not perfect, however, they are reliable enough to guarantee successful decoding. Two signalling schemes are addressed, namely, randomized masking (RM) and reduced cycle transmission (RCT). Under RM, the $n$ symbols of a codeword are generated according to a Bernoulli–Gaussian distribution with activity factor $0<\theta \leq 1$ . This is in contrast to RCT where each codeword consists of $\lfloor \theta n\rfloor $ Gaussian symbols followed by $n-\lfloor \theta n\rfloor $ zeros. Assuming the transmitters are unaware of the number of users, channel coefficients, and mutual delays, the probability of outage under RM is considerably lower compared with RCT if the signal-to-noise ratio (SNR) is sufficiently large. A generalized RCT scheme is also examined where the $n-\lfloor \theta n\rfloor $ zero symbols are not necessarily located at the end of a codeword. In the asymptote of large SNR, the outage probability becomes vanishingly small under RM, however, it is bounded away from zero for generalized RCT regardless of the value of SNR. [ABSTRACT FROM PUBLISHER]

This paper shows that the Maddah-Ali–Tse (MAT) scheme, which achieves the symmetric capacity of two example broadcast channels with strictly causal state information at the transmitter, is a simple special case of the Shayevitz–Wigger (SW) scheme for the broadcast channel with generalized feedback, which involves block Markov coding, Gray–Wyner compression, superposition coding, and Marton coding. Focusing on the class of symmetric broadcast channels with state, we derive an expression for the maximum achievable symmetric rate using the SW scheme. We show that the MAT results for the two-receiver case can be recovered by evaluating this expression for the special case in which superposition coding and Marton coding are not used. We then introduce a new broadcast channel example that shares many features of the MAT examples. We show that another special case of our maximum symmetric rate expression in which superposition coding is also used attains a higher symmetric rate than the MAT scheme. The symmetric capacity of this new example is not known, however. [ABSTRACT FROM PUBLISHER]

The $H$ -transforms are integral transforms that involve Fox’s $H$ -functions as kernels. A large variety of integral transforms can be put into particular forms of the $H$ -transform since $H$ -functions subsume most of the known special functions including Meijer’s $G$ -functions. In this paper, we embody the $H$ -transform theory into a unifying framework for modeling and analysis in wireless communication. First, we systematize the use of elementary identities and properties of the $H$ -transform by introducing operations on parameter sequences of $H$ -functions. We then put forth $H$ -fading and degree-2 irregular $H$ -fading to model radio propagation under composite, specular, and/or inhomogeneous conditions. The $H$ -fading describes composite effects of multipath fading and shadowing as a single $H$ -variate, including most of typical models such as Rayleigh, Nakagami- $m$ , Weibull, $ \alpha - \mu $ , $N\ast $ Nakagami- $m$ , (generalized) $K$ -fading, and Weibull/gamma fading as its special cases. As a new class of $H$ -variates (called the degree- $ \zeta $ irregular $H$ -variate), the degree-2 irregular $H$ -fading characterizes specular and/or inhomogeneous radio propagation in which the multipath component consists of a strong specularly reflected or line-of-sight (LOS) wave as well as unequal-power or correlated in-phase and quadrature scattered waves. This fading includes a variety of typical models such as Rician, Nakagami- $q$ , $ \kappa - \mu $ , $ \eta - \mu $ , Rician/LOS gamma, and $ \kappa - \mu $ /LOS gamma fading as its special cases. Finally, we develop a unifying $H$ -transform analysis for the amount of fading, error probability, channel capacity, and error exponent in wireless communication using the new systematic language of transcendental $H$ -functions. By virtue of two essential operations—called Mellin and convolution operations—involved in the Mellin transform and Mellin convolution of two $H$ -functions, the $H$ -transforms for these performance measures culminate in $H$ -functions. Using the algebraic asymptotic expansions of the $H$ -transform, we further analyze the error probability and capacity at high and low signal-to-noise ratios in a unified fashion. [ABSTRACT FROM PUBLISHER]

In a network, a node is said to incur a delay if its encoding of each transmitted symbol involves only its received symbols obtained before the time slot in which the transmitted symbol is sent (hence the transmitted symbol sent in a time slot cannot depend on the received symbol obtained in the same time slot). A node is said to incur no delay if its received symbol obtained in a time slot is available for encoding its transmitted symbol sent in the same time slot. Under the classical model, every node in a discrete memoryless network (DMN) incurs a unit delay, and the capacity region of the DMN satisfies the well-known cut-set outer bound. In this paper, we propose a generalized model for the DMN where some nodes may incur no delay. Under our generalized model, we obtain a new cut-set outer bound, which is proved to be tight for some two-node DMN and is shown to subsume an existing cut-set bound for the causal relay network. In addition, we establish under the generalized model another cut-set outer bound on the positive-delay region—the set of achievable rate tuples under the constraint that every node incurs a delay. We use the cut-set bound on the positive-delay region to show that for some two-node DMN under the generalized model, the positive-delay region is strictly smaller than the capacity region. [ABSTRACT FROM PUBLISHER]

Random key graphs form a class of random intersection graphs that are naturally induced by the random key predistribution scheme of Eschenauer and Gligor for securing wireless sensor network (WSN) communications. Random key graphs have received much attention recently, owing in part to their wide applicability in various domains, including recommender systems, social networks, secure sensor networks, clustering and classification analysis, and cryptanalysis to name a few. In this paper, we study connectivity properties of random key graphs in the presence of unreliable links. Unreliability of graph links is captured by independent Bernoulli random variables, rendering them to be on or off independently from each other. The resulting model is an intersection of a random key graph and an Erdős–Rényi graph, and is expected to be useful in capturing various real-world networks; e.g., with secure WSN applications in mind, link unreliability can be attributed to harsh environmental conditions severely impairing transmissions. We present conditions on how to scale this model’s parameters so that: 1) the minimum node degree in the graph is at least $k$ and 2) the graph is $k$ -connected, both with high probability as the number of nodes becomes large. The results are given in the form of zero-one laws with critical thresholds identified and shown to coincide for both graph properties. These findings improve the previous results by Rybarczyk on $k$ -connectivity of random key graphs (with reliable links), as well as the zero-one laws by Yağan on one-connectivity of random key graphs with unreliable links. [ABSTRACT FROM PUBLISHER]

Information theory provides principled ways to analyze different inference and learning problems, such as hypothesis testing, clustering, dimensionality reduction, classification, and so forth. However, the use of information theoretic quantities as test statistics, that is, as quantities obtained from empirical data, poses a challenging estimation problem that often leads to strong simplifications, such as Gaussian models, or the use of plug in density estimators that are restricted to certain representation of the data. In this paper, a framework to nonparametrically obtain measures of entropy directly from data using operators in reproducing kernel Hilbert spaces defined by infinitely divisible kernels is presented. The entropy functionals, which bear resemblance with quantum entropies, are defined on positive definite matrices and satisfy similar axioms to those of Renyi’s definition of entropy. Convergence of the proposed estimators follows from concentration results on the difference between the ordered spectrum of the Gram matrices and the integral operators associated to the population quantities. In this way, capitalizing on both the axiomatic definition of entropy and on the representation power of positive definite kernels, the proposed measure of entropy avoids the estimation of the probability distribution underlying the data. Moreover, estimators of kernel-based conditional entropy and mutual information are also defined. Numerical experiments on independence tests compare favorably with state-of-the-art. [ABSTRACT FROM PUBLISHER]

The Rényi entropy of general order unifies the well-known Shannon entropy with several other entropy notions, like the min-entropy or collision entropy. In contrast to the Shannon entropy, there seems to be no commonly accepted definition for the conditional Rényi entropy: several versions have been proposed and used in the literature. In this paper, we reconsider the definition for the conditional Rényi entropy of general order as proposed by Arimoto in the seventies. We show that this particular notion satisfies several natural properties. In particular, we show that it satisfies monotonicity under conditioning, meaning that conditioning can only reduce the entropy, and (a weak form of) chain rule, which implies that the decrease in entropy due to conditioning is bounded by the number of bits one conditions on. None of the other suggestions for the conditional Rényi entropy satisfies both these properties. Finally, we show a natural interpretation of the conditional Rényi entropy in terms of (unconditional) Rényi divergence, and we show consistency with a recently proposed notion of conditional Rényi entropy in the quantum setting. [ABSTRACT FROM PUBLISHER]

Information theoretical inequalities have strong ties with polymatroids and their representability. A polymatroid is entropic if its rank function is given by the Shannon entropy of the subsets of some discrete random variables. The book is a special iterated adhesive extension of a polymatroid with the property that entropic polymatroids have \(n\) -page book extensions over an arbitrary spine. We prove that every polymatroid has an \(n\) -page book extension over a single element and over an all-but-one-element spine. Consequently, for polymatroids on four elements, only book extensions over a two-element spine should be considered. Matúš proved that the Zhang–Yeung inequalities characterize polymatroids on four elements which have such a two-page book extension. The \(n\) -page book inequalities, defined in this paper, are conjectured to characterize polymatroids on four elements which have \(n\) -page book extensions over a two-element spine. We prove that the condition is necessary; consequently, every book inequality is an information inequality on four random variables. Using computer-aided multiobjective optimization, the sufficiency of the condition is verified up to nine-page book extensions. [ABSTRACT FROM PUBLISHER]

We consider a cooperative two-user multiaccess channel in which the transmission is controlled by a random state. Both encoders transmit a common message and, one of the encoders also transmits an individual message. We study the capacity region of this communication model for different degrees of availability of the states at the encoders, causally or strictly causally. In the case in which the states are revealed causally to both encoders but not to the decoder we find an explicit characterization of the capacity region in the discrete memoryless case. In the case in which the states are revealed only strictly causally to both encoders, we establish inner and outer bounds on the capacity region. The outer bound is nontrivial, and has a relatively simple form. It has the advantage of incorporating only one auxiliary random variable. In particular, it suggests that there is none, or at best only little, to gain from having the encoder that transmits both messages also sending an individual description of the state to the receiver, in addition to the compressed version that is sent cooperatively with the other encoder. We then introduce a class of cooperative multiaccess channels with states known strictly causally at both encoders for which the inner and outer bounds agree, and so we characterize the capacity region for this class. In this class of channels, the state can be obtained as a deterministic function of the channel inputs and output. We also study the model in which the states are revealed, strictly causally, in an asymmetric manner, to only one encoder. Throughout this paper, we discuss a number of examples, and compute the capacity region of some of these examples. The results shed more light on the utility of delayed channel state information for increasing the capacity region of state-dependent cooperative multiaccess channels, and tie with recent progress in this framework. [ABSTRACT FROM AUTHOR]

We show how to efficiently simulate the sending of a single message \(M\) to a receiver who has partial information about the message, so that the expected number of bits communicated in the simulation is close to the amount of additional information that the message reveals to the receiver. This is a generalization and strengthening of the Slepian–Wolf theorem, which shows how to carry out such a simulation with low amortized communication in the case that \(M\) is a deterministic function of \(X\) . A caveat is that our simulation is interactive. As a consequence, we prove that the internal information cost (namely the information revealed to the parties) involved in computing any relation or function using a two party interactive protocol is exactly equal to the amortized communication complexity of computing independent copies of the same relation or function. We also show that the only way to prove a strong direct sum theorem for randomized communication complexity is by solving a particular variant of the pointer jumping problem that we define. This paper implies that a strong direct sum theorem for communication complexity holds if and only if efficient compression of communication protocols is possible. In particular, together with our result, a recent result of Ganor, Kol, and Raz implies that the strongest version of direct sum for randomized communication complexity is false. [ABSTRACT FROM AUTHOR]

In this paper, we revisit the structure of infeasibility results in network information theory, based on a notion of information state. We also discuss ideas for generalizing a known outer bound for lossless transmission of independent sources over a network to one of lossy transmission of dependent sources over the same network. To concretely demonstrate this, we apply our ideas and prove new results for lossy transmission of dependent sources by generalizing: 1) the cut-set bound; 2) the best known outer bound on the capacity region of a general broadcast channel; and 3) the outer bound part of the result of Maric, Yates, and Kramer on strong interference channels with a common message. [ABSTRACT FROM AUTHOR]

We study a two-transmitter two-receiver network where Receiver 1 can only hear the transmitted signal of Transmitter 1. Transmitter 1 has two messages, one of which is intended for Receiver 1 while both are intended for Receiver 2. Transmitter 2 has one message which is intended for Receiver 2. We call this channel model the Z channel with degraded message sets. For networks with the element of distributed encoding, it has been shown that when the multiple access link between the two encoders and the decoder satisfies the conditions proposed by Liu and Goldsmith, capacity results can be obtained for a variety of problems. In this paper, we generalize these conditions and show that for a larger class of multiple access links, the capacity region of the Z channel with degraded message sets can be characterized despite the presence of distributed encoding. [ABSTRACT FROM AUTHOR]

The problem of simultaneously generating a secret key (SK) and private key (PK) pair among three terminals via public discussion is investigated. In this problem, each terminal observes a component of correlated sources. All three terminals are required to generate the common SK to be concealed from an eavesdropper that has access to the public discussion, while two designated terminals are required to generate an extra PK to be concealed from both the eavesdropper and the remaining terminal. An outer bound on the SK-PK capacity region was established by Ye and Narayan, and was shown to be achievable for a special case. In this paper, the SK-PK capacity region is established in general by developing schemes to achieve the outer bound for the remaining two cases. The main technique lies in the novel design of a random binning-joint decoding scheme that achieves the existing outer bound. [ABSTRACT FROM AUTHOR]

Shannon's entropy power inequality can be viewed as characterizing the minimum differential entropy achievable by the sum of two independent random variables with fixed differential entropies. The entropy power inequality has played a key role in resolving a number of problems in information theory. It is therefore interesting to examine the existence of a similar inequality for discrete random variables. In this paper, we obtain an entropy power inequality for random variables taking values in a group of order 2^n , i.e., for such a group G , we explicitly characterize the function f_{G}(x,y) giving the minimum entropy of the sum of two independent G$ -valued random variables with respective entropies x$ and y$ . Random variables achieving the extremum in this inequality are thus the analogs of Gaussians in this case, and these are also determined. It turns out that is convex in $x$ for fixed $y$ and, by symmetry, convex in $y$ for fixed $x$ . This is a generalization to groups of order 2^n of the result known as Mrs. Gerber's Lemma. [ABSTRACT FROM AUTHOR]