Search

In contrast to their seemingly simple and shared structure of independence and stationarity, Lévy processes exhibit a wide variety of behaviors, from the self-similar Wiener process to piecewise-constant compound Poisson processes. Inspired by the recent paper of Ghourchian, Amini, and Gohari, we characterize their compressibility by studying the entropy of their double discretization (both in time and amplitude) in the regime of vanishing discretization steps. For a Lévy process with absolutely continuous marginals, this reduces to understanding the asymptotics of the differential entropy of its marginals at small times, for which we obtain a new local central limit theorem. We generalize known results for stable processes to the non-stable case, with a special focus on Lévy processes that are locally self-similar, and conceptualize a new compressibility hierarchy of Lévy processes, captured by their Blumenthal–Getoor index. [ABSTRACT FROM AUTHOR]

The mutual information (MI) of Gaussian multi-input multi-output (MIMO) channels has been evaluated by utilizing random matrix theory (RMT) and shown to asymptotically follow Gaussian distribution, where the ergodic mutual information (EMI) converges to a deterministic quantity. However, with non-Gaussian channels, there is a bias between the EMI and its deterministic equivalent (DE), whose evaluation is not available in the literature. This bias of the EMI is related to the bias for the trace of the resolvent in large RMT. In this paper, we first derive the bias for the trace of the resolvent, which is further extended to compute the bias for the linear spectral statistics (LSS). Then, we apply the above results on non-Gaussian MIMO channels to determine the bias for the EMI. It is also proved that the bias for the EMI is −0.5 times of that for the variance of the MI. Finally, the derived bias is utilized to modify the central limit theory (CLT) and calculate the outage probability. Numerical results show that the modified CLT significantly outperforms previous methods in approximating the distribution of the MI and improves the accuracy for the outage probability evaluation. [ABSTRACT FROM AUTHOR]

Parties connected to independent sources through a network can generate correlations among themselves. Notably, the space of feasible correlations for a given network, depends on the physical nature of the sources and the measurements performed by the parties. In particular, quantum sources give access to nonlocal correlations that cannot be generated classically. In this paper, we derive a universal limit on correlations in networks in terms of their covariance matrix. We show that in a network satisfying a certain condition, the covariance matrix of any feasible correlation can be decomposed as a summation of positive semidefinite matrices each of whose terms corresponds to a source in the network. Our result is universal in the sense that it holds in any physical theory of correlation in networks, including the classical, quantum and all generalized probabilistic theories. [ABSTRACT FROM AUTHOR]

Distributed Arithmetic Coding (DAC) is a practical realization of Slepian-Wolf coding that partitions source space into cosets. Coset Cardinality Spectrum (CCS) is an important property of DAC that was defined in our previous work. In this paper, we give two applications of CCS. First, we find that DAC bitstream is not compact. The rate loss of DAC bitstream is caused by two factors: unequal coset partitioning and bit indivisibility. It is proved that as code length goes to infinity, the expected value of bit-indivisibility rate loss will tend to 0.5 for any irrational Rate Change Step (RCS), where the RCS refers to the rate change when one source bit is flipped. With the help of CCS, the bit-indivisibility rate loss can be compensated to some extend. Especially, for any irrational RCS, as code length goes to infinity, the expected value of the remaining bit-indivisibility rate loss after compensation will tend to about 0.47. The second application of CCS is DAC decoder design. We derive the formula of path metric and find that in the original paper on DAC, the intuitive formula of path metric is not correct. The backward-replacing algorithm is proposed to make full use of memory. Experimental results confirm the correctness of theoretical analyses. [ABSTRACT FROM AUTHOR]

The paper deals with linear information inequalities valid for entropy functions induced by discrete random variables. Specifically, the so-called conditional Ingleton inequalities are in the center of interest: these are valid under conditional independence assumptions on the inducing random variables. We discuss five inequalities of this particular type, four of which has appeared earlier in the literature. Besides the proof of the new fifth inequality, simpler proofs of (some of) former inequalities are presented. These five information inequalities are used to characterize all conditional independence structures induced by four discrete random variables. [ABSTRACT FROM AUTHOR]

The Schnorr-Stimm dichotomy theorem (Schnorr and Stimm, 1972) concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet $\Sigma $. The theorem asserts that, for any such sequence $S$ , the following two things are true. (1) If $S$ is not normal in the sense of Borel (meaning that every two strings of equal length appear with equal asymptotic frequency in $S$), then there is a finite-state gambler that wins money at an infinitely-often exponential rate betting on $S$. (2) If $S$ is normal, then any finite-state gambler loses money at an exponential rate betting on $S$. In this paper we use the Kullback-Leibler divergence to formulate the lower asymptotic divergence ${\mathrm {div}}(S||\alpha)$ of a probability measure $\alpha $ on $\Sigma $ from a sequence $S$ over $\Sigma $ and the upper asymptotic divergence ${\mathrm {Div}}(S||\alpha)$ of $\alpha $ from $S$ in such a way that a sequence $S$ is $\alpha $ -normal (meaning that every string $w$ has asymptotic frequency $\alpha (w)$ in $S$) if and only if ${\mathrm {Div}}(S||\alpha)=0$. We also use the Kullback-Leibler divergence to quantify the total risk ${\mathrm {Risk}}_{G}(w)$ that a finite-state gambler $G$ takes when betting along a prefix $w$ of $S$. Our main theorem is a strong dichotomy theorem that uses the above notions to quantify the exponential rates of winning and losing on the two sides of the Schnorr-Stimm dichotomy theorem (with the latter routinely extended from normality to $\alpha $ -normality). Modulo asymptotic caveats in the paper, our strong dichotomy theorem says that the following two things hold for prefixes $w$ of $S$. ($1~'$) The infinitely-often exponential rate of winning in 1 is $2^{{\mathrm {Div}}(S||\alpha)|w|}$. ($2~'$) The exponential rate of loss in 2 is $2^{- {\mathrm {Risk}}_{G}(w)}$. We also use (1 $'$) to show that $1- {\mathrm {Div}}(S||\alpha)/c$ , where $c= \log (1/ \min _{a\in \Sigma }\alpha (a))$ , is an upper bound on the finite-state $\alpha $ -dimension of $S$ and prove the dual fact that $1- {\mathrm {div}}(S||\alpha)/c$ is an upper bound on the finite-state strong $\alpha $ -dimension of $S$. [ABSTRACT FROM AUTHOR]

This paper studies large scatter matrix estimation for heavy tailed distributions. The contributions of this paper are twofold. First, we propose and advocate to use a new distribution family, the pair-elliptical, for modeling the high dimensional data. The pair-elliptical is more flexible and easier to check the goodness of fit compared to the elliptical. Secondly, built on the pair-elliptical family, we advocate using quantile-based statistics for estimating the scatter matrix. For this, we provide a family of quantile-based statistics. They outperform the existing ones for better balancing the efficiency and robustness. In particular, we show that the propose estimators have comparable performance to the moment-based counterparts under the Gaussian assumption. The method is also tuning-free compared to Catoni’s M-estimator for covariance matrix estimation. We further apply the method to conduct a variety of statistical methods. The corresponding theoretical properties as well as numerical performances are provided. [ABSTRACT FROM AUTHOR]

The entropy power inequality (EPI) and the Brascamp-Lieb inequality (BLI) are fundamental inequalities concerning the differential entropies of linear transformations of random vectors. The EPI provides lower bounds for the differential entropy of linear transformations of random vectors with independent components. The BLI, on the other hand, provides upper bounds on the differential entropy of a random vector in terms of the differential entropies of some of its linear transformations. In this paper, we define a family of entropy functionals, which we show are subadditive. We then establish that Gaussians are extremal for these functionals by adapting a proof technique from Geng and Nair (2014). As a consequence, we obtain a new entropy inequality that generalizes both the BLI and EPI. By considering a variety of independence relations among the components of the random vectors appearing in these functionals, we also obtain families of inequalities that lie between the EPI and the BLI. [ABSTRACT FROM AUTHOR]

Let $\mathrm {W}\in \mathbb {C}^{n\times n}$ be a single-spiked Wishart matrix in the class $\mathrm {W}\sim \mathcal {CW}_{n}(m,\mathrm {I}_{n}+ \theta \mathrm {v}\mathrm {v}^{\dagger}) $ with $m\geq n$ , where ${\mathrm {I}}_{n}$ is the $n\times n$ identity matrix, $\mathrm {v}\in \mathbb {C}^{n\times 1}$ is an arbitrary vector with unit Euclidean norm, $\theta \geq 0$ is a non-random parameter, and $(\cdot)^{\dagger} $ represents the conjugate-transpose operator. Let u1 and ${\mathrm {u}}_{n}$ denote the eigenvectors corresponding to the smallest and the largest eigenvalues of W, respectively. This paper investigates the probability density function (p.d.f.) of the random quantity $Z_{\ell }^{(n)}=\left |{\mathrm {v}^{\dagger} \mathrm {u}_\ell }\right |^{2}\in (0,1)$ for $\ell =1,n$. In particular, we derive a finite dimensional closed-form p.d.f. for $Z_{1}^{(n)}$ which is amenable to asymptotic analysis as $m,n$ diverges with $m-n$ fixed. It turns out that, in this asymptotic regime, the scaled random variable $nZ_{1}^{(n)}$ converges in distribution to $\chi ^{2}_{2}/2(1+\theta)$ , where $\chi _{2}^{2}$ denotes a chi-squared random variable with two degrees of freedom. This reveals that u1 can be used to infer information about the spike. On the other hand, the finite dimensional p.d.f. of $Z_{n}^{(n)}$ is expressed as a double integral in which the integrand contains a determinant of a square matrix of dimension $(n-2)$. Although a simple solution to this double integral seems intractable, for special configurations of $n=2,3$ , and 4, we obtain closed-form expressions. [ABSTRACT FROM AUTHOR]

All-or-nothing transforms (AONTs) were proposed by Rivest as a message preprocessing technique for encrypting data to protect against brute-force attacks, and have numerous applications in cryptography and information security. Later the unconditionally secure AONTs and their combinatorial characterization were introduced by Stinson. Informally, a combinatorial AONT is an array with the unbiased requirements and its security properties in general depend on the prior probability distribution on the inputs $s$ -tuples. Recently, it was shown by Esfahani and Stinson that a combinatorial AONT has perfect security provided that all the inputs $s$ -tuples are equiprobable, and has weak security provided that all the inputs $s$ -tuples are with non-zero probability. This paper aims to explore on the gap between perfect security and weak security for combinatorial $(t,s,v)$ -AONTs. Concretely, we consider the typical scenario that all the $s$ inputs take values independently (but not necessarily identically) and quantify the amount of information $H(\mathcal {X}|\mathcal {Y})$ about any $t$ inputs $\mathcal {X}$ that is not revealed by any $s-t$ outputs $\mathcal {Y}$. In particular, we establish the general lower and upper bounds on $H(\mathcal {X}|\mathcal {Y})$ for combinatorial AONTs using information-theoretic techniques, and also show that the derived bounds can be attained in certain cases. Furthermore, the discussions are extended for the security properties of combinatorial asymmetric AONTs. [ABSTRACT FROM AUTHOR]

Let $q\geq 2$ be a prime power. In this paper, we study the distribution of the minimum distance (in the Hamming metric) of a random linear code of dimension $k$ in $\mathbb {F}_{q}^{n}$. We provide quantitative estimates showing that the distribution function of the minimum distance is close (superpolynomially in $n$) to the cumulative distribution function of the minimum of $(q^{k}-1)/(q-1)$ independent binomial random variables with parameters $\frac {1}{q}$ and $n$. The latter, in turn, converges to a Gumbel distribution at integer points when $\frac {k}{n}$ converges to a fixed number in (0, 1). Our result confirms in a strong sense that apart from identification of the weights of proportional codewords, the probabilistic dependencies introduced by the linear structure of the random code, produce a negligible effect on the minimum code weight. As a corollary of the main result, we obtain an improvement of the Gilbert–Varshamov bound for $2< q< 49$. [ABSTRACT FROM AUTHOR]

We investigate a privacy-signaling game problem in which a sender with privacy concerns observes a pair of correlated random vectors which are modeled as jointly Gaussian. The sender aims to hide one of these random vectors and convey the other one whereas the objective of the receiver is to accurately estimate both of the random vectors. We analyze these conflicting objectives in a game theoretic framework with quadratic costs where depending on the commitment conditions (of the sender), we consider Nash or Stackelberg (Bayesian persuasion) equilibria. We show that a payoff dominant Nash equilibrium among all admissible policies is attained by a set of explicitly characterized linear policies. We also show that a payoff dominant Nash equilibrium coincides with a Stackelberg equilibrium. We formulate the information bottleneck problem within our Stackelberg framework under the mean squared error distortion criterion where the information bottleneck setup has a further restriction that only one of the random variables is observed at the sender. We show that this MMSE Gaussian Information Bottleneck Problem admits a linear solution which is explicitly characterized in the paper. We provide explicit conditions on when the optimal solutions, or equilibrium solutions in the Nash setup, are informative or noninformative. [ABSTRACT FROM AUTHOR]

The notion of compressibility of a random measure is a rather general concept which find applications in many contexts from data compression, to signal quantization, and parameter estimation. While compressibility for discrete and continuous measures is generally well understood, the case of discrete-continuous measures is quite subtle. In this paper, we focus on a class of multi-dimensional random measures that have singularities on affine lower-dimensional subsets. We refer to this class of random variables as affinely singular. Affinely singular random vectors naturally arises when considering linear transformation of component-wise independent discrete-continuous random variables. To measure the compressibility of such distributions, we introduce the new notion of dimensional-rate bias (DRB) which is closely related to the entropy and differential entropy in discrete and continuous cases, respectively. Similar to entropy and differential entropy, DRB is useful in evaluating the mutual information between distributions of the aforementioned type. Besides the DRB, we also evaluate the the RID of these distributions. We further provide an upper-bound for the RID of multi-dimensional random measures that are obtained by Lipschitz functions of component-wise independent discrete-continuous random variables (X). The upper-bound is shown to be achievable when the Lipschitz function is $A \mathrm {X}$ , where $A$ satisfies ${\mathrm{ SPARK}}({A_{m\times n}}) = m+1$ (e.g., Vandermonde matrices). When considering discrete-domain moving-average processes with non-Gaussian excitation noise, the above results allow us to evaluate the block-average RID and DRB, as well as to determine a relationship between these parameters and other existing compressibility measures. [ABSTRACT FROM AUTHOR]

This paper studies the problem of recovering the hidden vertex correspondence between two edge-correlated random graphs. We focus on the Gaussian model where the two graphs are complete graphs with correlated Gaussian weights and the Erdős-Rényi model where the two graphs are subsampled from a common parent Erdős-Rényi graph ${\mathcal {G}}(n,p)$. For dense Erdős-Rényi graphs with $p=n^{-o(1)}$ , we prove that there exists a sharp threshold, above which one can correctly match all but a vanishing fraction of vertices and below which correctly matching any positive fraction is impossible, a phenomenon known as the “all-or-nothing” phase transition. Even more strikingly, in the Gaussian setting, above the threshold all vertices can be exactly matched with high probability. In contrast, for sparse Erdős-Rényi graphs with $p=n^{-\Theta (1)}$ , we show that the all-or-nothing phenomenon no longer holds and we determine the thresholds up to a constant factor. Along the way, we also derive the sharp threshold for exact recovery, sharpening the existing results in Erdős-Rényi graphs. The proof of the negative results builds upon a tight characterization of the mutual information based on the truncated second-moment computation and an “area theorem” that relates the mutual information to the integral of the reconstruction error. The positive results follows from a tight analysis of the maximum likelihood estimator that takes into account the cycle structure of the induced permutation on the edges. [ABSTRACT FROM AUTHOR]

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

Motivated by the established notion of storage codes, we consider sets of infinite sequences over a finite alphabet such that every $k$ -tuple of consecutive entries is uniquely recoverable from its $l$ -neighborhood in the sequence. We address the problem of finding the maximum growth rate of the set, which we term capacity, as well as constructions of explicit families that approach the optimal rate. The techniques that we employ rely on the connection of this problem with constrained systems. In the second part of the paper we consider a modification of the problem wherein the entries in the sequence are viewed as random variables over a finite alphabet that follow some joint distribution, and the recovery condition requires that the Shannon entropy of the $k$ -tuple conditioned on its $l$ -neighborhood be bounded above by some $\epsilon >0$. We study properties of measures on infinite sequences that maximize the metric entropy under the recoverability condition. Drawing on tools from ergodic theory, we prove some properties of entropy-maximizing measures. We also suggest a procedure of constructing an $\epsilon $ -recoverable measure from a corresponding deterministic system. [ABSTRACT FROM AUTHOR]

This paper investigates the capacity of general multiple-input single-output (MISO) optical intensity channels (OICs) under per-antenna peak- and average-intensity constraints. We first consider the MISO equal-cost constrained OIC (EC-OIC), where, apart from the peak-intensity constraint, average intensities of inputs are equal to arbitrarily preassigned constants. The second model of our interest is the MISO bounded-cost constrained OIC (BC-OIC), where, as compared with the EC-OIC, average intensities of inputs are no larger than arbitrarily preassigned constants. By leveraging tools from quantile functions, stop-loss transform and convex ordering of nonnegative random variables, we prove two decomposition theorems for bounded and nonnegative random variables, based on which we equivalently transform both the EC-OIC and the BC-OIC into respective single-input single-output channels under a peak-intensity and several stop-loss mean constraints. Capacity lower and upper bounds for both channels are established, based on which the asymptotic capacity at high and low signal-to-noise-ratio are determined. [ABSTRACT FROM AUTHOR]

In 1994, Jim Massey proposed the guessing entropy as a measure of the difficulty that an attacker has to guess a secret used in a cryptographic system, and established a well-known inequality between entropy and guessing entropy. Over 15 years before, in an unpublished work, he also established a well-known inequality for the entropy of an integer-valued random variable of given variance. In this paper, we establish a link between the two works by Massey in the more general framework of the relationship between discrete (absolute) entropy and continuous (differential) entropy. Two approaches are given in which the discrete entropy (or Rényi entropy) of an integer-valued variable can be upper bounded using the differential (Rényi) entropy of some suitably chosen continuous random variable. As an application, lower bounds on guessing entropy and guessing moments are derived in terms of entropy or Rényi entropy (without side information) and conditional entropy or Arimoto conditional entropy (when side information is available). [ABSTRACT FROM AUTHOR]

We investigate the equilibrium behavior for the decentralized cheap talk problem for real random variables and quadratic cost criteria in which an encoder and a decoder have misaligned objective functions. In prior work, it has been shown that the number of bins in any equilibrium has to be countable, generalizing a classical result due to Crawford and Sobel who considered sources with density supported on [0, 1]. In this paper, we first refine this result in the context of log-concave sources. For sources with two-sided unbounded support, we prove that, for any finite number of bins, there exists a unique equilibrium. In contrast, for sources with semi-unbounded support, there may be a finite upper bound on the number of bins in equilibrium depending on certain conditions stated explicitly. Moreover, we prove that for log-concave sources, the expected costs of the encoder and the decoder in equilibrium decrease as the number of bins increases. Furthermore, for strictly log-concave sources with two-sided unbounded support, we prove convergence to the unique equilibrium under best response dynamics which starts with a given number of bins, making a connection with the classical theory of optimal quantization and convergence results of Lloyd’s method. In addition, we consider more general sources which satisfy certain assumptions on the tail(s) of the distribution and we show that there exist equilibria with infinitely many bins for sources with two-sided unbounded support. Further explicit characterizations are provided for sources with exponential, Gaussian, and compactly-supported probability distributions. [ABSTRACT FROM AUTHOR]

A general class of Bayesian lower bounds when the underlying loss function is a Bregman divergence is demonstrated. This class can be considered as an extension of the Weinstein–Weiss family of bounds for the mean squared error and relies on finding a variational characterization of Bayesian risk. This approach allows for the derivation of a version of the Cramér–Rao bound that is specific to a given Bregman divergence. This new generalization of the Cramér–Rao bound reduces to the classical one when the loss function is taken to be the Euclidean norm. In order to evaluate the effectiveness of the new lower bounds, the paper also develops upper bounds on Bayesian risk, which are based on optimal linear estimators. The effectiveness of the new bound is evaluated in the Poisson noise setting. [ABSTRACT FROM AUTHOR]

In contrast to time series, graphical data is data indexed by the vertices and edges of a graph. Modern applications such as the internet, social networks, genomics and proteomics generate graphical data, often at large scale. The large scale argues for the need to compress such data for storage and subsequent processing. Since this data might have several components available in different locations, it is also important to study distributed compression of graphical data. In this paper, we derive a rate region for this problem which is a counterpart of the Slepian–Wolf theorem. We characterize the rate region when the statistical description of the distributed graphical data can be modeled as being one of two types – as a member of a sequence of marked sparse Erdős–Rényi ensembles or as a member of a sequence of marked configuration model ensembles. Our results are in terms of a generalization of the notion of entropy introduced by Bordenave and Caputo in the study of local weak limits of sparse graphs. Furthermore, we give a generalization of this result for Erdős–Rényi and configuration model ensembles with more than two sources. [ABSTRACT FROM AUTHOR]

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

This paper employs auxiliary receivers as a mathematical tool to identify Gallager-type auxiliary random variables and write outer bounds for some basic multiuser settings. This approach is then applied to the relay, interference, and broadcast channel settings, yielding new outer bounds that improve on existing outer bounds and strictly outperform classical outer bounds. For instance, we strictly improve on: the cutset outer bound for the scalar Gaussian relay channel, the outer bounds for the Gaussian Z-interference channel, and the outer bounds for the two receiver broadcast channel. [ABSTRACT FROM AUTHOR]

For a continuous-time additive white Gaussian noise (AWGN) channel with possible feedback, it has been shown that as sampling gets infinitesimally fine, the mutual information of the associative discrete-time channels converges to that of the original continuous-time channel. We give in this paper more quantitative strengthenings of this result, which, among other implications, characterize how over-sampling approaches the true mutual information of a continuous-time Gaussian channel with bandwidth limit. The assumptions in our results are relatively mild. In particular, for the non-feedback case, compared to the Shannon-Nyquist sampling theorem, a widely used tool to connect continuous-time Gaussian channels to their discrete-time counterparts that requires the band-limitedness of the channel input, our results only require some integrability conditions on the power spectral density function of the input. [ABSTRACT FROM AUTHOR]

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

In this paper, we study an information-theoretic secret sharing problem, where a dealer distributes shares of a secret among a set of participants under the following constraints: (i) authorized sets of users can recover the secret by pooling their shares, and (ii) non-authorized sets of colluding users cannot learn any information about the secret. We assume that the dealer and participants observe the realizations of correlated Gaussian random variables and that the dealer can communicate with participants through a one-way, authenticated, rate-limited, and public channel. Unlike traditional secret sharing protocols, in our setting, no perfectly secure channel is needed between the dealer and the participants. Our main result is a closed-form characterization of the fundamental trade-off between secret rate and public communication rate. [ABSTRACT FROM AUTHOR]

Blowfish privacy is a recent generalisation of differential privacy that enables improved utility while maintaining privacy policies with semantic guarantees, a factor that has driven the popularity of differential privacy in computer science. This paper relates Blowfish privacy to an important measure of privacy loss of information channels from the communications theory community: min-entropy leakage. Symmetry in an input data neighbouring relation is central to known connections between differential privacy and min-entropy leakage. But while differential privacy exhibits strong symmetry, Blowfish neighbouring relations correspond to arbitrary simple graphs owing to the framework’s flexible privacy policies. To bound the min-entropy leakage of Blowfish-private mechanisms we organise our analysis over symmetrical partitions corresponding to orbits of graph automorphism groups. A construction meeting our bound with asymptotic equality demonstrates tightness. [ABSTRACT FROM AUTHOR]

What is the minimum number of guesses needed on average to guess a realization of a random variable correctly? The answer to this question led to the introduction of a quantity called guesswork by Massey in 1994, which can be viewed as an alternate security criterion to entropy. In this paper, we consider the guesswork in the presence of quantum side information, and show that a general sequential guessing strategy is equivalent to performing a single quantum measurement and choosing a guessing strategy based on the outcome. We use this result to deduce entropic one-shot and asymptotic bounds on the guesswork in the presence of quantum side information, and to formulate a semi-definite program (SDP) to calculate the quantity. We evaluate the guesswork for a simple example involving the BB84 states, both numerically and analytically, and we prove a continuity result that certifies the security of slightly imperfect key states when the guesswork is used as the security criterion. [ABSTRACT FROM AUTHOR]

Consider a channel $W$ along with a given input distribution $P_{X}$. In certain settings, such as in the construction of polar codes, the output alphabet of $W$ is ‘too large’, and hence we replace $W$ by a channel $Q$ having a smaller output alphabet. We say that $Q$ is upgraded with respect to $W$ if $W$ is obtained from $Q$ by processing its output. In this case, the mutual information $I(P_{X},W)$ between the input and output of $W$ is upper-bounded by the mutual information $I(P_{X},Q)$ between the input and output of $Q$. In this paper, we present an algorithm that produces an upgraded channel $Q$ from $W$ , as a function of $P_{X}$ and the required output alphabet size of $Q$ , denoted $L$. We show that the difference in mutual informations is ‘small’. Namely, it is $O(L^{-2/(| \mathcal {X}|-1)})$ , where $| \mathcal {X}|$ is the size of the input alphabet. This power law of $L$ is optimal. We complement our analysis with numerical experiments which show that the developed algorithm improves upon the existing state-of-the-art algorithms also in non-asymptotic setups. [ABSTRACT FROM AUTHOR]

In this paper, we consider a recently-proposed model of teaching and learning under uncertainty, in which a teacher receives independent observations of a single bit corrupted by binary symmetric noise, and sequentially transmits to a student through another binary symmetric channel based on the bits observed so far. After a given number $n$ of transmissions, the student outputs an estimate of the unknown bit, and we are interested in the exponential decay rate of the error probability as $n$ increases. We propose a novel block-structured teaching strategy in which the teacher encodes the number of 1s received in each block, and show that the resulting error exponent is the binary relative entropy $D\left({\frac {1}{2}\|\max (p,q)}\right)$ , where $p$ and $q$ are the noise parameters. This matches a trivial converse result based on the data processing inequality, and settles two conjectures of [Jog and Loh, 2021] and [Huleihel et al., 2019]. In addition, we show that the computation time required by the teacher and student is linear in $n$. We also study a more general setting in which the binary symmetric channels are replaced by general binary-input discrete memoryless channels. We provide an achievability bound and a converse bound, and show that the two coincide in certain cases, including (i) when the two channels are identical, and (ii) when the student-teacher channel is a binary symmetric channel. More generally, we give sufficient conditions under which our learning rate is the best possible for block-structured protocols. [ABSTRACT FROM AUTHOR]

Many clustering problems can be solved using semidefinite programming. Theoretical results in this vein frequently consider data with a planted clustering and a notion of signal strength such that the semidefinite program exactly recovers the planted clustering when the signal strength is sufficiently large. In practice, semidefinite programs are notoriously slow, and so speedups are welcome. In this paper, we show how to sketch a popular semidefinite relaxation of a graph clustering problem known as minimum bisection, and our analysis supports a meta-claim that the clustering task is less computationally burdensome when there is more signal. [ABSTRACT FROM AUTHOR]

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

This paper studies an information-theoretic one-shot variable-length secret key agreement problem with public discussion. Let X and Y be jointly distributed random variables, each taking values in some measurable space. Alice and Bob observe X and Y respectively, can communicate interactively through a public noiseless channel, and want to agree on a key length and a key that is approximately uniformly distributed over all bit sequences with the agreed key length. The public discussion is observed by an eavesdropper, Eve. The key should be approximately independent of the public discussion, conditional on the key length. We show that the optimal expected key length is close to the mutual information I(X;Y) within a logarithmic gap. Moreover, an upper bound and a lower bound on the optimal expected key length can be written down in terms of I(X;Y) only. This means that the optimal one-shot performance is always within a small gap of the optimal asymptotic performance regardless of the distribution of the pair (X,Y). This one-shot result may find applications in situations where the components of an i.i.d. pair source (Xn,Yn) are observed sequentially and the key is output bit by bit, or in situations where the random source is not an i.i.d. or ergodic process. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of secret key generation with one-way communication through both a rate-limited public channel and a rate-limited secure channels where the public channel is from Alice to Bob and Eve and the secure channel is from Alice to Bob. In this model, we do not pose any constraints on the sources, i.e. Bob is not degraded to or less noisy than Eve. We obtain the optimal secret key rate in this problem, both for the discrete memoryless sources and vector Gaussian sources. The vector Gaussian characterization is derived by suitably applying the enhancement argument, and proving a new extremal inequality. The extremal inequality can be seen as coupling of two extremal inequalities, which are related to the degraded compound MIMO Gaussian broadcast channel, and the vector generalization of Costa’s entropy power inequality, accordingly. [ABSTRACT FROM AUTHOR]

We show that the most common flavors of noisy leakage can be simulated in the information-theoretic setting using a single query of bounded leakage, up to a small statistical simulation error and a slight loss in the leakage parameter. The latter holds true in particular for one of the most used noisy-leakage models, where the noisiness is measured using the conditional average min-entropy (Naor and Segev, CRYPTO’09 and SICOMP’12). Our reductions between noisy and bounded leakage are achieved in two steps. First, we put forward a new leakage model (dubbed the dense leakage model) and prove that dense leakage can be simulated in the information-theoretic setting using a single query of bounded leakage, up to small statistical distance. Second, we show that the most common noisy-leakage models fall within the class of dense leakage, with good parameters. Third, we prove lower bounds on the amount of bounded leakage required for simulation with sub-constant error, showing that our reductions are nearly optimal. In particular, our results imply that useful general simulation of noisy leakage based on statistical distance and mutual information is impossible. We also provide a complete picture of the relationships between different noisy-leakage models. Our result finds applications to leakage-resilient cryptography, where we are often able to lift security in the presence of bounded leakage to security in the presence of noisy leakage, both in the information-theoretic and in the computational setting. Remarkably, this lifting procedure makes only black-box use of the underlying schemes. Additionally, we show how to use lower bounds in communication complexity to prove that bounded-collusion protocols (Kumar, Meka, and Sahai, FOCS’19) for certain functions do not only require long transcripts, but also necessarily need to reveal enough information about the inputs. [ABSTRACT FROM AUTHOR]

We establish the undecidability of conditional affine information inequalities, the undecidability of the conditional independence implication problem with a constraint that one random variable is binary, and the undecidability of the problem of deciding whether the intersection of the entropic region and a given affine subspace is empty. This is a step towards the conjecture on the undecidability of conditional independence implication. The undecidability is proved via a reduction from the periodic tiling problem (a variant of the domino problem). Hence, one can construct examples of the aforementioned problems that are independent of ZFC (assuming ZFC is consistent). [ABSTRACT FROM AUTHOR]

We study the problem of simulating a two-user multiple-access channel (MAC) over a multiple access network of noiseless links. Two encoders observe independent and identically distributed (i.i.d.) copies of a source random variable each, while a decoder observes i.i.d. copies of a side-information random variable. There are rate-limited noiseless communication links between each encoder and the decoder, and there is independent pairwise shared randomness between all the three possible pairs of nodes. The decoder has to output approximately i.i.d. copies of another random variable jointly distributed with the two sources and the side information. We are interested in the rate tuples which permit this simulation. This setting can be thought of as a multi-terminal generalization of the point-to-point channel simulation problem studied by Bennett et al. (2002) and Cuff (2013). When the pairwise shared randomness between the encoders is absent, the setting reduces to a special case of MAC simulation using another MAC studied by Haddadpour et al. (2013). We establish that the presence of encoder shared randomness can strictly improve the communication rate requirements. We first show that the inner bound derived from Haddadpour et al. (2013) is tight when the sources at the encoders are conditionally independent given the side-information at the decoder. This result recovers the existing results on point-to-point channel simulation and function computation over such multi-terminal networks. We then explicitly compute the communication rate regions for an example both with and without the encoder shared randomness and demonstrate that its presence strictly reduces the communication rates. Inner and outer bounds for the general case are also obtained. [ABSTRACT FROM AUTHOR]

We consider a distributed function computation problem in which parties observing noisy versions of a remote source facilitate the computation of a function of their observations at a fusion center through public communication. The distributed function computation is subject to constraints, including not only reliability and storage but also secrecy and privacy. Specifically, 1) the function computed should remain secret from an eavesdropper observing the public communication and correlated observations, measured in terms of the information leaked about the arguments of the function, to ensure secrecy regardless of the exact function used; 2) the remote source should remain private from the eavesdropper and the fusion center, measured in terms of the information leaked about the remote source itself. We derive the exact rate regions for lossless and lossy single-function computation and illustrate the lossy single-function computation rate region for an information bottleneck example, in which the optimal auxiliary random variables are characterized for binary-input symmetric-output channels. We extend the approach to lossless and lossy asynchronous multiple-function computations with joint secrecy and privacy constraints, in which case inner and outer bounds for the rate regions that differ only in the Markov chain conditions imposed are characterized. [ABSTRACT FROM AUTHOR]

Many known networks have structure of affiliation networks, where each of $n$ network nodes (actors) selects an attribute set from a given collection of $m$ attributes, and two nodes (actors) establish adjacency relation whenever they share a common attribute. We study the behavior of a random walk on such networks. For this purpose, we use a common model of such networks, a random intersection graph. We establish the cover time of the simple random walk on the binomial random intersection graph ${\mathcal{ G}}(n,m,p)$ at the connectivity threshold and above it. We consider the range of $(n,m,p)$ , where the typical attribute is shared by a (stochastically) bounded number of actors. [ABSTRACT FROM AUTHOR]

A fundamental challenge in learning is the presence of nonlinear redundancies and dependencies in the data. To address this, we propose a Fourier-based approach to characterize feature redundancies, in unsupervised learning, and feature-label dependencies, in the supervised variant of the problem. We first develop a novel Fourier expansion for functions (more generally stochastic mappings) of correlated binary random variables. This is a generalization of the standard Fourier expansion on the Boolean cube beyond product probability spaces. As an important application of this analysis, we investigate learning with feature subset selection. In the unsupervised variant of this problem, we characterize feature redundancies via the Shannon entropy and group the features into sufficiently informative and redundant. Then, we make a connection to the proposed Fourier expansion and derive an upper bound on the joint entropy. Based on that, we propose a measure to quantify feature redundancies and present an unsupervised learning algorithm. We test our method on various real-world and synthetic datasets and demonstrate improvements on conventional unsupervised feature selection techniques. Then, we investigate the supervised feature subset selection and reformulate it in the Fourier domain. Bridging the Bayesian error rate with the Fourier coefficients, we demonstrate that the Fourier expansion provides a powerful tool to characterize nonlinear feature-label dependencies. Further, we introduce a computationally efficient measure for selecting relevant features. Via a theoretical analysis, we show that our proposed measure finds provably asymptotically optimal feature subsets. Lastly, we present an algorithm based on this measure and via numerical experiments demonstrate its improvements on various supervised feature selection algorithms. [ABSTRACT FROM AUTHOR]

We propose a new method to compute the feedback capacity of unifilar finite state channels (FSCs) with memory using reinforcement learning (RL). The feedback capacity was previously estimated using its formulation as a Markov decision process (MDP) with dynamic programming (DP) algorithms. However, their computational complexity grows exponentially with the channel alphabet size. Therefore, we use RL, and specifically, its ability to parameterize value functions and policies with neural networks, to evaluate numerically the feedback capacity of channels with a large alphabet size. The outcome of the RL algorithm is a numerical lower bound on the feedback capacity, which is used to reveal the structure of the optimal solution. The structure is modeled by a graph-based auxiliary random variable that is utilized to derive an analytic upper bound on the feedback capacity with the duality bound. The capacity computation is concluded by verifying the tightness of the upper bound by testing whether it is Bahl-Cocke-Jelinek-Raviv (BCJR) invariant. We demonstrate this method on the Ising channel with an arbitrary alphabet size. For an alphabet size smaller than or equal to 8, we derive the analytic solution of the capacity. Next, the structure of the numerical solution is used to deduce a simple coding scheme that achieves the feedback capacity and serves as a lower bound for larger alphabets. For an alphabet size greater than 8, we present an upper bound on the feedback capacity. For an asymptotically large alphabet size, we present an asymptotic optimal coding scheme. [ABSTRACT FROM AUTHOR]

Graph covers and the Bethe free energy (BFE) have been useful theoretical tools for producing lower bounds on a variety of counting problems in graphical models, including the permanent and the ferromagnetic Ising model. Here, we investigate weighted homomorphism counting problems over bipartite graphs that are related to a conjecture of Sidorenko. We show that the BFE does yield a lower bound in a variety of natural settings, and when it does yield a lower bound, it necessarily improves upon the lower bound conjectured by Sidorenko. Conversely, we show that there exist bipartite graphs for which the BFE does not yield a lower bound on the homomorphism number. Finally, we use the characterizations developed as part of this work to provide a simple proof of Sidorenko’s conjecture in a number of special cases. [ABSTRACT FROM AUTHOR]

We study the problem of simultaneous search for multiple targets over a multidimensional unit cube and derive fundamental resolution limits of non-adaptive querying procedures using the 20 questions estimation framework. The performance criterion that we consider is the achievable resolution, which is defined as the maximal $L_\infty $ norm between the location vector and its estimated version where the maximization is over all target location vectors. The fundamental resolution limit is defined as the minimal achievable resolution of any non-adaptive query procedure, where each query has binary yes/no answers. We drive non-asymptotic and second-order asymptotic bounds on the minimal achievable resolution, using tools from finite blocklength information theory. Specifically, in the achievability part, we relate the 20 questions problem to data transmission over a multiple access channel, use the information spectrum method by Han and borrow results from finite blocklength analysis for random access channel coding. In the converse part, we relate the 20 questions problem to data transmission over a point-to-point channel and adapt finite blocklength converse results for channel coding. Our results extend the purely first-order asymptotic analyses of Kaspi et al. (ISIT 2015) for the one-dimensional case: we consider channels beyond the binary symmetric channel and derive non-asymptotic and second-order asymptotic bounds on the performance of optimal non-adaptive query procedures. [ABSTRACT FROM AUTHOR]

We develop a new upper bound on the capacity of the relay channel that is tighter than previously known upper bounds. This upper bound is proved using traditional weak converse techniques involving mutual information inequalities and Gallager-type explicit identification of auxiliary random variables. We show that the new upper bound is strictly tighter than all previous bounds for the Gaussian relay channel with non-zero channel gains. When specialized to the relay channel with orthogonal receiver components, the bound resolves a conjecture by Kim on a class of deterministic relay channels. When further specialized to the class of product-form relay channels with orthogonal receiver components, the bound resolves a generalized version of Cover’s relay channel problem, recovers the recent upper bound for the Gaussian case by Wu et al., and improves upon the recent bounds for the binary symmetric case by Wu et al. and Barnes et al., which were obtained using non-traditional geometric proof techniques. For the special class of a relay channel with orthogonal receiver components, we develop another upper bound on the capacity which utilizes an auxiliary receiver and show that it is strictly tighter than the bound by Tandon and Ulukus. Finally, we show through the Gaussian relay channel with i.i.d. relay output sequence that the bound with the auxiliary receiver can be strictly tighter than our main bound. [ABSTRACT FROM AUTHOR]

Mean-based reconstruction is a fundamental, natural approach to worst-case trace reconstruction over channels with synchronization errors. It is known that $\exp (\Theta (n^{1/3}))$ traces are necessary and sufficient for mean-based worst-case trace reconstruction over the deletion channel, and this result was also extended to certain channels combining deletions and geometric insertions of uniformly random bits. In this work, we use a simple extension of the original complex-analytic approach to show that these results are examples of a much more general phenomenon. We introduce oblivious synchronization channels, which map each input bit to an arbitrarily distributed sequence of replications and insertions of random bits. This general class captures all previously considered synchronization channels. We show that for any oblivious synchronization channel whose output length follows a sub-exponential distribution either mean-based trace reconstruction is impossible or $\exp (O(n^{1/3}))$ traces suffice for this task. [ABSTRACT FROM AUTHOR]

Aim of this short note is to study Shannon’s entropy power along entropic interpolations, thus generalizing Costa’s concavity theorem. We shall provide two proofs of independent interest: the former by $\Gamma $ -calculus, hence applicable to more abstract frameworks; the latter with an explicit remainder term, reminiscent of Villani (IEEE Trans. Inf. Theory, 2006), allowing us to characterize the case of equality. [ABSTRACT FROM AUTHOR]

We propose an estimator for the singular vectors of high-dimensional low-rank matrices corrupted by additive subgaussian noise, where the noise matrix is allowed to have dependence within rows and heteroskedasticity between them. We prove finite-sample $\ell _{2,\infty }$ bounds and a Berry-Esseen theorem for the individual entries of the estimator, and we apply these results to high-dimensional mixture models. Our Berry-Esseen theorem clearly shows the geometric relationship between the signal matrix, the covariance structure of the noise, and the distribution of the errors in the singular vector estimation task. These results are illustrated in numerical simulations. Unlike previous results of this type, which rely on assumptions of Gaussianity or independence between the entries of the additive noise, handling the dependence between entries in the proofs of these results requires careful leave-one-out analysis and conditioning arguments. Our results depend only on the signal-to-noise ratio, the sample size, and the spectral properties of the signal matrix. [ABSTRACT FROM AUTHOR]

We study an information analogue of infinitely divisible probability distributions, where the i.i.d. sum is replaced by the joint distribution of an i.i.d. sequence. A random variable $X$ is called informationally infinitely divisible if, for any $n\ge 1$ , there exists an i.i.d. sequence of random variables $Z_{1},\ldots,Z_{n}$ that contains the same information as $X$ , i.e., there exists an injective function $f$ such that $X=f(Z_{1},\ldots,Z_{n})$. While there does not exist such informationally infinitely divisible discrete random variable, we show that any discrete random variable $X$ can be divided into arbitrarily many identical pieces with a multiplicative penalty to the entropy, that is, if we remove the injectivity requirement on $f$ , then there exists i.i.d. $Z_{1},\ldots,Z_{n}$ and $f$ satisfying $X=f(Z_{1},\ldots,Z_{n})$ , and the entropy satisfies $H(X)/n\le H(Z_{1})\le 1.59H(X)/n+2.43$ bits. Furthermore, we study the case where $X=(Y_{1},\ldots,Y_{m})$ is itself an i.i.d. sequence, $m\ge 2$ , for which the multiplicative gap 1.59 can be replaced by $1+5\sqrt {(\log m)/m}$. This means that as $m$ increases, $(Y_{1},\ldots,Y_{m})$ becomes closer to being spectral infinitely divisible in a uniform manner. This can be regarded as an information analogue of Kolmogorov’s uniform theorem. Applications of our result include independent component analysis and distributed storage with a secrecy constraint. [ABSTRACT FROM AUTHOR]

We consider the setting of a distributed storage system where a single file is subdivided into smaller fragments of same size which are then replicated with a common replication factor across servers of identical cache size. An incoming file download request is sent to all the servers, and the download is completed whenever the request gathers all the fragments. At each server, we are interested in determining the set of fragments to be stored, and the sequence in which fragments should be accessed, such that the mean file download time for a request is minimized. We model the fragment download time as an exponential random variable independent and identically distributed for all fragments across all servers, and show that the mean file download time can be lower bounded in terms of the expected number of useful servers summed over all distinct fragment downloads. We present deterministic storage schemes that attempt to maximize the number of useful servers. We show that finding the optimal sequence of accessing the fragments is a Markov decision problem, whose complexity grows exponentially with the number of fragments. We propose heuristic algorithms that determine the sequence of access to the fragments which are empirically shown to perform well. [ABSTRACT FROM AUTHOR]

A new approach to $L_{2}$ -consistent estimation of a general density functional using $k$ -nearest neighbor distances is proposed, where the functional under consideration is in the form of the expectation of some function $f$ of the densities at each point. The estimator is designed to be asymptotically unbiased, using the convergence of the normalized volume of a $k$ -nearest neighbor ball to a Gamma distribution in the large-sample limit, and naturally involves the inverse Laplace transform of a scaled version of the function $f$. Some instantiations of the proposed estimator recover existing $k$ -nearest neighbor based estimators of Shannon and Rényi entropies and Kullback–Leibler and Rényi divergences, and discover new consistent estimators for many other functionals such as logarithmic entropies and divergences. The $L_{2}$ -consistency of the proposed estimator is established for a broad class of densities for general functionals, and the convergence rate in mean squared error is established as a function of the sample size for smooth, bounded densities. [ABSTRACT FROM AUTHOR]