Search

Data samples from ${\mathbb{R}}^ {d}$ with a common support of size $k$ are accessed through $m$ random linear projections (measurements) per sample. It is well-known that roughly $k$ measurements from a single sample are sufficient to recover the support. In the multiple sample setting, do $k$ overall measurements still suffice when only $m$ measurements per sample are allowed, with $m < k$ ? We answer this question in the negative by considering a generative model setting with independent samples drawn from a subgaussian prior. We show that $n=\Theta ((k^{2}/ m^{2})\cdot \log k(d- k))$ samples are necessary and sufficient to recover the support exactly. In turn, this shows that when $m < k$ , $k$ overall measurements are insufficient for support recovery; instead we need about $m$ measurements each from $k^{2}/ m^{2}$ samples, and therefore $k^{2}/ m$ overall measurements are necessary. [ABSTRACT FROM AUTHOR]

We consider a two-party distributed hypothesis testing problem for correlated Gaussian random variables. For a d-dimensional random vector X and a scalar random variable Y, where X and Y are jointly Gaussian with an unknown correlation vector ρ, parties P1 and P2 observe independent copies of X and Y, respectively. The parties seek to test if their observations are correlated or not, namely they seek to test if |ρ|2 exceeds τ or is it 0. To that end, they communicate interactively and declare the test output. We show that roughly order d/τ2 bits of communication are sufficient and necessary for resolving the distributed correlation testing problem above. Furthermore, we establish a lower bound of roughly d2/τ2 bits for the communication needed for distributed estimation of ρ, implying that distributed correlation testing requires less communication than distributed estimation. Both our lower bounds for testing and estimation hold for an arbitrary d and interactive communication with shared randomness, while our distributed test requires only one-way communication with shared randomness. For the one-dimensional case, with one-way communication and with probability of one of the error-types fixed, our bounds are more refined in the dependence on the other error-type and are tight even in the constant. [ABSTRACT FROM AUTHOR]

A transmitter observing a sequence of independent and identically distributed random variables seeks to keep a receiver updated about its latest observations. The receiver need not be apprised about each symbol seen by the transmitter, but needs to output a symbol at each time instant $t$. If at time $t$ the receiver outputs the symbol seen by the transmitter at time $U(t)\leq t$ , the age of information at the receiver at time $t$ is $t-U(t)$. We study the design of lossless source codes that enable transmission with minimum average age at the receiver. We show that the asymptotic minimum average age can be attained up to a constant gap by the Shannon codes for a tilted version of the original pmf generating the symbols, which can be computed easily by solving an optimization problem. Furthermore, we exhibit an example with alphabet $\mathcal {X}$ where Shannon codes for the original pmf incur an asymptotic average age of a factor $O(\sqrt {\log | \mathcal {X}|})$ more than that achieved by our codes. Underlying our prescription for optimal codes is a new variational formula for integer moments of random variables, which may be of independent interest. Also, we discuss possible extensions of our formulation to randomized schemes and to the erasure channel, and include a treatment of the related problem of source coding for minimum average queuing delay. [ABSTRACT FROM AUTHOR]

The task of manipulating correlated random variables in a distributed setting has received attention in the fields of both Information Theory and Computer Science. Often shared correlations can be converted, using a little amount of communication, into perfectly shared uniform random variables. Such perfect shared randomness, in turn, enables the solutions of many tasks. Even the reverse conversion of perfectly shared uniform randomness into variables with a desired form of correlation turns out to be insightful and technically useful. In this article, we describe progress-to-date on such problems and lay out pertinent measures, achievability results, limits of performance, and point to new directions. [ABSTRACT FROM AUTHOR]

Two parties observing correlated data seek to exchange their data using interactive communication. How many bits must they communicate? We propose a new interactive protocol for data exchange, which increases the communication size in steps until the task is done. We also derive a lower bound on the minimum number of bits that is based on relating the data exchange problem to the secret key agreement problem. Our single-shot analysis applies to all discrete random variables and yields upper and lower bounds of a similar form. In fact, the bounds are asymptotically tight and lead to a characterization of the optimal rate of communication needed for data exchange for a general source sequence, such as a mixture of independent and identically distributed (IID) random variables as well as the optimal second-order asymptotic term in the length of communication needed for data exchange for IID random variables, when the probability of error is fixed. This gives a precise characterization of the asymptotic reduction in the length of optimal communication due to interaction; in particular, two-sided Slepian–Wolf compression is strictly suboptimal. [ABSTRACT FROM PUBLISHER]

Two parties observing correlated random variables seek to run an interactive communication protocol. How many bits must they exchange to simulate the protocol, namely to produce a view with a joint distribution within a fixed statistical distance of the joint distribution of the input and the transcript of the original protocol? We present an information spectrum approach for this problem whereby the information complexity of the protocol is replaced by its information complexity density. Our single-shot bounds relate the communication complexity of simulating a protocol to tail bounds for information complexity density. As a consequence, we obtain a strong converse and characterize the second-order asymptotic term in communication complexity for independent and identically distributed observation sequences. Furthermore, we obtain a general formula for the rate of communication complexity, which applies to any sequence of observations and protocols. Connections with results from theoretical computer science and implications for the function computation problem are discussed. [ABSTRACT FROM PUBLISHER]

Multiple parties observing correlated data seek to recover each other’s data and attain omniscience. To that end, they communicate interactively over a noiseless broadcast channel - each bit transmitted over this channel is received by all the parties. We give a universal interactive communication protocol, termed the recursive data exchange protocol (RDE), which attains omniscience for any sequence of data observed by the parties and provide an individual sequence guarantee of performance. As a by-product, for observations of length n , we show the universal rate optimality of RDE up to an {\mathcal O}(n^{-1/2}\sqrt {\log n}) term in a generative setting where the data sequence is independent and identically distributed (in time). Furthermore, drawing on the duality between omniscience and secret key agreement due to Csiszár and Narayan, we obtain a universal protocol for generating a multiparty secret key of rate at most {\mathcal O}(n^{-1/2}\sqrt {\log n })$ less than the maximum rate possible. A key feature of RDE is its recursive structure whereby when a subset $A$ of parties recover each-other’s data, the rates appear as if the parties have been executing the protocol in an alternative model where the parties in $A$ are collocated. [ABSTRACT FROM PUBLISHER]

We revisit the problem of secret key agreement using interactive public communication for two parties and propose a new secret key agreement protocol. The protocol attains the secret key capacity for general observations and attains the second-order asymptotic term in the maximum length of a secret key for independent and identically distributed observations. In contrast to the previously suggested secret key agreement protocols, the proposed protocol uses interactive communication. In fact, the standard one-way communication protocol used prior to this paper fails to attain the asymptotic results above. Our converse proofs rely on a recently established upper bound for secret key lengths. Both our lower and upper bounds are derived in a single-shot setup and the asymptotic results are obtained as corollaries. [ABSTRACT FROM PUBLISHER]

The information-theoretic approach to security entails harnessing the correlated randomness available in nature to establish security. It uses tools from information theory and coding and yields provable security, even against an adversary with unbounded computational power. However, the feasibility of this approach in practice depends on the development of efficiently implementable schemes. In this paper, we review a special class of practical schemes for information-theoretic security that are based on 2-universal hash families. Specific cases of secret key agreement and wiretap coding are considered, and general themes are identified. The scheme presented for wiretap coding is modular and can be implemented easily by including an extra preprocessing layer over the existing transmission codes. [ABSTRACT FROM AUTHOR]