Search

This paper studies the problem of estimating the covariance of a collection of vectors using only highly compressed measurements of each vector. An estimator based on back-projections of these compressive samples is proposed and analyzed. A distribution-free analysis shows that by observing just a single linear measurement of each vector, one can consistently estimate the covariance matrix, in both infinity and spectral norm, and this analysis leads to precise rates of convergence in both norms. Through information-theoretic techniques, lower bounds showing that this estimator is minimax-optimal for both infinity and spectral norm estimation problems are established. These results are also specialized to give matching upper and lower bounds for estimating the population covariance of a collection of Gaussian vectors, again in the compressive measurement model. The analysis conducted in this paper shows that the effective sample complexity for this problem is scaled by a factor of $m^{2}/d^{2}$ , where $m$ is the compression dimension and $d$ is the ambient dimension. Applications to subspace learning (principal components analysis) and learning over distributed sensor networks are also discussed. [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]

Let X and Y be dependent random variables. This paper considers the problem of designing a scalar quantizer for Y to maximize the mutual information between the quantizer’s output and X, and develops fundamental properties and bounds for this form of quantization, which is connected to the log-loss distortion criterion. The main focus is the regime of low ${I}({X};{Y})$ , where it is shown that, if X is binary, a constant fraction of the mutual information can always be preserved using $\mathcal {O}(\log (1/{I}({X};{Y})))$ quantization levels, and there exist distributions for which this many quantization levels are necessary. Furthermore, for larger finite alphabets $2 < |\mathcal {X}| < \infty $ , it is established that an $\eta $ -fraction of the mutual information can be preserved using roughly $(\log (| \mathcal {X} | /{I}({X};{Y})))^{\eta \cdot (|\mathcal {X}| - 1)}$ quantization levels. [ABSTRACT FROM AUTHOR]

This paper provides a precise error analysis for the maximum likelihood estimate $\hat {\textit a}_{\text {ML}}({\textit u}_{1}^{\textit n})$ of the parameter ${\textit a}$ given samples ${\textit u}_{1}^{\textit n} = ({\textit u}_{1}, \ldots, {\textit u}_{\textit n})'$ drawn from a nonstationary Gauss-Markov process ${\textit U}_{\textit i} = {\textit a} {\textit U}_{\textit i-1} + {\textit Z}_{\textit i},\,\,{\textit i}\geq 1$ , where ${\textit U}_{0} = 0$ , ${\textit a}> 1$ , and ${\textit Z}_{\textit i}$ ’s are independent Gaussian random variables with zero mean and variance $\sigma ^{2}$. We show a tight nonasymptotic exponentially decaying bound on the tail probability of the estimation error. Unlike previous works, our bound is tight already for a sample size of the order of hundreds. We apply the new estimation bound to find the dispersion for lossy compression of nonstationary Gauss-Markov sources. We show that the dispersion is given by the same integral formula that we derived previously for the asymptotically stationary Gauss-Markov sources, i.e., $|{\textit a}| < 1$. New ideas in the nonstationary case include separately bounding the maximum eigenvalue (which scales exponentially) and the other eigenvalues (which are bounded by constants that depend only on a) of the covariance matrix of the source sequence, and new techniques in the derivation of our estimation error bound. [ABSTRACT FROM AUTHOR]

In many information-theoretic channel coding problems, adding an input cost constraint to the operational setup amounts to restricting the optimization domain in the capacity formula. This paper shows that, in contrast to common belief, such a simple modification does not hold for the cost-constrained (CC) wiretap channel (WTC). The secrecy-capacity of the discrete memoryless (DM) WTC without cost constraints is described by a single auxiliary random variable. For the CC DM-WTC, however, we show that two auxiliaries are necessary to achieve capacity. Specifically, we first derive the secrecy-capacity formula, proving the direct part via superposition coding. Then, we provide an example of a CC DM-WTC whose secrecy-capacity cannot be achieved using a single auxiliary. This establishes the fundamental role of superposition coding over CC WTCs. [ABSTRACT FROM AUTHOR]

The objective of a genome-wide association study (GWAS) is to associate subsequences of individuals’ genomes to the observable characteristics called phenotypes (e.g., high blood pressure). Motivated by the GWAS problem, in this paper we introduce the information-theoretic problem of associated subsequence retrieval, where a dataset of N (possibly high-dimensional) sequences of length G, and their corresponding observable (binary) characteristics is given. The sequences are chosen independently and uniformly at random from $\mathcal {X}^{\text {G}}$ , where $\mathcal {X}$ is a finite alphabet. The observable (binary) characteristic is only related to a specific unknown subsequence of length $L$ of the sequences, called associated subsequence. For each sequence, if the associated subsequence of it belongs to a universal finite set, then it is more likely to display the observable characteristic (i.e., it is more likely that the observable characteristic is one). The goal is to retrieve the associated subsequence using a dataset of N sequences and their observable characteristics. We demonstrate that as the parameters N, G, and L grow, a threshold effect appears in the curve of probability of error versus the rate which is defined as ${{\it\text { Gh}}(\text {L}/\text {G})}/{\text {N}}$ , where $\text {h}(\cdot)$ is the binary entropy function. This effect allows us to define the capacity of associated subsequence retrieval. We develop an achievable scheme and a matching converse for this problem, and thus characterize its capacity in two scenarios: the zero-error-rate and the $\epsilon $ -error-rate. [ABSTRACT FROM AUTHOR]

The support recovery problem consists of determining a sparse subset of variables that is relevant in generating a set of observations. In this paper, we study the support recovery problem in the phase retrieval model consisting of noisy phaseless measurements, which arises in a diverse range of settings such as optical detection, X-ray crystallography, electron microscopy, and coherent diffractive imaging. Our focus is on information-theoretic fundamental limits under an approximate recovery criterion, considering both discrete and Gaussian models for the sparse non-zero entries, along with Gaussian measurement matrices. In both cases, our bounds provide sharp thresholds with near-matching constant factors in several scaling regimes on the sparsity and signal-to-noise ratio. As a key step towards obtaining these results, we develop new concentration bounds for the conditional information content of log-concave random variables, which may be of independent interest. [ABSTRACT FROM AUTHOR]

The classical problem of supervised learning is to infer an accurate estimate of a target variable $Y$ from a measured variable $X$ using a set of labeled training samples. Motivated by the increasingly distributed nature of data and decision making, this paper considers a variation of this classical problem in which the inference is distributed between two nodes, e.g., a mobile device and a cloud, with a rate constraint on the communication between them. The mobile device observes $X$ and sends a description $M$ of $X$ to the cloud, which computes an estimate $\hat {Y}$ of $Y$. We follow the recent minimax learning approach to study this inference problem and show that it corresponds to a one-shot minimax noisy lossy source coding problem. We then establish information theoretic bounds on the risk-rate Lagrangian cost, leading to a general method for designing a near-optimal descriptor-estimator pair. A key ingredient in the proof of our result is a refined version of the strong functional representation lemma previously used to establish several one-shot source coding theorems. Our results show that a naive estimate-compress scheme for rate-constrained inference is not optimal in general. When the distribution of $(X,Y)$ is known and the error is measured by the logarithmic loss, our bounds on the risk-rate Lagrangian cost provide a new one-shot operational interpretation of the information bottleneck. We also demonstrate a way to bound the excess risk of the descriptor-estimator pair obtained by our method. [ABSTRACT FROM AUTHOR]

Suppose that ${ { y}}= \lvert \text {A} { x}_{0}\rvert +\eta $ where ${ x}_{0}\in {\mathbb R} ^{{d}}$ is the target signal and $\eta \in {\mathbb R}^{{m}}$ is a noise vector. The aim of phase retrieval is to estimate ${x}_{0}$ from ${ { y}}$. A popular model for estimating ${ x}_{0}$ is the nonlinear least squares ${\widehat { {x}}}:={\mathrm{ argmin}}_{ x} \| \lvert \text {A} { x}\rvert - { { y}}\|_{2}$. One has already developed many efficient algorithms for solving the model, such as the seminal error reduction algorithm. In this paper, we present the estimation performance of the model with proving that $\| {\widehat { {x}}}- { x}_{0}\|\lesssim {\|\eta \|_{2}}/{\sqrt {{m}}}$ under the assumption of A being a Gaussian random matrix. We also prove the reconstruction error ${\|\eta \|_{2}}/{\sqrt {{m}}}$ is sharp. For the case where ${ x}_{0}$ is sparse, we study the estimation performance of both the nonlinear Lasso of phase retrieval and its unconstrained version. Our results are non-asymptotic, and we do not assume any distribution on the noise $\eta $. To the best of our knowledge, our results represent the first theoretical guarantee for the nonlinear least squares and for the nonlinear Lasso of phase retrieval. [ABSTRACT FROM AUTHOR]

This paper provides upper and lower bounds on the optimal guessing moments of a random variable taking values on a finite set when side information may be available. These moments quantify the number of guesses required for correctly identifying the unknown object and, similarly to Arikan’s bounds, they are expressed in terms of the Arimoto-Rényi conditional entropy. Although Arikan’s bounds are asymptotically tight, the improvement of the bounds in this paper is significant in the non-asymptotic regime. Relationships between moments of the optimal guessing function and the MAP error probability are also established, characterizing the exact locus of their attainable values. The bounds on optimal guessing moments serve to improve non-asymptotic bounds on the cumulant generating function of the codeword lengths for fixed-to-variable optimal lossless source coding without prefix constraints. Non-asymptotic bounds on the reliability function of discrete memoryless sources are derived as well. Relying on these techniques, lower bounds on the cumulant generating function of the codeword lengths are derived, by means of the smooth Rényi entropy, for source codes that allow decoding errors. [ABSTRACT FROM PUBLISHER]

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]

This paper considers the problem of estimating a high-dimensional vector of parameters \theta \in \mathbb R^n from a noisy observation. The noise vector is independent identically distributed Gaussian with known variance. For a squared-error loss function, the James–Stein (JS) estimator is known to dominate the simple maximum-likelihood (ML) estimator when the dimension n exceeds two. The JS-estimator shrinks the observed vector toward the origin, and the risk reduction over the ML-estimator is greatest for {\theta } that lie close to the origin. JS-estimators can be generalized to shrink the data toward any target subspace. Such estimators also dominate the ML-estimator, but the risk reduction is significant only when {\theta } lies close to the subspace. This leads to the question: in the absence of prior information about \theta , how do we design estimators that give significant risk reduction over the ML-estimator for a wide range of \theta ? In this paper, we propose shrinkage estimators that attempt to infer the structure of \theta from the observed data in order to construct a good attracting subspace. In particular, the components of the observed vector are separated into clusters, and the elements in each cluster shrunk toward a common attractor. The number of clusters and the attractor for each cluster are determined from the observed vector. We provide concentration results for the squared-error loss and convergence results for the risk of the proposed estimators. The results show that the estimators give significant risk reduction over the ML-estimator for a wide range of \theta , particularly for large $n$ . Simulation results are provided to support the theoretical claims. [ABSTRACT FROM AUTHOR]

Many determinantal inequalities for positive definite block matrices are consequences of general entropy inequalities, specialized to Gaussian distributed vectors with prescribed covariances. In particular, strong subadditivity (SSA) yields \ln \det VAC + \ln \det VBC - \ln \det VABC - \ln \det VC \geq 0 for all $3\times 3$ block matrices V_{ABC} , where subscripts identify principal submatrices. We shall refer to the above-mentioned inequality as SSA of log-det entropy. In this paper, we develop further insights on the properties of the above-mentioned inequality and its applications to classical and quantum information theory. In the first part of this paper, we show how to find known and new necessary and sufficient conditions under which saturation with equality occurs. Subsequently, we discuss the role of the classical transpose channel (also known as Petz recovery map) in this problem and find its action explicitly. We then prove some extensions of the saturation theorem, by finding faithful lower bounds on a log-det conditional mutual information. In the second part, we focus on quantum Gaussian states, whose covariance matrices are not only positive but obey additional constraints due to the uncertainty relation. For Gaussian states, the log-det entropy is equivalent to the Rényi entropy of order 2. We provide a strengthening of log-det SSA for quantum covariance matrices that involves the so-called Gaussian Rényi-2 entanglement of formation, a well-behaved entanglement measure defined via a Gaussian convex roof construction. We then employ this result to define a log-det entropy equivalent of the squashed entanglement measure, which is remarkably shown to coincide with the Gaussian Rényi-2 entanglement of formation. This allows us to establish useful properties of such measure(s), such as monogamy, faithfulness, and additivity on Gaussian states. [ABSTRACT FROM PUBLISHER]

This paper investigates the asymptotic expansion for the maximum rate of fixed-length codes over a parallel Gaussian channel with feedback under the following setting: a peak power constraint is imposed on every transmitted codeword, and the average error probabilities of decoding the transmitted message are non-vanishing as the blocklength increases. The main contribution of this paper is a self-contained proof of an upper bound on the first- and second-order asymptotics of the parallel Gaussian channel with feedback. The proof techniques involve developing an information spectrum bound followed by using Curtiss’ theorem to show that a sum of dependent random variables associated with the information spectrum bound converges in distribution to a sum of independent random variables, thus facilitating the use of the usual central limit theorem. Combined with existing achievability results, our result implies that the presence of feedback does not improve the first- and second-order asymptotics. [ABSTRACT FROM PUBLISHER]

We consider the recursive estimation of the probability density function of continuous random variables from a strongly mixing random sample. We revisit here earlier research on this subject by considering a more general class of recursive estimators, including the usual ones. We derive the quadratic mean error of the considered class of estimators. Moreover, we establish a central limit theorem by using Lindeberg’s method resulting in a simplification of the existing assumptions on the sequence of smooth parameters and the mixing coefficient. This is the main contribution of this paper. Finally, the feasibility of the proposed estimator is illustrated throughout an empirical study. [ABSTRACT FROM AUTHOR]

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]

In the distributed function computation problem, dichotomy theorems, initiated by Han-Kobayashi, seek to classify functions by whether the rate regions for function computation improve on the Slepian-Wolf regions or not. In this paper, we develop a general approach to derive converse bounds on the distributed function computation problem. By using this approach, we recover the sufficiency part, i.e. the conditions such that the Slepian-Wolf regions become optimal, of the known dichotomy theorems in the two-terminal distributed computing. Furthermore, we derive an improved sufficient condition on the dichotomy theorem in the multiterminal distributed computing for the class of i.i.d. sources with the positivity condition. Finally, we derive the matching sufficient and necessary condition on the dichotomy theorem in the multiterminal distributed computing for the class of smooth sources. [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]

Phase retrieval refers to algorithmic methods for recovering a signal from its phaseless measurements. There has been recent interest in understanding the performance of local search algorithms that work directly on the non-convex formulation of the problem. Due to the non-convexity of the problem, the success of these local search algorithms depends heavily on their starting points. The most widely used initialization scheme is the spectral method, in which the leading eigenvector of a data-dependent matrix is used as a starting point. Recently, the performance of the spectral initialization was characterized accurately for measurement matrices with independent and identically distributed entries. This paper aims to obtain the same level of knowledge for isotropically random column-orthogonal matrices, which are substantially better models for practical phase retrieval systems. Towards this goal, we consider the asymptotic setting in which the number of measurements $m$ , and the dimension of the signal, $n$ , diverge to infinity with $m/n = \delta \in (1,\infty)$ , and obtain a simple expression for the overlap between the spectral estimator and the true signal vector. [ABSTRACT FROM AUTHOR]

This paper studies convergence of empirical measures smoothed by a Gaussian kernel. Specifically, consider approximating $P\ast \mathcal {N}_\sigma $ , for $\mathcal {N}_\sigma \triangleq \mathcal {N}(0,\sigma ^{2} \mathrm {I}_{d})$ , by $\hat {P}_{n}\ast \mathcal {N}_\sigma $ under different statistical distances, where $\hat {P}_{n}$ is the empirical measure. We examine the convergence in terms of the Wasserstein distance, total variation (TV), Kullback-Leibler (KL) divergence, and $\chi ^{2}$ -divergence. We show that the approximation error under the TV distance and 1-Wasserstein distance ($\mathsf {W}_{1}$) converges at the rate $e^{O(d)} n^{-1/2}$ in remarkable contrast to a (typical) $n^{-\frac {1}{d}}$ rate for unsmoothed $\mathsf {W}_{1}$ (and $d\ge 3$). Similarly, for the KL divergence, squared 2-Wasserstein distance ($\mathsf {W}_{2}^{2}$), and $\chi ^{2}$ -divergence, the convergence rate is $e^{O(d)} n^{-1}$ , but only if $P$ achieves finite input-output $\chi ^{2}$ mutual information across the additive white Gaussian noise (AWGN) channel. If the latter condition is not met, the rate changes to $\omega \left ({n^{-1}}\right)$ for the KL divergence and $\mathsf {W}_{2}^{2}$ , while the $\chi ^{2}$ -divergence becomes infinite – a curious dichotomy. As an application we consider estimating the differential entropy $h(S+Z)$ , where $S\sim P$ and $Z\sim \mathcal {N}_\sigma $ are independent $d$ -dimensional random variables. The distribution $P$ is unknown and belongs to some nonparametric class, but n independently and identically distributed (i.i.d) samples from it are available. Despite the regularizing effect of noise, we first show that any good estimator (within an additive gap) for this problem must have a sample complexity that is exponential in d. We then leverage the above empirical approximation results to show that the absolute-error risk of the plug-in estimator converges as $e^{O(d)} n^{-1/2}$ , thus attaining the parametric rate in n. This establishes the plug-in estimator as minimax rate-optimal for the considered problem, with sharp dependence of the convergence rate both in n and d. We provide numerical results comparing the performance of the plug-in estimator to that of general-purpose (unstructured) differential entropy estimators (based on kernel density estimation (KDE) or k nearest neighbors (kNN) techniques) applied to samples of $S+Z$. These results reveal a significant empirical superiority of the plug-in to state-of-the-art KDE and kNN methods. As a motivating utilization of the plug-in approach, we estimate information flows in deep neural networks and discuss Tishby’s Information Bottleneck and the compression conjecture, among others. [ABSTRACT FROM AUTHOR]

Recently, two extensions of Wyner’s common information—exact and Rényi common informations—were introduced respectively by Kumar, Li, and El Gamal (KLE), and the present authors. The class of common information problems involves determining the minimum rate of the common input to two independent processors needed to exactly or approximately generate a target joint distribution. For the exact common information problem, exact generation of the target distribution is required, while for Wyner’s and $\alpha $ -Rényi common informations, the relative entropy and Rényi divergence with order $\alpha $ were respectively used to quantify the discrepancy between the synthesized and target distributions. The exact common information is larger than or equal to Wyner’s common information. However, it was hitherto unknown whether the former is strictly larger than the latter for some joint distributions. In this paper, we first establish the equivalence between the exact and $\infty $ -Rényi common informations, and then provide single-letter upper and lower bounds for these two quantities. For doubly symmetric binary sources, we show that the upper and lower bounds coincide, which implies that for such sources, the exact and $\infty $ -Rényi common informations are completely characterized. Interestingly, we observe that for such sources, these two common informations are strictly larger than Wyner’s. This answers an open problem posed by KLE. Furthermore, we extend Wyner’s, $\infty $ -Rényi, and exact common informations to sources with countably infinite or continuous alphabets, including Gaussian sources. [ABSTRACT FROM AUTHOR]

KSG mutual information estimator, which is based on the distances of each sample to its $k$ -th nearest neighbor, is widely used to estimate mutual information between two continuous random variables. Existing work has analyzed the convergence rate of this estimator for random variables whose densities are bounded away from zero in its support. In practice, however, KSG estimator also performs well for a much broader class of distributions, including not only those with bounded support and densities bounded away from zero, but also those with bounded support but densities approaching zero, and those with unbounded support. In this paper, we analyze the convergence rate of the error of KSG estimator for smooth distributions, whose support of density can be both bounded and unbounded. As KSG mutual information estimator can be viewed as an adaptive recombination of KL entropy estimators, in our analysis, we also provide convergence analysis of KL entropy estimator for a broad class of distributions. [ABSTRACT FROM AUTHOR]

So-called improper complex signals have been shown to be beneficial in the single-antenna two-user Gaussian interference channel under the assumptions that all input signals are Gaussian and that we treat interference as noise (TIN). This result has been obtained under a restriction to pure strategies without time-sharing, and it was extended to the case where the rates, but not the transmit powers, may be averaged over several transmit strategies. In this paper, we drop such restrictions and discuss the most general case of coded time-sharing, where both the rates and the powers may be averaged. Since coded time-sharing can in general not be expressed by means of a convex hull of the rate region, we have to account for the possibility of time-sharing already during the optimization of the transmit strategy. By means of a novel channel enhancement argument, we prove a surprising result: proper signals are optimal if coded time-sharing is allowed. In addition to establishing this result, we present an algorithm to compute the corresponding achievable rate region. [ABSTRACT FROM AUTHOR]

The problem of finding a vector $\boldsymbol {x}$ which obeys a set of quadratic equations $| \boldsymbol {a}_{\text {k}}^\top \boldsymbol {x} |^{2}=\text {y}_{\text {k}}$ , $\text {k}=1,\cdots,\text {m}$ , plays an important role in many applications. In this paper we consider the case when both $\boldsymbol {x}$ and $\boldsymbol {a}_{k}$ are real-valued vectors of length n. A new loss function is constructed for this problem, which combines the smooth quadratic loss function with an activation function. Under the Gaussian measurement model, we establish that with high probability the target solution $\boldsymbol {x}$ is the only minimizer (up to a global sign) of the new loss function provided $\text {m}\gtrsim \text {n}$. Moreover, the loss function always has a negative directional curvature around its saddle points. [ABSTRACT FROM AUTHOR]

This paper provides conditions on the observation probability distribution in Bayesian localization and optimal filtering so that the conditional mean estimate satisfies convex stochastic dominance. Convex dominance allows us to compare the unconditional mean square error between two optimal Bayesian state estimators over arbitrary time horizons instead of using brute force Monte-Carlo computations. The proof uses two key ideas from microeconomics, namely, integral precision dominance and aggregation of single crossing. The convex dominance result is then used to give sufficient conditions so that the optimal policy of a controlled sensing two-state partially observed Markov decision process (POMDP) is lower bounded by a myopic policy. Numerical examples are presented where the Shannon capacity of the observation distribution using one sensor dominates that of another, and convex dominance holds but Blackwell dominance does not hold. These illustrate the usefulness of the main result in localization, filtering and controlled sensing applications. [ABSTRACT FROM AUTHOR]

Genomic evolution can be viewed as string-editing processes driven by mutations. An understanding of the statistical properties resulting from these mutation processes is of value in a variety of tasks related to biological sequence data, e.g., estimation of model parameters and compression. At the same time, due to the complexity of these processes, designing tractable stochastic models and analyzing them are challenging. In this paper, we study two kinds of systems, each representing a set of mutations. In the first system, tandem duplications and substitution mutations are allowed and in the other, interspersed duplications. We provide stochastic models and, via stochastic approximation, study the evolution of substring frequencies for these two systems separately. Specifically, we show that $k$ -mer frequencies converge almost surely and determine the limit set. Furthermore, we present a method for finding upper bounds on entropy for such systems. [ABSTRACT FROM AUTHOR]

In this paper, we study tail inequalities of the largest eigenvalue of a matrix infinitely divisible (i.d.) series, which is a finite sum of fixed matrices weighted by i.d. random variables. We obtain several types of tail inequalities, including Bennett-type and Bernstein-type inequalities. This allows us to further bound the expectation of the spectral norm of a matrix i.d. series. Moreover, by developing a new lower-bound function for $Q(s)=(s+1)\log (s+1)-s$ that appears in the Bennett-type inequality, we derive a tighter tail inequality of the largest eigenvalue of the matrix i.d. series than the Bernstein-type inequality when the matrix dimension is high. The resulting lower-bound function is of independent interest and can improve any Bennett-type concentration inequality that involves the function $Q(s)$. The class of i.d. probability distributions is large and includes Gaussian and Poisson distributions, among many others. Therefore, our results encompass the existing work on matrix Gaussian series as a special case. Lastly, we show that the tail inequalities of a matrix i.d. series have applications in several optimization problems including the chance constrained optimization problem and the quadratic optimization problem with orthogonality constraints. In addition, we also use the resulting tail bounds to show that random matrices constructed from i.d. random variables satisfy the restricted isometry property (RIP) when it acts as a measurement matrix in compressed sensing. [ABSTRACT FROM AUTHOR]

It is well known that superposition coding, namely separately encoding the independent sources, is optimal for symmetric multilevel diversity coding (SMDC) (Yeung-Zhang 1999) for any $L\geq 2$ , where $L$ is the number of levels of the coding system. However, the characterization of the coding rate region therein involves uncountably many linear inequalities and the constant term (i.e., the lower bound) in each inequality is given in terms of the solution of a linear optimization problem. Thus this implicit characterization of the coding rate region does not enable the determination of the achievability of a given rate tuple. In principle, the achievability of a given rate tuple can be determined by direct computation, but the complexity is prohibitive even for $L=5$. In this paper, for any fixed $L$ , we obtain in closed form a finite set of linear inequalities for characterizing the coding rate region. We further show by the symmetry of the problem that only a much smaller subset of this finite set of inequalities needs to be verified in determining the achievability of a given rate tuple. Yet, the cardinality of this smaller set grows at least exponentially fast with $L$. We also present a subset entropy inequality, which together with our explicit characterization of the coding rate region, is sufficient for proving the optimality of superposition coding. [ABSTRACT FROM AUTHOR]

Typically, real-world stochastic processes are not easy to analyze. In this paper, we study the representation of different stochastic process as a memoryless innovation process triggering a dynamic system. We show that such a representation is always feasible for innovation processes taking values over a continuous set. However, the problem becomes more challenging when the alphabet size of the innovation is finite. In this case, we introduce both lossless and lossy frameworks, and provide closed-form solutions and practical algorithmic methods. In addition, we discuss the properties and uniqueness of our suggested approach. Finally, we show that the innovation representation problem has many applications. We focus our attention on entropic causal inference, which has recently demonstrated promising performance, compared to alternative methods. [ABSTRACT FROM AUTHOR]

In this paper, we study the arbitrarily varying broadcast channel (AVBC) when the state information is available at the transmitter in a causal manner. We establish the inner and outer bounds on both the random code capacity region and the deterministic code capacity region with degraded message sets. The capacity region is then determined for a class of channels satisfying a condition on the mutual information between the strategy variables and the channel outputs. As an example, we consider the arbitrarily varying binary symmetric broadcast channel. We show the cases where the condition holds and, hence, the capacity region is determined and other cases where there is a gap between the bounds. This gap shows that the minimax theorem does not hold for rate regions. [ABSTRACT FROM AUTHOR]

Lossless variable-length source coding with codeword cost is considered for general sources. The problem setting, where we impose on unequal costs on code symbols, is called the variable-length coding with codeword cost. In this problem, the infimum of average codeword cost have already been determined for general sources. On the other hand, the overflow probability, which is defined as the probability of codeword cost being above a threshold, have not been considered yet. In this paper, we first determine the infimum of achievable threshold in the first-order sense and the second-order sense for general sources with additive memoryless codeword cost. Then, we compute it for some special sources such as i.i.d. sources and mixed sources. A generalization of the codeword cost is also discussed. [ABSTRACT FROM AUTHOR]

The entropy accumulation theorem states that the smooth min-entropy of an $n$ -partite system $A = (A_{1}, \ldots, A_{n})$ is lower-bounded by the sum of the von Neumann entropies of suitably chosen conditional states up to corrections that are sublinear in $n$. This theorem is particularly suited to proving the security of quantum cryptographic protocols, and in particular so-called device-independent protocols for randomness expansion and key distribution, where the devices can be built and preprogrammed by a malicious supplier. However, while the bounds provided by this theorem are optimal in the first order, the second-order term is bounded more crudely, in such a way that the bounds deteriorate significantly when the theorem is applied directly to protocols where parameter estimation is done by sampling a small fraction of the positions, as is done in most QKD protocols. The objective of this paper is to improve this second-order sublinear term and remedy this problem. On the way, we prove various bounds on the divergence variance, which might be of independent interest. [ABSTRACT FROM AUTHOR]

An additive white Gaussian noise energy-harvesting channel with an infinite-sized battery is considered. The energy arrival process is modeled as a sequence of independent and identically distributed random variables. The channel capacity $\frac {1}{2}\log (1+P)$ is achievable by the so-called best-effort and save-and-transmit schemes where $P$ denotes the battery recharge rate. This paper analyzes the save-and-transmit scheme whose transmit power is strictly less than $P$ and the best-effort scheme as a special case of save-and-transmit without a saving phase. In the finite blocklength regime, we obtain new non-asymptotic achievable rates for these schemes that approach the capacity with gaps vanishing at rates proportional to $1/\sqrt {n}$ and $({(\log n)/n})^{1/2}$ respectively where $n$ denotes the blocklength. The proof technique involves analyzing the escape probability of a Markov process. When $P$ is sufficiently large, we show that allowing the transmit power to back off from $P$ can improve the performance for save-and-transmit. The results are extended to a block energy arrival model where the length of each energy block $L$ grows sublinearly in $n$. We show that the save-and-transmit and best-effort schemes achieve coding rates that approach the capacity with gaps vanishing at rates proportional to $\sqrt {L/n}$ and $({\max \{\log n, L\}/n})^{1/2}$ , respectively. [ABSTRACT FROM AUTHOR]

In successive refinement of information, the decoder refines its representation of the source progressively as it receives more encoded bits. The rate-distortion region of successive refinement describes the minimum rates required to attain the target distortions at each decoding stage. In this paper, we derive a parametric characterization of the rate-distortion region for successive refinement of abstract sources. Our characterization extends Csiszár’s result to successive refinement, and generalizes a result by Tuncel and Rose, applicable for finite alphabet sources, to abstract sources. This characterization spawns a family of outer bounds to the rate-distortion region. It also enables an iterative algorithm for computing the rate-distortion region, which generalizes Blahut’s algorithm to successive refinement. Finally, it leads a new nonasymptotic converse bound. In all the scenarios where the dispersion is known, this bound is second-order optimal. In our proof technique, we avoid Karush–Kuhn–Tucker conditions of optimality, and we use basic tools of probability theory. We leverage the Donsker–Varadhan lemma for the minimization of relative entropy on abstract probability spaces. [ABSTRACT FROM AUTHOR]

In this paper, we consider a new normalization of matrices obtained by choosing distinct codewords at random from linear codes over finite fields and find that under some natural algebraic conditions of the codes their empirical spectral distribution converges to Wigner’s semicircle law as the length of the codes goes to infinity. One such condition is that the dual distance of the codes is at least five. This is analogous to previous work on the empirical spectral distribution of similar matrices obtained in this fashion that converges to the Marchenko–Pastur law. [ABSTRACT FROM AUTHOR]

In 1959, Rényi proposed the information dimension and the $d$ -dimensional entropy to measure the information content of general random variables. This paper proposes a generalization of information dimension to stochastic processes by defining the information dimension rate as the entropy rate of the uniformly quantized stochastic process divided by minus the logarithm of the quantizer step size $1/m$ in the limit as $m\to \infty $. It is demonstrated that the information dimension rate coincides with the rate-distortion dimension, defined as twice the rate-distortion function $R(D)$ of the stochastic process divided by $-\log (D)$ in the limit as $D\downarrow 0$. It is further shown that among all multivariate stationary processes with a given (matrix-valued) spectral distribution function (SDF), the Gaussian process has the largest information dimension rate and the information dimension rate of multivariate stationary Gaussian processes is given by the average rank of the derivative of the SDF. The presented results reveal that the fundamental limits of almost zero-distortion recovery via compressible signal pursuit and almost lossless analog compression are different in general. [ABSTRACT FROM AUTHOR]

The Gauss–Markov source produces $U_{i} = aU_{i-1} + Z_{i}$ for $i\geq 1$ , where $U_{0} = 0$ , $|a|< 1$ and $Z_{i}\sim \mathcal {N}(0, \sigma ^{2})$ are i.i.d. Gaussian random variables. We consider lossy compression of a block of $n$ samples of the Gauss–Markov source under squared error distortion. We obtain the Gaussian approximation for the Gauss–Markov source with excess-distortion criterion for any distortion $d>0$ , and we show that the dispersion has a reverse waterfilling representation. This is the first finite blocklength result for lossy compression of sources with memory. We prove that the finite blocklength rate-distortion function $R(n,d,\epsilon)$ approaches the rate-distortion function $\mathbb {R}(d)$ as $R(n,d,\epsilon) = \mathbb {R}(d) + \sqrt {\frac {V(d)}{n}}Q^{-1}(\epsilon) + o\left ({\frac {1}{\sqrt {n}}}\right)$ , where $V(d)$ is the dispersion, $\epsilon \in (0,1)$ is the excess-distortion probability, and $Q^{-1}$ is the inverse $Q$ -function. We give a reverse waterfilling integral representation for the dispersion $V(d)$ , which parallels that of the rate-distortion functions for Gaussian processes. Remarkably, for all $0 < d\leq \frac {\sigma ^{2}}{(1+|a|)^{2}}$ , $R(n,d,\epsilon)$ of the Gauss–Markov source coincides with that of $Z_{i}$ , the i.i.d. Gaussian noise driving the process, up to the second-order term. Among novel technical tools developed in this paper is a sharp approximation of the eigenvalues of the covariance matrix of $n$ samples of the Gauss–Markov source, and a construction of a typical set using the maximum likelihood estimate of the parameter $a$ based on $n$ observations. [ABSTRACT FROM AUTHOR]

In this paper, we establish a new bound tying together the effective length and the maximum correlation between the outputs of an arbitrary pair of Boolean functions which operate on two sequences of correlated random variables. We derive a new upper bound on the correlation between the outputs of these functions. The upper bound may find applications in problems in many areas which deal with common information. We build upon Witsenhausen’s result on maximum correlation. The present upper bound takes into account the effective length of the Boolean functions in characterizing the correlation. We use the new bound to characterize the communication-cooperation tradeoff in multi-terminal communications. We investigate binary block-codes (BBC). A BBC is defined as a vector of Boolean functions. We consider an ensemble of BBCs which is randomly generated using single-letter distributions. We characterize the vector of dependency spectrums of these BBCs. We use this vector to bound the correlation between the outputs of two distributed BBCs. Finally, the upper bound is used to show that the large blocklength single-letter coding schemes studied in the literature are sub-optimal in various multi-terminal communication settings. [ABSTRACT FROM AUTHOR]

This paper establishes the exact exponents for the soft-covering phenomenon of a memoryless channel under the total variation metric when random (i.i.d. and constant-composition) channel codes are used. The exponents, established herein, are strict improvements in both directions on bounds found in the literature. This complements the recent literature establishing the exact exponents under the relative entropy metric; however, the proof techniques have significant differences, and thus, neither result trivially implies the other. The found exponents imply new and improved bounds for various problems that use soft-covering as their achievability argument, including new lower bounds for the resolvability exponent and the secrecy exponent in the wiretap channel. [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]

An open problem in polarization theory is to determine the binary operations that always lead to polarization (in the general multilevel sense) when they are used in Arıkan style constructions. This paper, which is presented in two parts, solves this problem by providing a necessary and sufficient condition for a binary operation to be polarizing. This (first) part of this paper introduces the mathematical framework that we will use in the second part to characterize the polarizing operations. We define uniformity preserving, irreducible, ergodic, and strongly ergodic operations, and we study their properties. The concepts of a stable partition and the residue of a stable partition are introduced. We show that an ergodic operation is strongly ergodic if and only if all its stable partitions are their own residues. We also study the products of binary operations and the structure of their stable partitions. We show that the product of a sequence of binary operations is strongly ergodic if and only if all the operations in the sequence are strongly ergodic. In the second part of this paper, we provide a foundation of polarization theory based on the ergodic theory of binary operations that we develop in this part. [ABSTRACT FROM PUBLISHER]

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]

In this paper, we analyze the tradeoff between coding rate and asymptotic performance of a class of generalized low-density parity-check (GLDPC) codes constructed by including a certain fraction of generalized constraint (GC) nodes in the graph. The rate of the GLDPC ensemble is bounded using classical results on linear block codes, namely, Hamming bound and Varshamov bound. We also study the impact of the decoding method used at GC nodes. To incorporate both bounded-distance (BD) and maximum likelihood (ML) decoding at GC nodes into our analysis without resorting on multi-edge type of degree distributions (DDs), we propose the probabilistic peeling decoding (P-PD) algorithm, which models the decoding step at every GC node as an instance of a Bernoulli random variable with a successful decoding probability that depends on both the GC block code and its decoding algorithm. The P-PD asymptotic performance over the BEC can be efficiently predicted using standard techniques for LDPC codes such as density evolution (DE) or the differential equation method. Furthermore, for a class of GLDPC ensembles, we demonstrate that the simulated P-PD performance accurately predicts the actual performance of the GLPDC code under ML decoding at GC nodes. We illustrate our analysis for GLDPC code ensembles with regular and irregular DDs. In all cases, we show that a large fraction of GC nodes is required to reduce the original gap to capacity, but the optimal fraction is strictly smaller than one. We then consider techniques to further reduce the gap to capacity by means of random puncturing, and the inclusion of a certain fraction of generalized variable nodes in the graph. [ABSTRACT FROM AUTHOR]

A user wants to retrieve a file from a database without revealing the identity of the file retrieved to the operator of the database (server), which is known as the problem of private information retrieval (PIR). If it is further required that the user obtains no information about the other files in the database, the concept of symmetric PIR (SPIR) is introduced to guarantee privacy for both parties. For SPIR, the server(s) need to access some randomness independent of the database, to protect the content of undesired files from the user. The information-theoretic capacity of SPIR is defined as the maximum number of information bits of the desired file retrieved per downloaded bit. In this paper, the problem of SPIR is studied for a distributed storage system with $N$ servers (nodes), where all data (including the files and the randomness) are stored in a distributed way. Specifically, the files are stored by an $(N,K_{C})$ -MDS storage code. The randomness is distributedly stored such that any $K_{C}$ servers store independent randomness information. We consider two scenarios regarding to the ability of the storage nodes to cooperate. In the first scenario considered, the storage nodes do not communicate or collude. It is shown that the SPIR capacity for MDS-coded storage (hence called MDS-SPIR) is $1-\frac {K_{C}}{N}$ , when the amount of the total randomness of distributed nodes (unavailable at the user) is at least $\frac {K_{C}}{N - K_{\vphantom {R_{l}}C}}$ times the file size. Otherwise, the MDS-SPIR capacity equals zero. The second scenario considered is the $T$ -colluding SPIR problem (hence called TSPIR). Specifically, any $T$ out of $N$ servers may collude, that is, they may communicate their interactions with the user to guess the identity of the requested file. In the special case with $K_{C}=1$ , i.e., the database is replicated at each node, the capacity of TSPIR is shown to be $1-\frac {T}{N}$ , with the ratio of the total randomness size relative to the file size be at least $\frac {T}{\vphantom {R_{l}}N - T}$. For TSPIR with MDS-coded storage (called MDS-TSPIR for short), when restricted to schemes with additive randomness where the servers add the randomness to the answers regardless of the queries received, the capacity is proved to equal $1-\frac {K_{C} + T - 1}{N}$ , with total randomness at least $\frac {K_{C} + T - 1}{N - K_{\vphantom {R_{l}}C} - T + 1}$ times the file size. The MDS-TSPIR capacity for general schemes remains an open problem. [ABSTRACT FROM AUTHOR]

Hypergraphical sources are a natural class of sources for secret key generation, within which different subsets of terminals sharing secrets are allowed to discuss publicly in order to agree upon a global secret key. While their secrecy capacity, i.e., the maximum rate of a secret key that can be agreed upon by the entire set of terminals, is well-understood, what remains open is the maximum rate of a secret key that can be generated when there is a restriction on the overall rate of public discussion allowed. In this paper, we obtain a family of explicitly computable upper bounds on the number of bits of secret key that can be generated per bit of public discussion. These upper bounds are derived using a lamination technique based on the submodularity of the entropy function. In particular, a specific instance of these upper bounds, called the edge-partition bound, is shown to be tight for the pairwise independent network model, a special case of the hypergraphical source when the hypergraph is a graph. The secret key generation scheme achieving this upper bound is the tree-packing protocol of Nitinawarat et al., thereby resolving in the affirmative the discussion rate optimality of the tree-packing protocol. [ABSTRACT FROM AUTHOR]

The minimal set of Shannon-type inequalities (or elemental inequalities) plays a central role in efficiently determining whether a given inequality is in fact Shannon-type or not and in computing the linear programming bound for network coding capacity. In many cases, random variables under consideration are subject to additional constraints, such as functional dependence and conditional independence constraints. For example, functional dependence constraints are common in many communication problems due to deterministic encoding and decoding constraints. In other situations, the variables involved may form a Markov chain or in general a Markov random field, leading to conditional independence constraint. Subject to additional constraints, the challenge is how to identify the non-redundant inequalities. While one can always numerically determine the non-redundant inequalities (subject to additional linear equality constraints), it will be instrumental and also important if the non-redundant inequalities can be listed explicitly. In this paper, we show that this is achievable under the functional dependence and full conditional independence constraints. [ABSTRACT FROM AUTHOR]

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]

New capacity upper bounds are presented for the discrete-time Poisson channel with no dark current and an average-power constraint. These bounds are a consequence of techniques developed for the seemingly unrelated problem of upper bounding the capacity of binary deletion and repetition channels. Previously, the best known capacity upper bound in the regime where the average-power constraint does not approach zero was due to Martinez (JOSA B, 2007), which is re-derived as a special case of the framework developed in this paper. Furthermore, this framework is carefully instantiated in order to obtain a closed-form bound that improves the result of Martinez everywhere. Finally, capacity-achieving distributions for the discrete-time Poisson channel are studied under an average-power constraint and/or a peak-power constraint and arbitrary dark current. In particular, it is shown that the support of the capacity-achieving distribution under an average-power constraint must only be countably infinite. This settles a conjecture of Shamai (IEE Proceedings I, 1990) in the affirmative. Previously, it was only known that the support must be an unbounded set. [ABSTRACT FROM AUTHOR]

In this paper, we consider a binary erasure channel (BEC) with an unknown erasure probability of ${\delta }$ at a transmitter. In addition, we consider that ${\delta }$ has a constant value in each transmission block and the transmitter knows the probability distribution of ${\delta }$. For this problem with the infinite block length, based on the distribution of the random variable ${\delta }$ , a multi-layer encoding strategy at the transmitter and a successive decoding strategy at the receiver are proposed. In our proposed scheme, based on the value of ${\delta }$ , the receiver can decode a part of transmitted data from different transmission layers. In order to have a comparison with other erasure correction codes, we generalize the result of the infinite block length to the finite block-length transmission. We show that considering the average transmission rate, our scheme has a better performance than the other erasure correction codes such as the Raptor and the MDS codes. We also analyze both the decoding complexity and bit error rate versus the erasure probability of the channel. Besides, by using a numerical comparison, we try to show that our proposed strategy outperforms other transmission strategies. [ABSTRACT FROM AUTHOR]

The random variable simulation problem consists in using a $\boldsymbol {k}$ -dimensional i.i.d. random vector $\boldsymbol {X}^{\boldsymbol {k}}$ with distribution $\boldsymbol {P}_{\boldsymbol {X}}^{\boldsymbol {k}}$ to simulate an $\boldsymbol {n}$ -dimensional i.i.d. random vector $\boldsymbol {Y}^{\boldsymbol {n}}$ so that its distribution is approximately $\boldsymbol {Q}_{\boldsymbol {Y}}^{\boldsymbol {n}}$. In contrast to previous works, in this paper, we consider the standard Rényi divergence and two variants of all orders to measure the level of approximation. These two variants are the max-Rényi divergence $\boldsymbol {D}_{\boldsymbol {\alpha }}^{\mathsf {max}}(\boldsymbol {P},\boldsymbol {Q})$ and the sum-Rényi divergence $\boldsymbol {D}_{\boldsymbol {\alpha }}^{+}(\boldsymbol {P},\boldsymbol {Q})$. When $\boldsymbol {\alpha }=\infty $ , these two measures are strong because for any $\boldsymbol {\epsilon }\ge 0$ , $\boldsymbol {D}_{\infty }^{\mathsf {max}}(\boldsymbol {P},\boldsymbol {Q})\leq \boldsymbol {\epsilon }$ or $\boldsymbol {D}_{\infty }^{+}(\boldsymbol {P},\boldsymbol {Q})\leq \boldsymbol {\epsilon }$ implies $\boldsymbol {e}^{-\boldsymbol {\epsilon }}\leq ({\boldsymbol {P}(\boldsymbol {x})}/{\boldsymbol {Q}(\boldsymbol {x})})\leq \boldsymbol {e}^{\boldsymbol {\epsilon }}$ for all $\boldsymbol {x}$. Under these Rényi divergence measures, we characterize the asymptotics of normalized divergences as well as the Rényi conversion rates. The latter is defined as the supremum of ${\boldsymbol {n}}/{\boldsymbol {k}}$ such that the Rényi divergences vanish asymptotically. Our results show that, when the Rényi parameter is in the interval $(\textbf {0},\textbf {1})$ , the Rényi conversion rates equal the ratio of the Shannon entropies ${\boldsymbol {H}\left ({\boldsymbol {P}_{\boldsymbol {X}}}\right)}/{\boldsymbol {H}\left ({\boldsymbol {Q}_{\boldsymbol {Y}}}\right)}$ , which is consistent with traditional results in which the total variation measure was adopted. When the Rényi parameter is in the interval $(\textbf {1},\infty)$ , the Rényi conversion rates are, in general, smaller than ${\boldsymbol {H}\left ({\boldsymbol {P}_{\boldsymbol {X}}}\right)}/{\boldsymbol {H}\left ({\boldsymbol {Q}_{\boldsymbol {Y}}}\right)}$. When specialized to the case in which either $\boldsymbol {P}_{\boldsymbol {X}}$ or $\boldsymbol {Q}_{\boldsymbol {Y}}$ is uniform, the simulation problem reduces to the source resolvability and intrinsic randomness problems. The preceding results are used to characterize the asymptotics of Rényi divergences and the Rényi conversion rates for these two cases. [ABSTRACT FROM AUTHOR]