Search

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]

Given two discrete random variables $X$ and $Y$ , with probability distributions $p=(p_{1}, \ldots , p_{n})$ and $q=(q_{1}, \ldots , q_{m})$ , respectively, let us denote by ${\mathcal{ C}}(p, q)$ the set of all couplings of $p$ and $q$ , that is, the set of all bivariate probability distributions that have $p$ and $q$ as marginals. In this paper, we study the problem of finding a joint probability distribution in ${\mathcal{ C}}(p, q)$ of minimum entropy (equivalently, a coupling that maximizes the mutual information between $X$ and $Y$), and we discuss several situations where the need for this kind of optimization naturally arises. Since the optimization problem is known to be NP-hard, we give an efficient algorithm to find a joint probability distribution in ${\mathcal{ C}}(p, q)$ with entropy exceeding the minimum possible at most by 1 bit, thus providing an approximation algorithm with an additive gap of at most 1 bit. Leveraging on this algorithm, we extend our result to the problem of finding a minimum-entropy joint distribution of arbitrary $k\geq {2}$ discrete random variables $X_{1}, \ldots , X_{k}$ , consistent with the known $k$ marginal distributions of the individual random variables $X_{1}, \ldots , X_{k}$. In this case, our algorithm has an additive gap of at most $\log k$ from optimum. We also discuss several related applications of our findings and extensions of our results to entropies different from the Shannon entropy. [ABSTRACT FROM AUTHOR]

This paper develops a new family of estimators, the minimum density power divergence estimators (MDPDEs), for the parameters of the one-shot device model as well as a new family of test statistics, Z-type test statistics based on MDPDEs, for testing the corresponding model parameters. The family of MDPDEs contains as a particular case the maximum likelihood estimator (MLE) considered in Balakrishnan and Ling (2012). Through a simulation study, it is shown that some MDPDEs have a better behavior than the MLE in terms of robustness. At the same time, it can be seen that some Z-type tests based on MDPDEs have a better behavior than the classical Z-test statistic in terms of robustness, as well. [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]

The capacity under strong asynchronism was recently shown to be essentially unaffected by the imposed decoding delay—the elapsed time between when information is available at the transmitter and when it is decoded—and the output sampling rate. This paper shows that, in contrast with capacity, the second-order term in the maximum rate expansion is sensitive to both parameters. When the receiver must locate the sent codeword exactly and therefore achieve minimum delay equal to the blocklength $n$ , the second-order term in the maximum rate expansion is of order $\Theta (1/\rho)$ for any sampling rate $\rho =O(1/\sqrt {n})$ (and $\rho =\omega (1/n)$ for otherwise reliable communication is impossible). Instead, if $\rho =\omega (1/\sqrt {n})$ , then the second-order term is the same as under full sampling and is given by a standard $\Theta (\sqrt {n})$ term. However, if the delay constraint is only slightly relaxed to $n(1+o(1))$ , then the above order transition (for $\rho =O(1/\sqrt {n})$ and $\rho =\omega (1/\sqrt {n})$) vanishes and the second-order term remains the same as under full sampling for any $\rho =\omega (1/n)$. [ABSTRACT FROM AUTHOR]

This paper considers the fundamental limit of random linear estimation for i.i.d. signal distributions and i.i.d. Gaussian measurement matrices. Its main contribution is a rigorous characterization of the asymptotic mutual information (MI) and minimum mean-square error (MMSE) in this setting. Under mild technical conditions, our results show that the limiting MI and MMSE are equal to the values predicted by the replica method from statistical physics. This resolves a well-known problem that has remained open for over a decade. [ABSTRACT FROM AUTHOR]

We study the first- and second-order asymptotics of covert communication over binary-input discrete memoryless channels for three different covertness metrics and under maximum probability of error constraint. When covertness is measured in terms of the relative entropy between the channel output distributions induced with and without communication, we characterize the exact first- and second-order asymptotics of the number of bits that can be reliably transmitted with a maximum probability of error less than $\epsilon $ and a relative entropy less than $\delta $. When covertness is measured in terms of the variational distance between the channel output distributions or in terms of the probability of missed detection for fixed probability of false alarm, we establish the exact first-order asymptotics and bound the second-order asymptotics. Pulse position modulation achieves the optimal first-order asymptotics for all three metrics, as well as the optimal second-order asymptotics for relative entropy. The main conceptual contribution of this paper is to clarify how the choice of a covertness metric impacts the information-theoretic limits of covert communications. The main technical contribution underlying our results is a detailed expurgation argument to show the existence of a code satisfying the reliability and covertness criteria. [ABSTRACT FROM AUTHOR]

The conventional channel resolvability problem refers to the determination of the minimum rate required for an input process so that the output distribution approximates a target distribution in either the total variation distance or the relative entropy. In contrast to previous works, in this paper, we use the (normalized or unnormalized) Rényi divergence (with the Rényi parameter in $[{0,2}]\cup \{\infty \}$) to measure the level of approximation. We also provide asymptotic expressions for normalized Rényi divergence when the Rényi parameter is larger than or equal to 1 as well as (lower and upper) bounds for the case when the same parameter is smaller than 1. We characterize the Rényi resolvability, which is defined as the minimum rate required to ensure that the Rényi divergence vanishes asymptotically. The Rényi resolvabilities are the same for both the normalized and unnormalized divergence cases. In addition, when the Rényi parameter smaller than 1, consistent with the traditional case where the Rényi parameter is equal to 1, the Rényi resolvability equals the minimum mutual information over all input distributions that induce the target output distribution. When the Rényi parameter is larger than 1 the Rényi resolvability is, in general, larger than the mutual information. The optimal Rényi divergence is proven to vanish at least exponentially fast for both of these two cases, as long as the code rate is larger than the Rényi resolvability. The optimal exponential rate of decay for i.i.d. random codes is also characterized exactly. We apply these results to the wiretap channel, and completely characterize the optimal tradeoff between the rates of the secret and non-secret messages when the leakage measure is given by the (unnormalized) Rényi divergence. This tradeoff differs from the conventional setting when the leakage is measured by the traditional mutual information. [ABSTRACT FROM AUTHOR]

Marton’s inner bound is the best known achievable rate region for a general two-receiver discrete memoryless broadcast channel. In this paper, we establish improved bounds on the cardinalities of the auxiliary random variables appearing in this inner bound to the true rate region. We combine a perturbation technique, along with a representation using concave envelopes of information-theoretic functions that involve the use of auxiliary random variables, to achieve this improvement. The new cardinality bounds lead to a proof that a randomized-time-division strategy achieves every rate triple in Marton’s region for binary input broadcast channels. This extends the result by Hajek and Pursley which showed that the Cover-van der Muelen region was exhausted by the randomized-time-division strategy. [ABSTRACT FROM AUTHOR]

In this paper, we analyze several variants of a simple method for generating prime numbers with fewer random bits. To generate a prime p less than x, the basic idea is to fix a constant q ∝ x 1-ε, pick a uniformly random a < q coprime to q, and choose p of the form a + t · q, where only t is updated if the primality test fails. We prove that variants of this approach provide prime generation algorithms requiring a few random bits and whose output distribution is close to uniform, under less and less expensive assumptions: first a relatively strong conjecture by H. Montgomery, made precise by Friedlander and Granville; then the Extended Riemann Hypothesis; and finally fully unconditionally using the Barban-Davenport-Halberstam theorem. We argue that this approach has a number of desirable properties compared with the previous algorithms, at least in an asymptotic sense. In particular: 1) it uses much fewer random bits than both the “trivial algorithm” (testing random numbers less than x for primality) and Maurer's almost uniform prime generation algorithm; 2) the distance of its output distribution to uniform can be made arbitrarily small, unlike algorithms like PRIMEINC (studied by Brandt and Damgård), which we show exhibit significant biases; and 3) all quality measures (number of primality tests, output entropy, randomness, and so on) can be obtained under standard conjectures or even unconditionally, whereas most previous nontrivial algorithms can only be proved based on stronger, less standard assumptions like the Hardy-Littlewood prime tuple conjecture. Note, however, that our analysis involves non-explicit constants, and therefore does not establish the superiority of our approach for concrete parameter sizes. [ABSTRACT FROM AUTHOR]

An important problem in secret sharing schemes is minimizing the share size. For ($k$ , $n$)-threshold schemes and ($k$ , $L$ , $n$)-ramp schemes, constructions that minimize the share size are known. This paper presents optimal constructions for a more general class of access structures in which subsets with the same cardinality have the same amount of information about the secret. We refer to schemes with such uniform access structures as uniform secret sharing. We first derive a tight lower bound for share entropy and then present an optimal construction. Our lower bound exceeds that previously reported. The optimal construction encodes the secret value using one or more ramp schemes. [ABSTRACT FROM AUTHOR]

This paper obtains the first degrees of freedom (DoFs) bound that is provably sensitive tonetworkcoherence time, i.e., coherence time in an interference network, where all channels experience the same coherence patterns. This is accomplished by a novel adaptation of the aligned image sets bound and settles various open problems noted previously by Naderi and Avestimehr and by Gouet al.For example, a necessary and sufficient condition is obtained for the optimality of 1/2 DoF per user in a partially connected interference network, where the channel state information at the receivers (CSIRs) is perfect, the channel state information at the transmitters (CSITs) is instantaneous but limited to finite precision, and the network coherence time is $T_{c}=1$. The surprising insight that emerges is that even with perfect CSIR and instantaneous finite precision CSIT, the network coherence time matters, i.e., it has a DoF impact. [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]

In this paper, we consider distributed testing problems with cascaded encoders, which allow cascaded communications among encoders so that each encoder can utilize messages from other encoders for encoding. We first focus on a special case of testing against independence and design a scheme that enables each encoder to take advantage of extra information from other encoders. We also derive a matching upper bound and prove that the designed scheme is optimal. We then investigate the case with general hypotheses and obtain a lower bound on the type 2 error exponent. We further compare the performances that can be achieved by schemes with and without cascaded communications. We show that cascaded communication improves the performance in terms of the type 2 error exponent under positive rate communication constraints. On the other hand, we prove that cascaded communication does not provide performance gain under zero-rate communication constraints. [ABSTRACT FROM AUTHOR]

The ordering of communication channels was first introduced by Shannon. In this paper, we aim to find characterizations of two orderings: input-degradedness and the Shannon ordering. A channel $W$ is said to be input-degraded from another channel $W'$ if $W$ can be simulated from $W'$ by randomization at the input. We provide a necessary and sufficient condition for a channel to be input-degraded from another one. We show that any decoder that is good for $W$ is also good for $W'$. We provide two characterizations for input-degradedness, one of which is similar to the Blackwell-Sherman-Stein theorem. We show that $W'$ contains $W$ (in the Shannon ordering sense) if and only if $W$ is the skew-composition of $W'$ with a convex-product $n$ channel. This fact is used to derive a characterization of the Shannon ordering that is similar to the Blackwell-Sherman-Stein theorem. [ABSTRACT FROM AUTHOR]

Compressed sensing is now established as an effective method for dimension reduction when the underlying signals are sparse or compressible with respect to some suitable basis or frame. One important, yet under-addressed problem regarding the compressive acquisition of analog signals is how to perform quantization. This is directly related to the important issues of how “compressed” compressed sensing is (in terms of the total number of bits one ends up using after acquiring the signal) and ultimately whether compressed sensing can be used to obtain compressed representations of suitable signals. In this paper, we propose a concrete and practicable method for performing “analog-to-information conversion”. Following a compressive signal acquisition stage, the proposed method consists of a quantization stage, based on $ \Sigma \Delta $ (sigma-delta) quantization, and a subsequent encoding (compression) stage that fits within the framework of compressed sensing seamlessly. We prove that, using this method, we can convert analog compressive samples to compressed digital bitstreams and decode using tractable algorithms based on convex optimization. We prove that the proposed analog-to-information converter (AIC) provides a nearly optimal encoding of sparse and compressible signals. Finally, we present numerical experiments illustrating the effectiveness of the proposed AIC. [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]

Separable codes were defined by Cheng and Miao in 2011, motivated by applications to the identification of pirates in a multimedia setting. Combinatorially, \overline t -separable codes lie somewhere between t -frameproof and (t-1) -frameproof codes: all t -frameproof codes are (t-1) -frameproof. Results for frameproof codes show that (when q is large) there are q codewords, and that no q -ary n can have more than approximately codewords. This paper provides improved probabilistic existence results for t\geq 3 . More precisely, for all t\geq 3 and all n\geq 3 , there exists a constant \kappa (depending only on t and n ), such that there exists a codewords for all sufficiently large integers q . This shows, in particular, that the upper bound [derived from the bound on (t-1) -frameproof codes] on the number of codewords in a t=2 . Results due to Gao and Ge show that a q -separable code of length n can contain at most \frac {3}{2}q^{2\lceil n/3\rceil }-\frac {1}{2}q^{\lceil n/3\rceil } codewords, and that codes with at least \kappa q^{2n/3} codewords exist. Thus, optimal \overline 2 -separable codes behave neither like two-frameproof nor one-frameproof codes. This paper also observes that the bound of Gao and Ge can be strengthened to show that the number of codewords of a q -ary \overline 2 -separable code of length $n$ is at most q^{\lceil 2n/3\rceil }+\tfrac {1}{2}q^{\lfloor n/3\rfloor }(q^{\lfloor n/3\rfloor }-1) . [ABSTRACT FROM PUBLISHER]

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 this paper, we study the problem of channel simulation via interactive communication, known as the coordination capacity, in a two-terminal network. We assume that two terminals observe independent identically distributed (i.i.d.) copies of two random variables and would like to generate i.i.d. copies of two other random variables jointly distributed with the observed random variables. The terminals are provided with two-way communication links, and shared common randomness, all at limited rates. Two special cases of this problem are the interactive function computation studied by Ma and Ishwar, and the tradeoff curve between one-way communication and shared randomness studied by Cuff. The latter work had inspired Gohari and Anantharam to study the general problem of channel simulation via interactive communication stated above. However, only inner and outer bounds for the special case of no shared randomness were obtained in their work. In this paper, we settle this problem by providing an exact computable characterization of the multiround problem. To show this we employ the technique of output statistics of random binning that has been recently developed by the authors. [ABSTRACT FROM AUTHOR]

The history of infections and epidemics holds famous examples where understanding, containing, and ultimately treating an outbreak began with understanding its mode of spread. Influenza, HIV, and most computer viruses spread person to person, device to device, and through contact networks; Cholera, Cancer, and seasonal allergies, on the other hand, do not. In this paper, we study two fundamental questions of detection. First, given a snapshot view of a (perhaps vanishingly small) fraction of those infected, under what conditions is an epidemic spreading via contact (e.g., Influenza), distinguishable from a random illness operating independently of any contact network (e.g., seasonal allergies)? Second, if we do have an epidemic, under what conditions is it possible to determine which network of interactions is the main cause of the spread—the causative network—without any knowledge of the epidemic, other than the identity of a minuscule subsample of infected nodes? The core, therefore, of this paper, is to obtain an understanding of the diagnostic power of network information. We derive sufficient conditions that networks must satisfy for these problems to be identifiable, and produce efficient, highly scalable algorithms that solve these problems. We show that the identifiability condition we give is fairly mild, and in particular, is satisfied by two common graph topologies: the $d$ -dimensional grid, and the Erdös-Renyi graphs. [ABSTRACT FROM AUTHOR]

Guyon (Guyon J. Limit theorems for bifurcating Markov chains. Application to the detection of cellular aging. Ann Appl Probab, 2007, 17: 1538-1569) introduced an important model for homogeneous bifurcating Markov chains indexed by a binary tree taking values in general state space and studied their limit theorems. The results were applied to detect cellular aging. In this paper, we define a discrete form of nonhomogeneous bifurcating Markov chains indexed by a binary tree and discuss the equivalent properties for them. The strong law of large numbers and the entropy ergodic theorem are studied for these Markov chains with finite state space. In contrast to previous work, we use a new approach to prove the main results of this paper. [ABSTRACT FROM AUTHOR]

We consider the problem of information embedding where the encoder modifies a white Gaussian host signal in a power-constrained manner to encode a message, and the decoder recovers both the embedded message and the modified host signal. This partially extends the recent work of Sumszyk and Steinberg to the continuous-alphabet Gaussian setting. Through a control-theoretic lens, we observe that the problem is a minimalist example of what is called the triple role of control actions. We show that a dirty-paper-coding strategy achieves the optimal rate for perfect recovery of the modified host and the message for any message rate. For imperfect recovery of the modified host, by deriving bounds on the minimum mean-square error (MMSE) in recovering the modified host signal, we show that Dirty-Paper Coding-based strategies are guaranteed to attain within a uniform constant factor of 16 of the optimal weighted sum of power required in host signal modification and the MMSE in the modified host signal reconstruction for all weights and all message rates. When specialized to the zero-rate case, our results provide the tightest known lower bounds on the asymptotic costs for the vector version of a famous open problem in decentralized control: the Witsenhausen counterexample. Numerically, this tighter bound helps us characterize the asymptotically optimal costs for the vector Witsenhausen problem to within a factor of 1.3 for all problem parameters, improving on the earlier best known bound of 2. [ABSTRACT FROM AUTHOR]

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 presents polar coding schemes for the two-user discrete memoryless broadcast channel (DM-BC) which achieve Marton’s region with both common and private messages. This is the best achievable rate region known to date, and it is tight for all classes of two-user DM-BCs whose capacity regions are known. To accomplish this task, we first construct polar codes for both the superposition as well as binning strategy. By combining these two schemes, we obtain Marton’s region with private messages only. Finally, we show how to handle the case of common information. The proposed coding schemes possess the usual advantages of polar codes, i.e., they have low encoding and decoding complexity and a superpolynomial decay rate of the error probability. We follow the lead of Goela, Abbe, and Gastpar, who recently introduced polar codes emulating the superposition and binning schemes. To align the polar indices, for both schemes, their solution involves some degradedness constraints that are assumed to hold between the auxiliary random variables and channel outputs. To remove these constraints, we consider the transmission of $k$ blocks and employ a chaining construction that guarantees the proper alignment of the polarized indices. The techniques described in this paper are quite general, and they can be adopted to many other multiterminal scenarios whenever there polar indices need to be aligned. [ABSTRACT FROM AUTHOR]

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]

In this paper, Bayesian quickest change detection problems with sampling right constraints are considered. In particular, there is a sequence of random variables whose probability density function will change at an unknown time. The goal is to detect this change in a way such that a linear combination of the average detection delay and the false alarm probability is minimized. Two types of sampling right constrains are discussed. The first one is a limited sampling right constraint, in which the observer can take at most \(N\) observations from this random sequence. Under this setup, we show that the cost function can be written as a set of iterative functions, which can be solved by Markov optimal stopping theory. The optimal stopping rule is shown to be a threshold rule. An asymptotic upper bound of the average detection delay is developed as the false alarm probability goes to zero. This upper bound indicates that the performance of the limited sampling right problem is close to that of the classic Bayesian quickest detection for several scenarios of practical interest. The second constraint discussed in this paper is a stochastic sampling right constraint, in which sampling rights are consumed by taking observations and are replenished randomly. The observer cannot take observations if there are no sampling rights left. We characterize the optimal solution, which has a very complex structure. For practical applications, we propose a low complexity algorithm, in which the sampling rule is to take observations as long as the observer has sampling rights left and the detection scheme is a threshold rule. We show that this low complexity scheme is first order asymptotically optimal as the false alarm probability goes to zero. [ABSTRACT FROM AUTHOR]

In this paper, we use entropy functions to characterize the set of rate-capacity tuples achievable with either zero decoding error, or vanishing decoding error, for general network coding problems for acyclic networks. We show that when sources are colocated, the outer bound is tight and the sets of zero-error achievable and vanishing-error achievable rate-capacity tuples are the same. Then, we extend this paper to networks subject to linear encoding constraints, routing constraints (where some or all nodes can only perform routing), and secrecy constraints. Finally, we show that even for apparently simple networks, design of optimal codes may be difficult. In particular, we prove that for the incremental multicast problem and for the single-source secure network coding problem, characterization of the achievable set can be very hard and linear network codes may not be optimal. [ABSTRACT FROM AUTHOR]

The second-order achievable rate region in Slepian-Wolf source coding systems is investigated. The concept of second-order achievable rates, which enables us to make a finer evaluation of achievable rates, has already been introduced and analyzed for general sources in the single-user source coding problem. Analogously, in this paper, we first define the second-order achievable rate region for the Slepian–Wolf coding system to establish the source coding theorem in the second-order sense. The Slepian–Wolf coding problem for correlated sources is one of typical problems in the multiterminal information theory. In particular, Miyake and Kanaya, and Han have established the first-order source coding theorems for general correlated sources. On the other hand, in general, the second-order achievable rate problem for the Slepian–Wolf coding system with general sources remains still open up to present. In this paper, we present the analysis concerning the second-order achievable rates for general sources, which are based on the information spectrum methods developed by Han and Verdú. Moreover, we establish the explicit second-order achievable rate region for independently and identically distributed (i.i.d.) correlated sources with countably infinite alphabets and mixtures of i.i.d. correlated sources, respectively, using the relevant asymptotic normality. [ABSTRACT FROM AUTHOR]

In this paper, we consider different aspects of the problem of compressing for function computation across a network, which we call network functional compression. In network functional compression, computation of a function (or, some functions) of sources located at certain nodes in a network is desired at receiver(s). The rate region of this problem has been considered in the literature under certain restrictive assumptions, particularly in terms of the network topology, the functions, and the characteristics of the sources. In this paper, we present results that significantly relax these assumptions. For a one-stage tree network, we characterize a rate region by introducing a necessary and sufficient condition for any achievable coloring-based coding scheme called coloring connectivity condition. We also propose a modularized coding scheme based on graph colorings to perform arbitrarily closely to rate lower bounds. For a general tree network, we provide a rate lower bound based on graph entropies and show that, this bound is tight in the case of having independent sources. In particular, we show that, in a general tree network case with independent sources, to achieve the rate lower bound, intermediate nodes should perform computations. However, for a family of functions and random variables, which we call chain-rule proper sets, it is sufficient to have no computations at intermediate nodes to perform arbitrarily closely to the rate lower bound. In addition, we consider practical issues of coloring-based coding schemes and propose an efficient algorithm to compute a minimum entropy coloring of a characteristic graph under some conditions on source distributions and/or the desired function. Finally, extensions of these results for cases of having feedback and lossy function computations are discussed. [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]

This paper investigates the downlink of a cloud radio access network (C-RAN) in which a central processor communicates with two mobile users through two base stations (BSs). The BSs act as relay nodes and cooperate with each other through error-free rate-limited links. We develop and analyze two coding schemes for this scenario. The first coding scheme modifies the Liu–Kang scheme (to make it amenable to a rigorous analysis) and extends it to introduce common codewords and to apply for downlink C-RAN with BS-to-BS cooperation. This first coding scheme enables arbitrary correlation among the auxiliary codewords that are recovered by the BSs. We show that this scheme improves over previous schemes for various instances of Gaussian C-RAN channels. In particular, in many scenarios, the scheme can better exploit the possibility of BS-to-BS cooperation than other schemes. The second coding scheme extends the distributed decode and forward (DDF) scheme by means of Gray–Wyner compression and by exploiting the cooperation links between BSs. In addition and as a separate extension, we provide an improved capacity approximation for the DDF strategy for the capacity of a general $N$ -BS $L$ -user C-RAN model in the memoryless Gaussian case. [ABSTRACT FROM AUTHOR]

This paper studies the basic question of whether a given channel $V$ can be dominated (in the precise sense of being more noisy) by a $q$ -ary symmetric channel. The concept of less noisy relation between channels originated in network information theory (broadcast channels) and is defined in terms of mutual information or Kullback–Leibler divergence. We provide an equivalent characterization in terms of $\chi ^{2}$ -divergence. Furthermore, we develop a simple criterion for domination by a $q$ -ary symmetric channel in terms of the minimum entry of the stochastic matrix defining the channel $V$. The criterion is strengthened for the special case of additive noise channels over finite Abelian groups. Finally, it is shown that domination by a symmetric channel implies (via comparison of Dirichlet forms) a logarithmic Sobolev inequality for the original channel. [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]

The sparsity and compressibility of finite-dimensional signals are of great interest in fields, such as compressed sensing. The notion of compressibility is also extended to infinite sequences of independent identically distributed or ergodic random variables based on the observed error in their nonlinear $k$ -term approximation. In this paper, we use the entropy measure to study the compressibility of continuous-domain innovation processes (alternatively known as white noise). Specifically, we define such a measure as the entropy limit of the doubly quantized (time and amplitude) process. This provides a tool to compare the compressibility of various innovation processes. It also allows us to identify an analogue of the concept of “entropy dimension” which was originally defined by Rényi for random variables. Particular attention is given to stable and impulsive Poisson innovation processes. Here, our results recognize Poisson innovations as the more compressible ones with an entropy measure far below that of stable innovations. While this result departs from the previous knowledge regarding the compressibility of impulsive Poisson laws compared with continuous fat-tailed distributions, our entropy measure ranks $\alpha$ -stable innovations according to their tail. [ABSTRACT FROM AUTHOR]

In this paper, a general binary-input binary-output channel is investigated in the presence of feedback and input constraints. The feedback capacity and the optimal input distribution of this setting are calculated for the case of an $(1,\infty )$ -RLL input constraint, that is, the input sequence contains no consecutive ones. These results are obtained via explicit solution of an equivalent dynamic programming optimization problem. A simple coding scheme is designed based on the principle of posterior matching, which was introduced by Shayevitz and Feder for memoryless channels. The posterior matching scheme for our input-constrained setting is shown to achieve capacity using two new ideas: history bits, which captures the memory embedded in our setting, and message-interval splitting, which eases the analysis of the scheme. Additionally, in the special case of an S-channel, we give a very simple zero-error coding scheme that is shown to achieve capacity. For the input-constrained binary symmetric channel, we show using our capacity formula that feedback increases capacity when the cross-over probability is small. [ABSTRACT FROM AUTHOR]

Rivest and Shamir introduced a write-once memory (WOM), a model of storage devices whose storage elements have restrictions on state transitions, and they presented some coding methods to reuse a WOM. An interesting question about a WOM is how efficiently we can reuse it with the best coding method, and as an answer to the question, Fu and Han Vinck determined the capacity of Fiat and Shamir’s generalized WOMs. In this paper, we extend their results, introducing write-constrained memories (WCMs) that consider state transition costs, and determining the capacity of WCMs under a certain type of cost constraints. [ABSTRACT FROM AUTHOR]

High-order cumulants and high-order spectra play an important role in the theory of stationary processes. For nonlinear processes, it is quite challenging to develop an asymptotic theory for their estimators. This paper presents a systematic asymptotic theory for estimators of high-order moments for a general class of stationary processes, using the framework of functional dependence measures. In particular, we prove the asymptotic normality of the estimators and establish a uniform convergence rate. We also provide a sufficient condition for the summability of high-order cumulants. Based on the latter, we prove consistency and asymptotic normality of the third-order spectra or bispectrum estimators under mild and easily verifiable conditions. [ABSTRACT FROM AUTHOR]

We consider a broadcast channel with three receivers and three-degraded message sets, i.e., the transmitter has a common message intended for all three receivers, a message intended for receivers 2 and 3, and a private message intended only for receiver 3. The messages are transmitted over a family of parallel degraded broadcast channels. In the most general case, the broadcast channel consists of the product of six parallel degraded broadcast channels, each with a different order of degradedness. We first consider an achievable rate region of Nair and El Gamal, by appropriately choosing independent input random variables and auxiliary random variables for each subchannel. We then show that the achievable rate region attains the capacity region for two different classes of such broadcast channels, one consisting of the product of five parallel degraded broadcast channels and another consisting of the product of three parallel degraded broadcast channels. To accomplish this, we make use of an information-theoretic inequality that may be proven using the Csiszár-sum identity. Next, we extend the result to the Gaussian case. We consider the aligned Gaussian MIMO broadcast channel consisting of the product of six parallel degraded Gaussian broadcast channels, where the Gaussian noise vectors for each of the users in each of the subchannels follow a degradedness order, i.e., the noise covariance matrices may be ordered in a positive semi-definite sense. We show that the Nair–El Gamal achievable rate region considered in this paper is maximized by Gaussian inputs. To prove that Gaussian inputs are optimal, we prove an extremal entropy inequality employing a new method recently introduced by Geng and Nair to prove the capacity region of the two-user Gaussian MIMO broadcast channel with common and private messages. [ABSTRACT FROM AUTHOR]

In this paper, we study the cycle distribution of random low-density parity-check (LDPC) codes, randomly constructed protograph-based LDPC codes, and random quasi-cyclic (QC) LDPC codes. We prove that for a random bipartite graph, with a given (irregular) degree distribution, the distributions of cycles of different length tend to independent Poisson distributions, as the size of the graph tends to infinity. We derive asymptotic upper and lower bounds on the expected values of the Poisson distributions that are independent of the size of the graph, and only depend on the degree distribution and the cycle length. For a random lift of a bi-regular protograph, we prove that the asymptotic cycle distributions are essentially the same as those of random bipartite graphs as long as the degree distributions are identical. For random QC-LDPC codes, however, we show that the cycle distribution can be quite different from the other two categories. In particular, depending on the protograph and the value of $c$ , the expected number of cycles of length $c$ , in this case, can be either $\Theta (N)$ or $\Theta (1)$ , where $N$ is the lifting degree (code length). We also provide numerical results that match our theoretical derivations. Our results provide a theoretical foundation for emperical results that were reported in the literature but were not well-justified. They can also be used for the analysis and design of LDPC codes and associated algorithms that are based on cycles. [ABSTRACT FROM AUTHOR]

This paper addresses the correspondence between linear inequalities for Shannon entropy and differential entropy for sums of independent group-valued random variables. We show that any balanced (with the sum of coefficients being zero) linear inequality for Shannon entropy holds if and only if its differential entropy counterpart also holds; moreover, any linear inequality for differential entropy must be balanced. In particular, our result shows that recently proved differential entropy inequalities by Kontoyiannis and Madiman can be deduced from their discrete counterparts due to Tao in a unified manner. Generalizations to certain abelian groups are also obtained. Our proof of extending inequalities for Shannon entropy to differential entropy relies on a result of Rényi which relates the Shannon entropy of a finely discretized random variable to its differential entropy and also helps in establishing that the entropy of the sum of quantized random variables is asymptotically equal to that of the quantized sum; the converse uses the asymptotics of the differential entropy of convolutions with weak additive noise. [ABSTRACT FROM PUBLISHER]

A measure of correlation is said to have the tensorization property if it does not change when computed for i.i.d. copies. More precisely, a measure of correlation between two random variables X, Y denoted by \rho (X, Y) , has the tensorization property if \rho (X^n, Y^n)=\rho (X, Y) where (X^n, Y^n) denotes $n$ i.i.d. copies of (X, Y)$ . Two well-known examples of such measures are the maximal correlation and the hypercontractivity ribbon (HC ribbon). We show that the maximal correlation and the HC ribbon are special cases of the new notion of \Phi $ -ribbons, defined in this paper for a class of convex functions \Phi $ . \Phi $ -ribbon reduces to the HC ribbon and the maximal correlation for special choices of \Phi $ , and is a measure of correlation with the tensorization property. We show that the \Phi $ -ribbon also characterizes the recently introduced and introduce an equivalent characterization of this ribbon. [ABSTRACT FROM AUTHOR]

It is well known that the entropy $H(X)$ of a discrete random variable $X$ is always greater than or equal to the entropy $H(f(X))$ of a function $f$ of $X$ , with equality if and only if $f$ is one-to-one. In this paper, we give tight bounds on $H(f(X))$ , when the function $f$ is not one-to-one, and we illustrate a few scenarios, where this matters. As an intermediate step toward our main result, we derive a lower bound on the entropy of a probability distribution, when only a bound on the ratio between the maximal and minimal probabilities is known. The lower bound improves on previous results in the literature, and it could find applications outside the present scenario. [ABSTRACT FROM AUTHOR]

In this paper, the optimal sampling strategies (uniform or nonuniform) and distortion tradeoffs for Gaussian bandlimited periodic signals with additive white Gaussian noise are studied. Our emphasis is on characterizing the optimal sampling locations as well as the optimal presampling filter to minimize the reconstruction distortion. We first show that to achieve the optimal distortion, no presampling filter is necessary for any arbitrary sampling rate. Then, we provide a complete characterization of optimal distortion for low and high sampling rates (with respect to the signal bandwidth). We also provide bounds on the reconstruction distortion for rates in the intermediate region. It is shown that nonuniform sampling outperforms uniform sampling for low sampling rates. In addition, the optimal nonuniform sampling set is robust with respect to missing sampling values. On the other hand, for the sampling rates above the Nyquist rate, the uniform sampling strategy is optimal. [ABSTRACT FROM PUBLISHER]

This paper investigates the achievable rates of an additive white Gaussian noise energy-harvesting (EH) channel with an infinite battery. The EH process is characterized by a sequence of blocks of harvested energy, which is known causally at the source. The harvested energy remains constant within a block while the harvested energy across different blocks is characterized by a sequence of independent and identically distributed random variables. The blocks have length $L$ , which can be interpreted as the coherence time of the energy-arrival process. If L$ is a constant or grows sublinearly in the blocklength n$ , we fully characterize the first-order term in the asymptotic expansion of the maximum transmission rate subject to a fixed tolerable error probability \varepsilon $ . The first-order term is known as the \varepsilon for any $\varepsilon $ less than 1/2. The lower bound is obtained through analyzing the save-and-transmit strategy. If $L$ grows linearly in $n$ , we obtain lower and upper bounds on the $\varepsilon $ -capacity, which coincide whenever the cumulative distribution function of the EH random variable is continuous and strictly increasing. In order to achieve the lower bound, we have proposed a novel adaptive save-and-transmit strategy, which chooses different save-and-transmit codes across different blocks according to the energy variation across the blocks. [ABSTRACT FROM PUBLISHER]

Usually, it is very difficult to determine the exact distribution for a test statistic. In this paper, asymptotic distributions of locally most powerful invariant test for independence of complex Gaussian vectors are developed. In particular, its cumulative distribution function (CDF) under the null hypothesis is approximated by a function of chi-squared CDFs. Moreover, the CDF corresponding to the non-null distribution is expressed in terms of non-central chi-squared CDFs for close hypothesis, and Gaussian CDF as well as its derivatives for far hypothesis. The results turn out to be very accurate in terms of fitting their empirical counterparts. Closed-form expression for the detection threshold is also provided. Numerical results are presented to validate our theoretical findings. [ABSTRACT FROM PUBLISHER]

We revisit the problem of asymmetric binary hypothesis testing against a composite alternative hypothesis. We introduce a general framework to treat such problems when the alternative hypothesis adheres to certain axioms. In this case, we find the threshold rate, the optimal error and strong converse exponents (at large deviations from the threshold), and the second order asymptotics (at small deviations from the threshold). We apply our results to find the operational interpretations of various Rényi information measures. In case the alternative hypothesis is comprised of bipartite product distributions, we find that the optimal error and strong converse exponents are determined by the variations of Rényi mutual information. In case the alternative hypothesis consists of tripartite distributions satisfying the Markov property, we find that the optimal exponents are determined by the variations of Rényi conditional mutual information. In either case, the relevant notion of Rényi mutual information depends on the precise choice of the alternative hypothesis. As such, this paper also strengthens the view that different definitions of Rényi mutual information, conditional entropy, and conditional mutual information are adequate depending on the context in which the measures are used. [ABSTRACT FROM AUTHOR]

In this paper, we propose an open-loop unequal-error-protection querying policy based on superposition coding for the noisy 20 questions problem. In this problem, a player wishes to successively refine an estimate of the value of a continuous random variable by posing binary queries and receiving noisy responses. When the queries are designed non-adaptively as a single block and the noisy responses are modeled as the output of a binary symmetric channel, the 20 questions problem can be mapped to an equivalent problem of channel coding with unequal error protection (UEP). A new non-adaptive querying strategy based on UEP superposition coding is introduced, whose estimation error decreases with an exponential rate of convergence that is significantly better than that of the UEP repetition coding introduced by Variani et al. (2015). With the proposed querying strategy, the rate of exponential decrease in the number of queries matches the rate of a closed-loop adaptive scheme, where queries are sequentially designed with the benefit of feedback. Furthermore, the achievable error exponent is significantly better than that of random block codes employing equal error protection. [ABSTRACT FROM AUTHOR]

In this paper, we introduce new Stein identities for gamma target distribution as well as a new non-linear channel specifically designed for gamma inputs. From these two ingredients, we derive an explicit and simple formula for the derivative of the input-output mutual information of this non-linear channel with respect to the channel quality parameter. This relation is reminiscent of the well-known link between the derivative of the input-output mutual information of additive Gaussian noise channel with respect to the signal-to-noise ratio and the minimum mean-square error. The proof relies on a rescaled version of De Bruijn identity for gamma target distribution together with a stochastic representation for the gamma-specific Fisher information. Finally, we are able to derive precise bounds and asymptotics for the input-output mutual information of the non-linear channel with gamma inputs. [ABSTRACT FROM AUTHOR]

We study the communication efficient secret sharing (CESS) problem. A classical threshold secret sharing scheme encodes a secret into $n$ shares given to n$ parties, such that any set of at least t$ , t n$ . However, Staircase codes may require dividing the secret and the shares into many symbols. We also describe how Staircase codes can be used to construct threshold changeable secret sharing with minimum storage cost, i.e., minimum share size. [ABSTRACT FROM AUTHOR]