Search

We consider the problem of noisy Bayesian active learning where we are given a finite set of functions \mathcal H , a sample space \mathcal X , and a label set \mathcal L . One of the functions in \mathcal H assigns labels to samples in \mathcal X . The goal is to identify the function that generates the labels even though the result of a label query on a sample is corrupted by independent noise. More precisely, the objective is to declare one of the functions in \mathcal H as the true label generating function with high confidence using as a few label queries as possible, by selecting the queries adaptively and in a strategic manner. Previous work in Bayesian active learning considers generalized binary search and its variants for the noisy case, and analyzes the number of queries required by these sampling strategies. In this paper, we show that these schemes are, in general, suboptimal. Instead we propose and analyze an alternative strategy for sample collection. Our sampling strategy is motivated by a connection between Bayesian active learning and active hypothesis testing, and is based on querying the label of a sample, which maximizes the extrinsic Jensen–Shannon divergence at each step. We provide upper and lower bounds on the performance of this sampling strategy, and show that these bounds are better than the previous bounds in the literature. [ABSTRACT FROM PUBLISHER]

Statistical inference and information processing of high-dimensional data often require an efficient and accurate estimation of their second-order statistics. With rapidly changing data, limited processing power and storage at the acquisition devices, it is desirable to extract the covariance structure from a single pass over the data and a small number of stored measurements. In this paper, we explore a quadratic (or rank-one) measurement model which imposes minimal memory requirements and low computational complexity during the sampling process, and is shown to be optimal in preserving various low-dimensional covariance structures. Specifically, four popular structural assumptions of covariance matrices, namely, low rank, Toeplitz low rank, sparsity, jointly rank-one and sparse structure, are investigated, while recovery is achieved via convex relaxation paradigms for the respective structure. The proposed quadratic sampling framework has a variety of potential applications, including streaming data processing, high-frequency wireless communication, phase space tomography and phase retrieval in optics, and noncoherent subspace detection. Our method admits universally accurate covariance estimation in the absence of noise, as soon as the number of measurements exceeds the information theoretic limits. We also demonstrate the robustness of this approach against noise and imperfect structural assumptions. Our analysis is established upon a novel notion called the mixed-norm restricted isometry property (RIP- \ell 2/\ell 1 ), as well as the conventional RIP- \ell 2/\ell 2 for near-isotropic and bounded measurements. In addition, our results improve upon the best-known phase retrieval (including both dense and sparse signals) guarantees using PhaseLift with a significantly simpler approach. [ABSTRACT FROM PUBLISHER]

A novel information theoretic approach is proposed to solve the secret sharing problem, in which a dealer distributes one or multiple secrets among a set of participants in such a manner that for each secret only qualified sets of users can recover this secret by pooling their shares together while nonqualified sets of users obtain no information about the secret even if they pool their shares together. While existing secret sharing systems (implicitly) assume that communications between the dealer and participants are noiseless, this paper takes a more practical assumption that the dealer delivers shares to the participants via a noisy broadcast channel. Thus, in contrast to the existing solutions that are mainly based on number theoretic tools, an information theoretic approach is proposed, which exploits the channel randomness during delivery of shares as additional resources to achieve secret sharing requirements. In this way, secret sharing problems can be reformulated as equivalent secure communication problems via wiretap channel models, and can hence be solved by employing the powerful information theoretic security techniques. This approach is first developed for the classic secret sharing problem, in which only one secret is to be shared. This classic problem is shown to be equivalent to a communication problem over a compound wiretap channel. Thus, the lower and upper bounds on the secrecy capacity of the compound channel provide the corresponding bounds on the secret sharing rate, and the secrecy scheme designed for the compound channel provides the secret sharing schemes. The power of the approach is further demonstrated by a more general layered multisecret sharing problem, which is shown to be equivalent to the degraded broadcast multiple-input multiple-output (MIMO) channel with layered decoding and secrecy constraints. The secrecy capacity region for the degraded MIMO broadcast channel is characterized, which provides the secret sharing capacity region. Furthermore, the secure encoding scheme that achieves the secrecy capacity region provides an information theoretic scheme for sharing the secrets. [ABSTRACT FROM AUTHOR]

This paper discovers fundamental principles of the backoff process that governs the performance of IEEE 802.11. A simplistic principle founded upon regular variation theory is that the backoff time has a truncated Pareto-type tail distribution with an exponent of (\log \gamma \!)/\log m ( \boldsymbol m is the multiplicative factor and \gamma is the collision probability). This reveals that the per-node backoff process is heavy-tailed in the strict sense for \gamma > 1/m^2 , and paves the way for the following unifying result. The state-of-the-art theory on the superposition of the heavy-tailed processes is applied to establish a dichotomy exhibited by the aggregate backoff process, putting emphasis on the importance of time-scales on which we view the backoff processes. While the aggregation on normal time-scales leads to a Poisson process, it is approximated by a new limiting process possessing long-range dependence (LRD) on coarse time-scales. This dichotomy turns out to be instrumental in formulating short-term fairness, extending existing formulas to arbitrary population, and to elucidate the absence of LRD in practical situations. A refined wavelet analysis is conducted to strengthen this argument. [ABSTRACT FROM AUTHOR]

The goal of this paper is to present constructions of high-rate nonbinary write-once memory (WOM) codes for multilevel flash memories. The constructions provided here are all based on the basic idea of mapping high-rate binary codebooks to nonbinary codebooks. The proposed codes maintain the same length and encoding complexity as their underlying binary constituents. We begin by presenting some elementary, yet rate-efficient constructions. Afterward, we consider a high-rate two-write WOM-code defined over an alphabet of size four. In addition, we consider the application of our constructions to the creation of fixed-rate WOM codes. The constructions presented in this paper improve upon the best-known code constructions for certain code lengths. [ABSTRACT FROM AUTHOR]

Hybrid analog–digital coding has been used for several communication scenarios, such as joint source–channel coding of Gaussian sources over Gaussian channels and relay communication over Gaussian networks. In this paper, a generalized hybrid coding technique is proposed for communication over discrete memoryless and Gaussian systems, and its utility is demonstrated via three examples—lossy joint source–channel coding over multiple access channels, channel coding over two-way relay channels, and channel coding over diamond networks. The corresponding coding schemes recover and extend several existing results in the literature. [ABSTRACT FROM AUTHOR]

The Haroutunian exponent arises in the study of channel reliability functions for both block coding with feedback and fixed-delay coding without feedback. For asymmetric channels, such as the $Z$ -channel, the Haroutunian exponent is strictly larger than the sphere-packing exponent. The sphere-packing exponent is believed to be an upper bound for the reliability function in the two aforementioned communication problems, but in attempting to prove this, one gets stuck at the Haroutunian exponent because of entanglements between the channel behavior and the input distribution. In this paper, we present a characteristic of the Haroutunian exponent that differentiates it from the random coding and sphere-packing exponents. We consider the parallel channel, the repeated use of the original discrete memoryless channel independently some $L$ number of times. It is well known that the capacity of the parallel channel is $L$ times the capacity of the original channel, and the random coding and sphere-packing exponents of the $L$ -use parallel channel decompose into $L$ times the exponents of the original channel. The main result of this paper is to show that the (appropriately normalized) Haroutunian exponent of the parallel channel asymptotically decomposes to the sphere-packing exponent of the original channel, as opposed to the Haroutunian exponent of the original channel. This fact is then used to prove two results. First, an upper bound for the reliability function for fixed blocklength coding with delayed feedback is proved. This upper bound converges to the sphere-packing exponent as the delay in the feedback path tends to infinity. Second, the reliability function for fixed delay coding without feedback is shown to be upper bounded by the sphere-packing exponent. [ABSTRACT FROM PUBLISHER]

The sliding window Lempel–Ziv (SWLZ) algorithm that makes use of recurrence times and match lengths has been studied from various perspectives in information theory literature. In this paper, we undertake a finer study of these quantities under two different scenarios: 1) zero entropy sources that are characterized by strong long-term memory and 2) the processes with weak memory as described through various mixing conditions. For zero entropy sources, a general statement on match length is obtained. It is used in the proof of almost sure optimality of fixed shift variant of Lempel–Ziv (FSLZ) and SWLZ algorithms given in literature. Through an example of stationary and ergodic processes generated by an irrational rotation, we establish that for a window of size nw , a compression ratio given by O(\log nw/{{nw}^{a}}) , where $a$ depends on n_{w} \rightarrow \infty , is obtained under the application of FSLZ and SWLZ algorithms. In addition, we give a general expression for the compression ratio for a class of stationary and ergodic processes with zero entropy. Next, we extend the study of Ornstein and Weiss on the asymptotic behavior of the normalized version of recurrence times and establish the large deviation property for a class of mixing processes. In addition, an estimator of entropy based on recurrence times is proposed for which large deviation principle is proved for sources satisfying similar mixing conditions. [ABSTRACT FROM PUBLISHER]

The bidirectional relay channel, in which two users communicate with each other through a relay node, is a simple but fundamental and practical network architecture. In this paper, we consider the block fading bidirectional relay channel with a decode-and-forward relay and propose efficient transmission strategies that exploit the block fading property of the channel. We assume that a direct link between the two users is not present and consider two transmission modes: 1) the multiple-access mode (both users transmit to the relay) and 2) the broadcast mode (the relay transmits to both users). Most existing relaying protocols assume a fixed schedule for using these transmission modes. In contrast, we abandon the restriction of having a fixed and predefined schedule and propose to optimize the selection of the transmission modes and the associated transmission rates based on the instantaneous channel state information (CSI) of the involved links. Thereby, we consider two different types of transmit power constraints: 1) a fixed transmit power for each node and 2) a per-node long-term power constraint. To enable the use of a nonpredefined schedule for transmission mode selection, the relay has to be equipped with two buffers for storage of the information received from both users. We develop new relaying protocols based on adaptive mode selection and provide the corresponding achievable long-term rate regions. In particular, based on the CSI of the involved links, the optimal transmission mode as well as the optimal transmission rates and/or the transmit powers of the nodes are chosen in each time slot to maximize the weighted sum rate of both users. By varying the weights assigned to the users, the boundary surface of the achievable long-term rate region of the proposed protocol can be obtained. In addition, we discuss and address two practical challenges for the implementation of the proposed protocols, namely, the availability of the knowledge of the channel statistics required for the implementation of the optimal protocols, and the increase of the end-to-end delay due to the data buffering. Numerical results confirm the superiority of the proposed buffer-aided protocols compared with existing bidirectional relaying protocols. [ABSTRACT FROM PUBLISHER]

In a series of remarkable papers, Babadi and Tarokh proved the randomness of matrices and product of two matrices arising from binary linear block codes with respect to the empirical spectral distribution, provided that their dual distances are sufficiently large. However, numerical experiments conducted by Babadi and Tarokh revealed that Gold codes, which have a dual distance of 5, also possess such a randomness property. Hence, the interesting question was raised as to whether or not the stringent requirement of large dual distances can be relaxed in the theorems in order to explain the mysterious randomness of Gold sequences. In this paper, we improve the results of Babadi and Tarokh on several fronts and provide an affirmative answer to this question. [ABSTRACT FROM PUBLISHER]

In this paper, a construction of codebooks based on a set of bent functions satisfying certain conditions is introduced. It includes some earlier constructions of codebooks meeting the Levenstein bound as special cases. With this construction, two new families of codebooks achieving the Levenstein bound are obtained. The codebooks constructed in this paper could have a very small alphabet size. [ABSTRACT FROM PUBLISHER]

Low-density parity-check (LDPC) convolutional codes (or spatially coupled codes) were recently shown to approach capacity on the binary erasure channel (BEC) and binary-input memoryless symmetric channels. The mechanism behind this spectacular performance is now called threshold saturation via spatial coupling. This new phenomenon is characterized by the belief-propagation threshold of the spatially coupled ensemble increasing to an intrinsic noise threshold defined by the uncoupled system. In this paper, we present a simple proof of threshold saturation that applies to a wide class of coupled scalar recursions. Our approach is based on constructing potential functions for both the coupled and uncoupled recursions. Our results actually show that the fixed point of the coupled recursion is essentially determined by the minimum of the uncoupled potential function and we refer to this phenomenon as Maxwell saturation. A variety of examples are considered including the density-evolution equations for: irregular LDPC codes on the BEC, irregular low-density generator-matrix codes on the BEC, a class of generalized LDPC codes with BCH component codes, the joint iterative decoding of LDPC codes on intersymbol-interference channels with erasure noise, and the compressed sensing of random vectors with independent identically distributed components. [ABSTRACT FROM PUBLISHER]

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

In this paper, we consider the finite-state multiple access channel (MAC) with partially cooperative encoders and delayed channel state information (CSI). Here, partial cooperation refers to the communication between the encoders via finite-capacity links. The channel states are assumed to be governed by a Markov process. Full CSI is assumed at the receiver, while at the transmitters, only delayed CSI is available. The capacity region of this channel model is derived by first solving the case of the finite-state MAC with a common message. Achievability for the latter case is established using the notion of strategies, however, we show that optimal codes can be constructed directly over the input alphabet. This results in a single codebook construction that is then leveraged to apply simultaneous joint decoding. Simultaneous decoding is crucial here because it circumvents the need to rely on the capacity region’s corner points, a task that becomes increasingly cumbersome with the growth in the number of messages to be sent. The common message result is then used to derive the capacity region for the case with partially cooperating encoders. Next, we apply this general result to the special case of the Gaussian vector MAC with diagonal channel transfer matrices, which is suitable for modeling, e.g., orthogonal frequency division multiplexing-based communication systems. The capacity region of the Gaussian channel is presented in terms of a convex optimization problem that can be solved efficiently using numerical tools. The region is derived by first presenting an outer bound on the general capacity region and then suggesting a specific input distribution that achieves this bound. Finally, numerical results are provided that give valuable insight into the practical implications of optimally using conferencing to maximize the transmission rates. [ABSTRACT FROM AUTHOR]

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

We propose a new coding scheme using only one lattice that achieves the \({1}/{2}~{\rm log(1+ \mathop {\mathrm {\mathsf {SNR}\kern 0pt}}\nolimits )}\) capacity of the additive white Gaussian noise (AWGN) channel with lattice decoding, which is provable for signal-to-noise ratio \( \mathop {\mathrm {\mathsf {SNR}\kern 0pt}}\nolimits >e\) at present. The scheme applies a discrete Gaussian distribution over an AWGN-good lattice, but otherwise does not require a shaping lattice or dither. Thus, it significantly simplifies the default lattice coding scheme of Erez and Zamir which involves a quantization-good lattice as well as an AWGN-good lattice. Using the flatness factor, we show that the error probability of the proposed scheme under minimum mean-square error lattice decoding is almost the same as that of Erez and Zamir, for any rate up to the AWGN channel capacity. We introduce the notion of good constellations, which carry almost the same mutual information as that of continuous Gaussian inputs. We also address the implementation of Gaussian shaping for the proposed lattice Gaussian coding scheme. [ABSTRACT FROM AUTHOR]

New quadratic bent functions in polynomial form are constructed in this paper. The constructions give new Boolean bent, generalized Boolean bent and \(p\) -ary bent functions. Based on \(\boldsymbol {\mathbb {Z}}_{4}\) -valued quadratic forms, a simple method provides several new constructions of generalized Boolean bent functions. From these generalized Boolean bent functions a method is presented to transform them into Boolean bent and semi-bent functions. Moreover, many new \(p\) -ary bent functions can also be obtained by applying similar methods. [ABSTRACT FROM AUTHOR]

Compressed sensing is provided a data-acquisition paradigm for sparse signals. Remarkably, it has been shown that the practical algorithms provide robust recovery from noisy linear measurements acquired at a near optimal sampling rate. In many real-world applications, a signal of interest is typically sparse not in the canonical basis but in a certain transform domain, such as wavelets or the finite difference. The theory of compressed sensing was extended to the analysis sparsity model, but known extensions are limited to the specific choices of sensing matrix and sparsifying transform. In this paper, we propose a unified theory for robust recovery of sparse signals in a general transform domain by convex programming. In particular, our results apply to the general acquisition and sparsity models and show how the number of measurements for recovery depends on properties of measurement and sparsifying transforms. Moreover, we also provide extensions of our results to the scenarios where the atoms in the transform have varying incoherence parameters and the unknown signal exhibits a structured sparsity pattern. In particular, for the partial Fourier recovery of sparse signals over a circulant transform, our main results suggest a uniformly random sampling. Numerical results demonstrate that the variable density random sampling by our main results provides a superior recovery performance over the known sampling strategies. [ABSTRACT FROM AUTHOR]

One of the most important open problems in the theory of error-correcting codes is to determine the tradeoff between the rate $R$ and minimum distance $\delta $ of a binary code. The best known tradeoff is the Gilbert–Varshamov bound, and says that for every $\delta \in (0, 1/2)$ , there are codes with minimum distance $\delta $ and rate $R = {R_{\mathsf {GV}}}(\delta) > 0$ (for a certain simple function ${R_{\mathsf {GV}}}(\cdot)$ ). In this paper, we show that the Gilbert–Varshamov bound can be achieved by codes, which support local error-detection and error-correction algorithms. Specifically, we show the following results. 1) Local testing: for all $\delta \in (0,1/2)$ and all $R < {R_{\mathsf {GV}}}(\delta)$ , there exist codes with length $n$ , rate $R$ , and minimum distance $\delta $ that are locally testable with $\mathsf {quasipolylog}(n)$ query complexity. 2) Local correction: for all $\epsilon > 0$ , for all $\delta < 1/2$ sufficiently large, and all $R < (1-\epsilon) {R_{\mathsf {GV}}}(\delta)$ , there exist codes with length $n$ , rate $R$ , and minimum distance $\delta $ that are locally correctable from $({\delta }/{2}) - o(1)$ fraction errors with $O(n^{\epsilon })$ query complexity. Furthermore, these codes have an efficient randomized construction, and the local testing and local correction algorithms can be made to run in time polynomial in the query complexity. Our results on locally correctable codes also immediately give locally decodable codes with the same parameters. Our local testing result is obtained by combining Thommesen’s random concatenation technique and the best known locally testable codes by Kopparty et al. Our local correction result, which is significantly more involved, also uses random concatenation, along with a number of further ideas: the Guruswami–Sudan–Indyk list decoding strategy for concatenated codes, Alon–Edmonds–Luby distance amplification, and the local list-decodability, local list-recoverability, and local testability of Reed–Muller codes. Curiously, our final local correction algorithms go via local list-decoding and local testing algorithms; this seems to be the first time local testability is used in the construction of a locally correctable code. [ABSTRACT FROM AUTHOR]

Quantum teleportation uses prior shared entanglement and classical communication to send an unknown quantum state from one party to another. Remote state preparation (RSP) is a similar distributed task in which the sender knows the entire classical description of the state to be sent. (This may also be viewed as the task of nonoblivious compression of a single sample from an ensemble of quantum states.) We study the communication complexity of approximate RSP (ARSP) in which the goal is to prepare an approximation of the desired quantum state. Jain (Quant. Inf. & Comp., 2006) showed that the worst-case communication complexity of ARSP can be bounded from above in terms of the maximum possible information in an encoding. He also showed that this quantity is a lower bound for communication complexity of (exact) remote state preparation. In this paper, we tightly characterize the worst-case and average-case communication complexity of remote state preparation in terms of nonasymptotic information-theoretic quantities. We also show that the average-case communication complexity of RSP can be much smaller than the worst-case one. In the process, we show that $n$ bits cannot be communicated with less than $n$ transmitted bits in local operations and classical communication protocols. This strengthens a result due to Nayak and Salzman (J. ACM, 2006) and may be of independent interest. [ABSTRACT FROM AUTHOR]

For non-binary codes the Elias bound is a good upper bound for the asymptotic information rate at low-relative minimum distance, whereas the Plotkin bound is better at high-relative minimum distance. In this paper, we obtain a hybrid of these bounds, which improves both. This in turn is based on the anticode bound, which is a hybrid of the Hamming and Singleton bounds and improves both bounds. The question of convexity of the asymptotic rate function is an important open question. We conjecture a much weaker form of the convexity, and we show that our bounds follow immediately if we assume the conjecture. [ABSTRACT FROM AUTHOR]

The capability of a given channel to communicate information is, a priori, distinct from its capability to distribute shared randomness. In this paper, we define randomness distribution capacities of quantum channels assisted by forward, back, or two-way classical communication and compare these to the corresponding communication capacities. With forward assistance or no assistance, we find that they are equal. We establish the mutual information of the channel as an upper bound on the two-way assisted randomness distribution capacity. This implies that all of the capacities are equal for classical-quantum channels. On the other hand, we show that the back-assisted randomness distribution capacity of a quantum-classical channel is equal to its mutual information. This is often strictly greater than the back-assisted communication capacity. We give an explicit example of such a separation where the randomness distribution protocol is noiseless. [ABSTRACT FROM AUTHOR]

We consider a communication network where there exist wiretappers who can access a subset of channels, called a wiretap set, which is chosen from a given collection of wiretap sets. The collection of wiretap sets can be arbitrary. Secure network coding is applied to prevent the source information from being leaked to the wiretappers. In secure network coding, the required alphabet size is an open problem not only of theoretical interest but also of practical importance, because it is closely related to the implementation of such coding schemes in terms of computational complexity and storage requirement. In this paper, we develop a systematic graph-theoretic approach for improving Cai and Yeung’s lower bound on the required alphabet size for the existence of secure network codes. The new lower bound thus obtained, which depends only on the network topology and the collection of wiretap sets, can be significantly smaller than Cai and Yeung’s lower bound. A polynomial-time algorithm is devised for efficient computation of the new lower bound. [ABSTRACT FROM PUBLISHER]

The multiple-unicast conjecture in network coding states that for multiple unicast sessions in an undirected network, network coding has no advantage over routing in improving the throughput or saving bandwidth. In this paper, we propose a reduction method to study the multiple-unicast conjecture, and prove the conjecture for a new class of networks that are characterized by relations between cut-sets and source-receiver paths. This class subsumes all the known types of networks with non-zero max-flow min-cut gaps but zero coding advantage. Combining this result with a computer-aided search, we derive as a corollary that network coding is unnecessary in networks with up to six coding nodes. We also prove the multiple-unicast conjecture for almost all unit-link-length networks with up to three sessions and seven nodes. [ABSTRACT FROM AUTHOR]

Estimators of information theoretic measures, such as entropy and mutual information, are a basic workhorse for many downstream applications in modern data science. State-of-the-art approaches have been either geometric [nearest neighbor (NN)-based] or kernel-based (with a globally chosen bandwidth). In this paper, we combine both these approaches to design new estimators of entropy and mutual information that outperform the state-of-the-art methods. Our estimator uses local bandwidth choices of $k$ -NN distances with a finite $k$ , independent of the sample size. Such a local and data dependent choice ameliorates boundary bias and improves performance in practice, but the bandwidth is vanishing at a fast rate, leading to a non-vanishing bias. We show that the asymptotic bias of the proposed estimator is universal; it is independent of the underlying distribution. Hence, it can be precomputed and subtracted from the estimate. As a byproduct, we obtain a unified way of obtaining both the kernel and NN estimators. The corresponding theoretical contribution relating the asymptotic geometry of nearest neighbors to order statistics is of independent mathematical interest. [ABSTRACT FROM PUBLISHER]

The purpose of this paper is to point out a new connection between information theory and dynamical systems. In the information theory side, we consider rate distortion theory, which studies lossy data compression of stochastic processes under distortion constraints. In the dynamical systems side, we consider mean dimension theory, which studies how many parameters per iterate we need to describe a dynamical system. The main results are new variational principles connecting rate distortion function to metric mean dimension. [ABSTRACT FROM PUBLISHER]

The main result of this paper is that an orthogonal access scheme, such as time division multiple access achieves the all-unicast degrees of freedom (DoF) region of the topological interference management problem if and only if the network topology graph is chordal bipartite, i.e., every cycle that can contain a chord, does contain a chord. The all-unicast DoF region includes the DoF region for any arbitrary choice of a unicast message set, so e.g., the results of Maleki and Jafar on the optimality of orthogonal access for the sum-DoF of one-dimensional convex networks are recovered as a special case. The result is also established for the corresponding topological representation of the index coding problem. [ABSTRACT FROM PUBLISHER]

Quantum Lovász number is a quantum generalization of the Lovász number in graph theory. It is the best known efficiently computable upper bound of the entanglement-assisted zero-error classical capacity of a quantum channel. However, it remains an intriguing open problem whether quantum entanglement can always enhance the zero-error capacity to achieve the quantum Lovász number. In this paper, by constructing a particular class of qutrit-to-qutrit channels, we show that there exists a strict gap between the entanglement-assisted zero-error capacity and the quantum Lovász number. Interestingly, for this class of quantum channels, the quantum generalization of fractional packing number is strictly larger than the zero-error capacity assisted with feedback or no-signaling correlations, which differs from the case of classical channels. [ABSTRACT FROM PUBLISHER]

In this paper, we consider a quantum generalization of the task considered by Slepian and Wolf regarding distributed source compression. In our task, Alice, Bob, Charlie, and Reference share a joint pure state. Alice and Bob wish to send a part of their respective systems to Charlie without collaborating with each other. We give achievability bounds for this task in the one-shot setting and provide the asymptotic and independent identically distributed analysis in the case when there is no side information with Charlie. Our result implies the result of Abeyesinghe et al., who studied a special case of this problem. As another special case wherein Bob holds trivial registers, we recover the result of Devetak and Yard regarding quantum state redistribution. [ABSTRACT FROM PUBLISHER]

This paper presents a new algorithm, termed truncated amplitude flow (TAF), to recover an unknown vector x from a system of quadratic equations of the form yi=|\langle {a}i, {x}\rangle |^{2} , where ai ’s are given random measurement vectors. This problem is known to be NP-hard in general. We prove that as soon as the number of equations is on the order of the number of unknowns, TAF recovers the solution exactly (up to a global unimodular constant) with high probability and complexity growing linearly with both the number of unknowns and the number of equations. Our TAF approach adapts the amplitude-based empirical loss function and proceeds in two stages. In the first stage, we introduce an orthogonality-promoting initialization that can be obtained with a few power iterations. Stage two refines the initial estimate by successive updates of scalable truncated generalized gradient iterations, which are able to handle the rather challenging nonconvex and nonsmooth amplitude-based objective function. In particular, when vectors x and ai ’s are real valued, our gradient truncation rule provably eliminates erroneously estimated signs with high probability to markedly improve upon its untruncated version. Numerical tests using synthetic data and real images demonstrate that our initialization returns more accurate and robust estimates relative to spectral initializations. Furthermore, even under the same initialization, the proposed amplitude-based refinement outperforms existing Wirtinger flow variants, corroborating the superior performance of TAF over state-of-the-art algorithms. [ABSTRACT FROM PUBLISHER]

In recent literature, a family of optimal linear locally recoverable codes (LRC codes) that attain the maximum possible distance (given code length, cardinality, and locality) is presented. The key ingredient for constructing such optimal linear LRC codes is the so-called $r$ -good polynomials, where r$ is equal to the locality of the LRC code. However, given a prime p$ , known constructions of r exist only for some special integers r$ , and the problem of constructing optimal LRC codes over small field for any given locality is still open. In this paper, by using function composition, we present two general methods of designing good polynomials, which lead to three new constructions of r$ -good polynomials. Such polynomials bring new constructions of optimal LRC codes. In particular, our constructed polynomials as well as the power functions yield optimal (n,k,r) for all positive integers $r$ as localities, where $q$ is near the code length $n$ . [ABSTRACT FROM AUTHOR]

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

The bandwidth of a bandlimited signal is an important number that is relevant in many applications and concepts. For example, according to the Shannon sampling theorem, the bandwidth determines the minimum sampling rate that is required for a perfect reconstruction. In this paper we consider bandlimited signals with finite energy and bandlimited signals that are absolutely integrable and analyze whether the bandwidth of these signals can be determined algorithmically. We employ the concept of Turing computability, a theoretical model that describes the fundamental limits of what can be solved algorithmically on a digital hardware, and ask if, for a given computable bandlimited signal, it is possible to compute its bandwidth on a Turing machine. We show that this is not possible in general, because there exist computable bandlimited signals for which the bandwidth is a non-computable real number. Even the weaker question if the bandwidth of a given signal is smaller than a predefined value cannot be always answered algorithmically. Further, we prove that in the case where the bandwidth in not computable, it is even impossible to algorithmically determine a sequence of upper bounds that converges to the actual bandwidth of the signal. As a positive result, we show that the set of signals whose bandwidth is larger than some given value is semi-decidable. [ABSTRACT FROM AUTHOR]

In this paper, we develop the first method for finding strong converse bounds in quantum network information theory. The general scheme relies on a recently obtained result in the field of non-commutative functional inequalities, namely the tensorization property of quantum reverse hypercontractivity for the quantum depolarizing semigroup. We develop a novel technique to employ this result to find both finite blocklength and exponential strong converse bounds for the tasks of quantum source coding with compressed classical side information, and distributed quantum hypothesis testing with communication constraints for a classical-quantum state. In the classical setting, these two problems can be reformulated in a unified framework in terms of the so-called image-size characterization problem, which we extend to the classical-quantum setting. We also use this technique to establish analogous strong converse bounds in broadcast communication scenarios. In particular, we consider the transmission of classical information through a degraded broadcast channel, whose outputs are two quantum systems, with the state of one being a degraded version of the other. In establishing this last result, we prove a second-order Fano-type inequality, which is of independent interest. Our method to study strong converses has potential applications in other important tasks of quantum network information theory. [ABSTRACT FROM AUTHOR]

Entropy and relative or cross entropy measures are two very fundamental concepts in information theory and are also widely used for statistical inference across disciplines. The related optimization problems, in particular the maximization of the entropy and the minimization of the cross entropy or relative entropy (divergence), are essential for general logical inference in our physical world. In this paper, we discuss a two parameter generalization of the popular Rényi entropy and associated optimization problems. We derive the desired entropic characteristics of the new generalized entropy measure including its positivity, expandability, extensivity and generalized (sub-)additivity. More importantly, when considered over the class of sub-probabilities, our new family turns out to be scale-invariant; this property does not hold for most existing generalized entropy measures. We also propose the corresponding cross entropy and relative entropy measures and discuss their geometric properties including generalized Pythagorean results over $\beta $ -convex sets. The maximization of the new entropy and the minimization of the corresponding cross or relative entropy measures are carried out explicitly under the non-extensive (‘third-choice’) constraints given by the Tsallis’ normalized $q$ -expectations which also correspond to the $\beta $ -linear family of probability distributions. Important properties of the associated forward and reverse projection rules are discussed along with their existence and uniqueness. In this context, we have come up with, for the first time, a class of entropy measures – a subfamily of our two-parameter generalization – that leads to the classical (extensive) exponential family of MaxEnt distributions under the non-extensive constraints; this discovery has been illustrated through the useful concept of escort distributions and can potentially be important for future research in information theory. Other members of the new entropy family, however, lead to the power-law type generalized $q$ -exponential MaxEnt distributions which is in conformity with Tsallis’ nonextensive theory. Therefore, our new family indeed provides a wide range of entropy and associated measures combining both the extensive and nonextensive MaxEnt theories under one umbrella. [ABSTRACT FROM AUTHOR]

An equiangular tight frame (ETF) yields a type of optimal packing of lines in a Euclidean space. ETFs seem to be rare, and all known infinite families of them arise from some type of combinatorial design. In this paper, we introduce a new method for constructing ETFs. We begin by showing that it is sometimes possible to construct multiple ETFs for the same space that are “mutually unbiased” in a way that is analogous to the quantum-information-theoretic concept of mutually unbiased bases. We then show that taking certain tensor products of these mutually unbiased ETFs with other ETFs sometimes yields infinite families of new complex ETFs. [ABSTRACT FROM AUTHOR]

We study a class of real robust phase retrieval problems under a Gaussian assumption on the coding matrix when the received signal is sparsely corrupted by noise. The goal is to establish conditions on the sparsity under which the input vector can be exactly recovered. The recovery problem is formulated as residual minimization in the $\ell _{1}$ -norm. The main contribution is a robust phase retrieval counterpart to the seminal paper by Candes and Tao on compressed sensing ($\ell _{1}$ regression) [Decoding by linear programming. IEEE Transactions on Information Theory, 51(12):4203–4215, 2005]. The analysis depends on a key new property of the coding matrix called the Absolute Range Property (ARP) which is the analogue to the Null Space Property (NSP) in compressed sensing. When the residuals are computed using squared magnitudes, we show that ARP follows from a standard Restricted Isometry Property (RIP). However, when the residuals are computed using absolute magnitudes, a different kind of RIP or growth property is required. We conclude by showing that the robust phase retrieval objectives are sharp with respect to their minimizers with high probability. [ABSTRACT FROM AUTHOR]

Resistive memories store information in a crossbar arrangement of two-terminal devices that can be programmed to patterns of high or low resistance. While extremely compact, this technology suffers from the “sneak-path” problem: certain information patterns cannot be recovered, as multiple low resistances in parallel make a high resistance indistinguishable from a low resistance. In this paper, a multi-layer device is considered, and the number of bits it can store is derived exactly and asymptotic bounds are developed. The information density of a series of isolated arrays with extreme aspect ratios is derived in the single- and multi-layer cases with and without peripheral selection circuitry. This density is shown to be non-zero in the limit, unlike that of the arrays with moderate aspect ratios previously considered. A simple encoding scheme that achieves capacity asymptotically is presented. [ABSTRACT FROM AUTHOR]

In this paper, we consider communication on a two-hop channel in which a source wants to send information reliably and securely to the destination via a relay. We consider both the untrusted relay case and the external eavesdropper case. In the untrusted relay case, the relay behaves as an eavesdropper, and there is a cooperative node, which sends a jamming signal to confuse the relay when it is receiving from the source. In the external eavesdropper case, the relay is trusted, and there is an external node eavesdropping the communication. We propose two secure transmission schemes using the scaled compute-and-forward technique. One of the schemes is based on a random binning code, and the other one is based on a lattice chain code. It is proved that in the high signal-to-noise-ratio (SNR) scenario and/or the limited relay power scenario, if the destination is used as the jammer, both schemes outperform all existing schemes and achieve the upper bound. In particular, if the SNR is large and the source, the relay, and the cooperative jammer have identical power and channels, both schemes achieve the upper bound for secrecy rate, which is merely 1/2 bit per channel use lower than the channel capacity without secrecy constraints. We also prove that one of our schemes achieves a positive secrecy rate in the external eavesdropper case in which the relay is trusted and there exists an external eavesdropper. [ABSTRACT FROM AUTHOR]

Let p be a prime, n=2m and d=3p^m-2 with m\geq 2 , and \gcd (d,p^n-1)=1 . In this paper, the correlation distribution between a p -ary m -sequence of period p^n-1 and its d -decimation sequence is investigated in a unified approach. Some results for the binary case are extended to the general case. It is shown that the problem of determining the correlation distribution for d can be reduced to that of solving two combinatorial problems related to the unit circle of the finite field \mathbb {F}_{p^{n}} . For an arbitrary odd prime p , it seems difficult to solve these two problems. However, for p=3 , by studying the weight distribution of the ternary Zetterberg code and counting the numbers of solutions of some equations over \mathbb {F}_{3^{n}} , the two problems are solved, and thus, the corresponding correlation distribution for d$ is completely determined. It is noteworthy that this is the first time that the correlation distribution for a non-binary Niho decimation has been determined since 1976. [ABSTRACT FROM PUBLISHER]

We derive sequential necessary and sufficient conditions for any channel input conditional distribution \mathcal P0,n\triangleq \{PXt|X^{t-1,Y^{t-1}}:t=0,\ldots ,n\} to maximize the finite-time horizon directed information defined by C^\mathrm FBX^{n \rightarrow Y^{n}} \triangleq \sup \cal P0,n I(X^{n}\rightarrow ~{Y^{n}}) , where I(X^n \rightarrow Y^n) =\sum t=0^n{I}(X^{t};Yt|Y^{t-1}) , for channel distributions \PYt|Y^{t-1,Xt:t=0,\ldots ,n\} and \PYt|Yt-M^{t-1,Xt:~t=0,\ldots ,n\} , where Y^t\triangleq \Y^-1, Y0,\ldots ,Y_t\ and X^t\triangleq \X0,\ldots ,X_t\ are the channel input and output random processes, and $M$ is a finite non-negative integer. We apply the necessary and sufficient conditions to application examples of time-varying channels with memory to derive recursive closed form expressions of the optimal distributions, which maximize the finite-time horizon directed information. Furthermore, we derive the feedback capacity from the asymptotic properties of the optimal distributions by investigating the limit C_{X^\infty \rightarrow Y^\infty }^{\mathrm{ FB}} \triangleq \lim _{ n \longrightarrow \infty } ({1}/({n+1})) C_{X^{n} \rightarrow Y^{n}}^{\mathrm{ FB}} without any ´ a priori assumptions, such as stationarity, ergodicity, or irreducibility of the channel distribution. The framework based on sequential necessary and sufficient conditions can be easily applied to a variety of channels with memory, beyond the ones considered in this paper. [ABSTRACT FROM PUBLISHER]

We define a variable-length code having the property that no (non-empty) prefix of each its codeword is a suffix of any other one, and vice versa. This kind of code can be seen as an extension of two well-known codes in the literature, called, respectively, fix-free code and non-overlapping code. In this paper we present constructive algorithms for such codes and some numerical results about their cardinality. [ABSTRACT FROM PUBLISHER]

Communication complexity investigates the amount of communication needed for two or more players to determine some joint function of their private inputs. For many interesting functions, the communication complexity can be much smaller than basic information theoretic measures associated with the players’ inputs such as the input length, the entropy, or even the conditional entropy. Communication complexity of many functions reduces further when the players share randomness. Classical works studied the communication complexity of functions when the interacting players share randomness perfectly, i.e., they get identical copies of randomness from a common source. This paper considers the variant of this question when the players share randomness imperfectly, i.e., when they get noisy copies of the randomness produced by some common source. Our main result shows that any function that can be computed by a $k$ -bit protocol in the perfect sharing model has a 2^{k} -bit protocol in the setting of imperfectly shared randomness and such an exponential growth is necessary. Our upper bound relies on ideas from locality sensitive hashing, while lower bounds rely on hypercontractivity and a new invariance principle tailored for communication protocols. [ABSTRACT FROM PUBLISHER]

An (n,k,l) maximum distance separable (MDS) array code of length n , dimension k=n-r , and sub-packetization l is formed of l\times n matrices over a finite field F , with every column of the matrix stored on a separate node in the distributed storage system and viewed as a coordinate of the codeword. Repair of a failed node (recovery of one erased column) can be performed by accessing a set of d\le n-1 surviving (helper) nodes. The code is said to have the optimal access property if the amount of data accessed at each of the helper nodes meets a lower bound on this quantity. For optimal-access MDS codes with . In our previous work (IEEE Trans. Inf. Theory, vol. 63, no. 4, 2017), for any n and r , we presented an explicit construction of optimal-access MDS codes with sub-packetization . In this paper, we take up the question of reducing the sub-packetization value l to make it to approach the lower bound. We construct an explicit family of optimal-access codes with l=r^\lceil n/r\rceil , which differs from the optimal value by at most a factor of r^2 . These codes can be constructed over any finite field $F$ as long as $|F|\ge r\lceil n/r\rceil $ , and afford low-complexity encoding and decoding procedures. We also define a version of the repair problem that bridges the context of regenerating codes and codes with locality constraints (LRC codes), which we call group repair with optimal access. In this variation, we assume that the set of $n=sm$ nodes is partitioned into $m$ repair groups of size $s$ , and require that the amount of accessed data for repair is the smallest possible whenever the $d=s+k-1$ helper nodes include all the other $s-1$ nodes from the same group as the failed node. For this problem, we construct a family of codes with the group optimal access property. These codes can be constructed over any field $F$ of size $|F|\ge n$ , and also afford low-complexity encoding and decoding procedures. [ABSTRACT FROM PUBLISHER]

As a class of optimal combinatorial objects, bent functions have important applications in cryptography, sequence design, and coding theory. Bent idempotents are a subclass of bent functions and of great interest, since they can be stored in less space and allow faster computation of the Walsh-Hadamard transform. The objective of this paper is to present a generic construction of bent functions from known ones. It includes the previous constructions of bent functions by Mesnager and Xu et al. as special cases, and produces new bent functions, which cannot be produced by earlier ones. In particular, it also generates infinite families of bent idempotents over F2^{2m} of any algebraic degree between 2 and $m$ . This together with a recent construction by Su and Tang gives a positive answer to an open problem on bent idempotents proposed by Carlet. In addition, an infinite family of anti-self-dual bent functions is obtained in which the sum of any three distinct functions is again an anti-self-dual bent function in this family. This solves an open problem recently proposed by Mesnager. [ABSTRACT FROM PUBLISHER]

Source coding is the canonical problem of data compression in information theory. In a locally encodable source coding, each compressed bit depends on only few bits of the input. In this paper, we show that a recently popular model of semisupervised clustering is equivalent to locally encodable source coding. In this model, the task is to perform multiclass labeling of unlabeled elements. At the beginning, we can ask in parallel a set of simple queries to an oracle who provides (possibly erroneous) binary answers to the queries. The queries cannot involve more than two (or a fixed constant number of) elements. Now the labeling of all the elements (or clustering) must be performed based on the noisy query answers. The goal is to recover all the correct labelings while minimizing the number of such queries. The equivalence to locally encodable source codes leads us to find lower bounds on the number of queries required in variety of scenarios. We provide querying schemes based on pairwise ‘same cluster’ queries - and pairwise AND queries, and show provable performance guarantees for each of the schemes. [ABSTRACT FROM AUTHOR]

Recently Reed-Solomon (RS) codes were shown to possess a repair scheme that supports repair of failed nodes with optimal repair bandwidth. In this paper, we extend this result in two directions. First, we propose a new repair scheme for the RS codes constructed in [Tamo-Ye-Barg, IEEE Transactions on Information Theory, vol. 65, May 2019] and show that repair is robust to erroneous information provided by the helper nodes while maintaining the optimal repair bandwidth. Second, we construct a new family of RS codes with optimal access for the repair of any single failed node. We also show that the constructed codes can accommodate both features, supporting optimal-access repair with optimal error-correction capability. Going beyond RS codes, we also prove that any scalar MDS code with repair bandwidth attaining the cutset bound affords a repair scheme with optimal access property. [ABSTRACT FROM AUTHOR]

Estimating Kullback-Leibler divergence from identical and independently distributed samples is an important problem in various domains. One simple and effective estimator is based on the $k$ nearest neighbor distances between these samples. In this paper, we analyze the convergence rates of the bias and variance of this estimator. Furthermore, we derive a lower bound of the minimax mean square error and show that kNN method is asymptotically rate optimal. [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]

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]