Abstract: Presents a listing of the editorial board, board of governors, current staff, committee members, and/or society editors for this issue of the publication. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Abstract: Presents a listing of the editorial board, board of governors, current staff, committee members, and/or society editors for this issue of the publication. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
S. G. Bobkov;G. P. Chistyakov;F. Götze;
Pages: 5283 - 5293 Abstract: We explore asymptotically optimal bounds for deviations of Bernoulli convolutions from the Poisson limit in terms of the Shannon relative entropy and the Pearson χ2 -distance. The results are based on proper non-uniform estimates for densities. This part deals with the so-called non-degenerate case. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Sergey G. Bobkov;
Pages: 5294 - 5301 Abstract: Upper bounds on absolute moments of the scores are derived for sums of independent random variables in terms of the moments of the scores, as well as in terms of the total variation norm of densities of summands. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Anders Høst-Madsen;Elyas Sabeti;Chad Walton;
Pages: 5302 - 5322 Abstract: A central question in the era of big data is what to do with the enormous amount of information. One possibility is to characterize it through statistics, e.g., averages, or classify it using machine learning, in order to understand the general structure of the overall data. The perspective in this paper is the opposite, namely that most of the value in the information in some applications is in the parts that deviate from the average, that are unusual, atypical. We define what we mean by atypical in an axiomatic way as data that can be encoded with fewer bits in itself rather than using the code for the typical data. We show that this definition has good theoretical properties. We then develop an implementation based on universal source coding, and apply this to a number of real world data sets. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Uri Hadar;Ofer Shayevitz;
Pages: 5323 - 5338 Abstract: We study a distributed estimation problem in which two remotely located parties, Alice and Bob, observe an unlimited number of i.i.d. samples corresponding to two different parts of a random vector. Alice can send k bits on average to Bob, who in turn wants to estimate the cross-correlation matrix between the two parts of the vector. In the case where the parties observe jointly Gaussian scalar random variables with an unknown correlation ρ, we obtain two constructive and simple unbiased estimators attaining a variance of (1 - ρ2)/(2k ln 2), which coincides with a known but non-constructive random coding result of Zhang and Berger. We extend our approach to the vector Gaussian case, which has not been treated before, and construct an estimator that is uniformly better than the scalar estimator applied separately to each of the correlations. We then show that the Gaussian performance can essentially be attained even when the distribution is completely unknown. This in particular implies that in the general problem of distributed correlation estimation, the variance can decay at least as O(1/k) with the number of transmitted bits. This behavior, however, is not tight: we give an example of a rich family of distributions for which local samples reveal essentially nothing about the correlations, and where a slightly modified estimator attains a variance of 2-Ω(k). PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Sundeep Rangan;Philip Schniter;Alyson K. Fletcher;Subrata Sarkar;
Pages: 5339 - 5351 Abstract: Approximate message passing (AMP) methods and their variants have attracted considerable recent attention for the problem of estimating a random vector x observed through a linear transform A. In the case of large i.i.d. zero-mean Gaussian A, the methods exhibit fast convergence with precise analytic characterizations on the algorithm behavior. However, the convergence of AMP under general transforms A is not fully understood. In this paper, we provide sufficient conditions for the convergence of a damped version of the generalized AMP (GAMP) algorithm in the case of quadratic cost functions (i.e., Gaussian likelihood and prior). It is shown that, with sufficient damping, the algorithm is guaranteed to converge, although the amount of damping grows with peak-to-average ratio of the squared singular values of the transforms A. This result explains the good performance of AMP on i.i.d. Gaussian transforms A, but also their difficulties with ill-conditioned or non-zero-mean transforms A. A related sufficient condition is then derived for the local stability of the damped GAMP method under general cost functions, assuming certain strict convexity conditions. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

$alpha$+
-Divergence&rft.title=IEEE+Transactions+on+Information+Theory&rft.issn=0018-9448&rft.date=2019&rft.volume=65&rft.spage=5352&rft.epage=5366&rft.aulast=Ohnishi;&rft.aufirst=Yuzo&rft.au=Yuzo+Maruyama;Takeru+Matsuda;Toshio+Ohnishi;">Harmonic Bayesian Prediction Under $alpha$
-Divergence

Authors:
Yuzo Maruyama;Takeru Matsuda;Toshio Ohnishi;
Pages: 5352 - 5366 Abstract: We investigate Bayesian shrinkage methods for constructing predictive distributions. We consider the multivariate normal model with a known covariance matrix and show that the Bayesian predictive density with respect to Stein’s harmonic prior dominates the best invariant Bayesian predictive density when the dimension is greater than or equal to 3. Alpha divergence from the true distribution to a predictive distribution is adopted as a loss function. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Chenglong Ye;Yuhong Yang;
Pages: 5367 - 5379 Abstract: High-dimensional linear regression with interaction effects is broadly applied in research fields such as bioinformatics and social science. In this paper, first, we investigate the minimax rate of convergence for regression estimation in high-dimensional sparse linear models with two-way interactions. Here, we derive matching upper and lower bounds under three types of heredity conditions: strong heredity, weak heredity, and no heredity. From the results: 1) A stronger heredity condition may or may not drastically improve the minimax rate of convergence. In fact, in some situations, the minimax rates of convergence are the same under all three heredity conditions; 2) The minimax rate of convergence is determined by the maximum of the total price of estimating the main effects and that of estimating the interaction effects, which goes beyond purely comparing the order of the number of non-zero main effects $r_{1}$ and non-zero interaction effects $r_{2}$ ; and 3) Under any of the three heredity conditions, the estimation of the interaction terms may be the dominant part in determining the rate of convergence. This is due to either the dominant number of interaction effects over main effects or the higher interaction estimation price induced by a large ambient dimension. Second, we construct an adaptive estimator that achieves the minimax rate of convergence regardless of the true heredity condition and the sparsity indices $r_{1}, r_{2}$ . PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Morteza Ashraphijuo;Vaneet Aggarwal;Xiaodong Wang;
Pages: 5380 - 5400 Abstract: We investigate the fundamental conditions on the sampling pattern, i.e., locations of the sampled entries, for finite completability of a low-rank tensor given some components of its Tucker rank. In order to find the deterministic necessary and sufficient conditions, we propose an algebraic geometric analysis on the Tucker manifold, which allows us to incorporate multiple rank components in the proposed analysis in contrast with the conventional geometric approaches on the Grassmannian manifold. This analysis characterizes the algebraic independence of a set of polynomials defined based on the sampling pattern, which is closely related to finite completability of the sampled tensor, where finite completability simply means that the number of possible completions of the sampled tensor is finite. Probabilistic conditions are then studied and a lower bound on the sampling probability is given, which guarantees that the proposed deterministic conditions on the sampling patterns for finite completability hold with high probability. Furthermore, using the proposed geometric approach for finite completability, we propose a sufficient condition on the sampling pattern that ensures there exists exactly one completion of the sampled tensor. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Lek-Heng Lim;Rodolphe Sepulchre;Ke Ye;
Pages: 5401 - 5405 Abstract: We show how the geodesic distance on S++n, the cone of n × n real symmetric or complex Hermitian positive definite matrices regarded as a Riemannian manifold, may be used to naturally define a distance between two such matrices of different dimensions. Given that S++n also parameterizes n-dimensional ellipsoids, inner products on ℝn, and n × n covariances of nondegenerate probability distributions, this gives us a natural way to define a geometric distance between a pair of such objects of different dimensions. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Yu-Xiang Wang;Huan Xu;Chenlei Leng;
Pages: 5406 - 5432 Abstract: An important problem in analyzing big data is subspace clustering, i.e., to represent a collection of points in a high-dimensional space via the union of low-dimensional subspaces. Sparse subspace clustering (SSC) and Low-rank representation (LRR) are the state-of-the-art methods for this task. These two methods are fundamentally similar in that both are based on convex optimization exploiting the intuition of “Self-Expressiveness”. The main difference is that the SSC minimizes the vector ℓ1 norm of the representation matrix to induce sparsity while LRR minimizes the nuclear norm (aka trace norm) to promote a low-rank structure. Because the representation matrix is often simultaneously sparse and low-rank, we propose a new algorithm, termed Low-rank sparse subspace clustering (LRSSC), by the combining SSC and LRR, and develop theoretical guarantees of the success of the algorithm. The results reveal interesting insights into the strengths and the weaknesses of SSC and LRR, and demonstrate how the LRSSC can take advantage of both methods in preserving the “Self-Expressiveness Property” and “Graph Connectivity” at the same time. A byproduct of our analysis is that it also expands the theoretical guarantee of SSC to handle cases when the subspaces have arbitrarily small canonical angles but are “nearly independent”. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Lev Yohananov;Eitan Yaakobi;
Pages: 5433 - 5453 Abstract: Motivated by systems, where the information is represented by a graph such as neural networks, associative memories, and distributed systems. In this paper, we present a new class of codes, called codes over graphs. Under this paradigm, the information is stored on the edges of undirected or directed complete graphs, and a code over graphs is a set of graphs. A node failure is the event, where all edges in the neighborhood of the erased node have been erased. We say that a code over graphs can tolerate $rho $ node failures, if it can correct the erased edges of any $rho $ failed nodes in the graph. While the construction of optimal codes over graphs can be easily accomplished by MDS codes, their field size has to be at least ${mathcal{ O}}(n^{2})$ , when $n$ is the number of nodes in the graph. In this paper, we present several constructions of codes over graphs with smaller field size. To accomplish this task, we use constructions of product codes and rank metric codes. Furthermore, we present optimal codes over graphs correcting two node failures over the binary field, when the number of nodes in the graph is a prime number. Last, we also provide upper bound on the number of nodes for optimal codes. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Swanand Kadhe;Salim El Rouayheb;Iwan Duursma;Alex Sprintson;
Pages: 5454 - 5468 Abstract: We extend the notion of locality from the Hamming metric to the rank and subspace metrics. Our main contribution is to construct a class of array codes with locality constraints in the rank metric. Our motivation for constructing such codes stems from the need to design codes for efficient data recovery from correlated and/or mixed (i.e., complete and partial) failures in distributed storage systems. Specifically, the proposed local rank-metric codes can recover locally from crisscross errors and erasures, which affect a limited number of rows and/or columns of the storage array. We also derive a Singlet-on-like upper bound on the minimum rank distance of (linear) codes with rank-locality constraints. Our proposed construction achieves this bound for a broad range of parameters. The construction builds upon Tamo and Barg's method for constructing locally repairable codes with optimal minimum Hamming distance. Finally, we construct a class of constant-dimension subspace codes (also known as Grassmannian codes) with locality constraints in the subspace metric. The key idea is to show that a Grassmannian code with locality can be easily constructed from a rank-metric code with locality by using the lifting method proposed by Silva et al. We present an application of such codes for distributed storage systems, wherein nodes are connected over a network that can introduce errors and erasures. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Mehran Elyasi;Soheil Mohajer;
Pages: 5469 - 5483 Abstract: Determinant codes are a class of exact-repair regenerating codes for distributed storage systems with parameters (n, k = d, d). These codes cover the entire trade-off between per-node storage and repair-bandwidth. In an earlier work of the authors, the repair data of the determinant code sent by a helper node to repair a failed node depends on the identity of the other helper nodes participating in the process, which is practically undesired. In this paper, a new repair mechanism is proposed for determinant codes, which relaxes this dependency, while preserving all other properties of the code. Moreover, it is shown that the determinant codes are capable of repairing multiple failures, with a per-node repair-bandwidth which scales sub-linearly with the number of failures. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Weiqi Li;Zhiying Wang;Hamid Jafarkhani;
Pages: 5484 - 5502 Abstract: Reed-Solomon (RS) codes are widely used in distributed storage systems. In this paper, we study the repair bandwidth and sub-packetization size of RS codes. The repair bandwidth is defined as the amount of transmitted information from surviving nodes to a failed node. The RS code can be viewed as a polynomial over a finite field GF(qI) evaluated at a set of points, where I is called the sub-packetization size. Smaller bandwidth reduces the network traffic in distributed storage, and smaller I facilitates the implementation of RS codes with lower complexity. Recently, Guruswami and Wootters proposed a repair method for RS codes when the evaluation points are the entire finite field. While the sub-packetization size can be arbitrarily small, the repair bandwidth is higher than the minimum storage regenerating (MSR) bound. Tamo, Ye, and Barg achieved the MSR bound but the sub-packetization size grows faster than the exponential function of the number of the evaluation points. In this paper, we present code constructions and repair schemes that extend these results to accommodate different sizes of the evaluation points. In other words, we design schemes that provide points in between. These schemes provide a flexible tradeoff between the sub-packetization size and the repair bandwidth. In addition, we generalize our schemes to manage multiple failures. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Liang Bai;Zihui Liu;
Pages: 5503 - 5518 Abstract: Based on applications to the wire-tap channel of type II with the coset coding scheme, we will define optimal codes which are described as the ones achieving upper bounds on e2 - M2, where e2 and M2 are the second relative greedy weight and the second relative generalized Hamming weight, respectively. By using the finite geometry method, we will first classify all the 4-dimensional codes with respect to their k1-dimensional subcodes for k1 = 1 and k1 = 2 and determine the upper bounds on e2- M2 for each class of codes, and then obtain optimal codes by explicitly constructing the value assignments which achieve upper bounds on e2 - M2. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Thach V. Bui;Minoru Kuribayashi;Mahdi Cheraghchi;Isao Echizen;
Pages: 5519 - 5528 Abstract: We consider non-adaptive threshold group testing for identification of up to d defective items in a set of n items, where a test is positive if it contains at least 2 ≤ u ≤ d defective items, and negative otherwise. The defective items can be identified using t = O ((d/u)u (d/d-u)d-u (u log d/u + log 1/∈)·d2 log n) tests with probability at least 1 - ∈ for any ∈> 0 or t = O((d/u)u (d/d-u)d-u d3 log n · log d/n) tests with probability 1. The decoding time is t × poly(d2 log n). This result significantly improves the best known results for decoding non-adaptive threshold group testing: O(n log n + n log 1/∈) for probabilistic decoding, where ∈> 0, and O(nu log n) for deterministic decoding. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Amit Solomon;Yuval Cassuto;
Pages: 5529 - 5546 Abstract: We construct error-correcting write-once memory (WOM) codes that guarantee correction of any specified number of errors in q-level memories. The constructions use suitably designed short q-ary WOM codes and concatenate them with outer error-correcting codes over different alphabets using suitably designed mappings. With a new storage-efficiency measure, we call EC-rate and show that for common error types the codes save redundancy and implementation complexity over straightforward concatenation. In addition to constructions for guaranteed error correction, we extend the error-correcting WOM scheme to binary multi-level coding for random errors, and toward soft-decision decoding provide an efficient way to extract reliability information without using higher-precision readout. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Abhishek Agarwal;Larkin Flodin;Arya Mazumdar;
Pages: 5547 - 5564 Abstract: Index coding, a source coding problem over broadcast channels, has been a subject of both theoretical and practical interests since its introduction (by Birk and Kol, 1998). In short, the problem can be defined as follows: there is an input P (p1,⋯,pn), a set of n clients who each desire a single entry pi of the input, and a broadcaster whose goal is to send as few messages as possible to all clients so that each one can recover its desired entry. Additionally, each client has some predetermined “side information,” corresponding to the certain entries of the input P, which we represent as the “side information graph” G. The graph G has a vertex vi for client i and a directed edge (vi, vj), indicating that client i knows the jth entry of the input. Given a fixed side information graph G, we are interested in determining or approximating the “broadcast rate” of index coding on the graph, i.e., the least number of messages the broadcaster can transmit so that every client recovers its desired information. The complexity of determining this broadcast rate in the most general case is open, and the best-known approximations are barely better than the trivial O(n)-approximation corresponding to sending each client their information directly without performing any coding. Using index coding schemes based on linear programs (LPs), we take a two-pronged approach to approximating the broadcast rate. First, extending earlier work on planar graphs, we focus on approximating the broadcast rate for special graph families, such as graphs with the small chromatic number and disk graphs. In certain cases, we are able to show that simple LP-based schemes give constant-factor approximations of the broadcast rate, which seem extremely difficult to obtain in the general case. Second, we prov-de several LP-based schemes for the general case, which are not constant-factor approximations, but which strictly improve on the best-known schemes. These can be viewed as both a strengthening of the constant-factor approximations proven for special graph families (as these schemes strictly improve on those which we prove are good approximations), as well as another tool that can be used either in practice or in future theoretical analyses. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Yiwei Zhang;Xin Wang;Hengjia Wei;Gennian Ge;
Pages: 5565 - 5573 Abstract: Given a database, the private information retrieval (PIR) protocol allows a user to make queries to several servers and retrieve a certain item of the database via the feedbacks without revealing the identity of the specific item to any single server. Classic k-server PIR protocols work on replicated databases, i.e., each of the k servers stores a whole copy of the database. Recently, new PIR models were proposed with coding techniques arising from the distributed storage system. In these new models, each server only stores a fraction 1/s of the whole database, where s> 1 is the given rational number. The PIR array codes are recently proposed by Fazeli, Vardy, and Yaakobi to characterize the new models. The central problem in designing a PIR array code with m servers and the k-PIR property (which indicates that these m servers may emulate a classic k-server PIR protocol) is to maximize k/m, known as the virtual server rate. Our main contribution to this problem is twofold. First, for the case 1 2, a new upper bound on the rate of a PIR array code is presented. Besides, we also have some discussions on an asymptotically optimal construction by Blackburn and Etzion. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Weijun Fang;Fang-Wei Fu;
Pages: 5574 - 5579 Abstract: In this paper, we consider the problem for which lengths a maximum distance separable (MDS) Euclidean self-dual code over Fq exists. This problem is completely solved for the case where q is even. For q is odd, some q-ary MDS Euclidean self-dual codes were obtained in the literature. In this paper, we construct six new classes of q-ary MDS Euclidean self-dual codes by using generalized Reed-Solomon (GRS for short) codes and extended GRS codes. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Arya Mazumdar;Andrew Mcgregor;Sofya Vorotnikova;
Pages: 5580 - 5591 Abstract: Motivated by applications in distributed storage, the storage capacity of a graph was recently defined to be the maximum amount of information that can be stored across the vertices of a graph such that the information at any vertex can be recovered from the information stored at the neighboring vertices. Computing the storage capacity is a fundamental problem in network coding and is related, or equivalent, to some well-studied problems such as index coding with side information and generalized guessing games. In this paper, we consider storage capacity as a natural information-theoretic analogue of the minimum vertex cover of a graph. Indeed, while it was known that storage capacity is upper bounded by minimum vertex cover, we show that by treating it as such we can get a 3/2 approximation for planar graphs, and a 4/3 approximation for triangle-free planar graphs. Since the storage capacity is intimately related to the index coding rate, we get a 2 approximation of index coding rate for planar graphs and 3/2 approximation for triangle-free planar graphs. Previously, only a trivial 4 approximation of the index coding rate was known for planar graphs. We also show a polynomial time approximation scheme for the index coding rate when the alphabet size is constant. We then develop a general method of “gadget covering” to upper bound the storage capacity in terms of the average of a set of vertex covers. This method is intuitive and leads to the exact characterization of storage capacity for various families of graphs. As an illustrative example, we use this approach to derive the exact storage capacity of cycles-with-chords, a family of graphs related to outerplanar graphs. Finally, we generalize the storage capacity notion to include recovery from partial node failures in distributed storage. We show tight upper and lower bounds on this partial recovery capacity that scales nicely with the fraction of failures in a vertex. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Huseyin A. Inan;Peter Kairouz;Mary Wootters;Ayfer Özgür;
Pages: 5592 - 5603 Abstract: We consider the probabilistic group testing problem where d random defective items in a large population of N items are identified with high probability by applying binary tests. It is known that the Θ(d log N) tests are necessary and sufficient to recover the defective set with vanishing probability of error when d = O(Nα) for some α ∈ (0, 1). However, to the best of our knowledge, there is no explicit (deterministic) construction achieving Θ(d log N) tests in general. In this paper, we show that a famous construction introduced by Kautz and Singleton for the combinatorial group testing problem (which is known to be suboptimal for combinatorial group testing for moderate values of d) achieves the order optimal Θ(d log N) tests in the probabilistic group testing problem when d = Ω(log2 N). This provides a strongly explicit construction achieving the order optimal result in the probabilistic group testing setting for a wide range of values of d. To prove the order-optimality of Kautz and Singleton's construction in the probabilistic setting, we provide a novel analysis of the probability of a non-defective item being covered by a random defective set directly, rather than arguing from combinatorial properties of the underlying code, which has been the main approach in the literature. Furthermore, we use a recursive technique to convert this construction into one that can also be efficiently decoded with only a log-log factor increase in the number of tests. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Dmitri Truhachev;David G. M. Mitchell;Michael Lentmaier;Daniel J. Costello;Alireza Karami;
Pages: 5604 - 5617 Abstract: A novel code construction based on spatially coupled low-density parity-check (SC-LDPC) codes is presented. The proposed code ensembles are comprised of several protograph-based chains characterizing individual SC-LDPC codes. We demonstrate that the code ensembles obtained by connecting appropriately chosen individual SC-LDPC code chains at specific points have improved iterative decoding thresholds. In addition, the connected chain ensembles have a smaller decoding complexity required to achieve a specific bit error probability compared to the individual code chains. Moreover, we demonstrate that, like the individual component chains, the proposed constructions have a typical minimum distance that grows linearly with block length. Finally, we show that the improved asymptotic properties of the connected chain ensembles also translate into improved finite length performance. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Jean Barbier;Mohamad Dia;Nicolas Macris;
Pages: 5618 - 5642 Abstract: Sparse superposition codes, or sparse regression codes, constitute a new class of codes, which was first introduced for communication over the additive white Gaussian noise (AWGN) channel. It has been shown that such codes are capacity-achieving over the AWGN channel under optimal maximum-likelihood decoding as well as under various efficient iterative decoding schemes equipped with power allocation or spatially coupled constructions. Here, we generalize the analysis of these codes to a much broader setting that includes all memoryless channels. We show, for a large class of memoryless channels, that spatial coupling allows an efficient decoder, based on the generalized approximate message-passing (GAMP) algorithm, to reach the potential (or Bayes optimal) threshold of the underlying (or uncoupled) code ensemble. Moreover, we argue that spatially coupled sparse superposition codes universally achieve capacity under GAMP decoding by showing, through analytical computations, that the error floor vanishes and the potential threshold tends to capacity, as one of the code parameters goes to infinity. Furthermore, we provide a closed-form formula for the algorithmic threshold of the underlying code ensemble in terms of Fisher information. Relating an algorithmic threshold to a Fisher information has theoretical as well as practical importance. Our proof relies on the state evolution analysis and uses the potential method developed in the theory of low-density parity-check (LDPC) codes and compressed sensing. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Henry D. Pfister;Rüdiger L. Urbanke;
Pages: 5643 - 5655 Abstract: For any prime power q, Mori and Tanaka introduced a family of q-ary polar codes based on the q x q Reed- Solomon polarization kernels. For transmission over a q-ary erasure channel, they also derived a closed-form recursion for the erasure probability of each effective channel. In this paper, we use that expression to analyze the finite-length scaling of these codes on the q-ary erasure channel with erasure probability ε ∈ (0, 1). Our primary result is that for any γ> 0 and δ> 0, there is a q0, such that for all q ≥ q0, the fraction of effective channels with erasure rate at most N-γ is at least 1 - ε- O(N-1/2+δ), where N = qn is the blocklength. Since this fraction cannot be larger than 1 - ε - O(N-1/2), this establishes near-optimal finite-length scaling for this family of codes. Our approach can be seen as an extension of a similar analysis for binary polar codes by Hassani, Alishahi, and Urbanke. A similar analysis is also considered for q-ary polar codes with m x m polarizing matrices. This separates the effect of the alphabet size from the effect of the matrix size. If the polarizing matrix at each stage is drawn independently and uniformly from the set of invertible m × m matrices, then the linear operator associated with the Lyapunov function analysis can be written in the closed form. To prove near-optimal scaling for polar codes with fixed q as m increases, however, two technical obstacles remain. Thus, we conclude by stating two concrete mathematical conjectures that, if proven, would imply near-optimal scaling for fixed q. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Christopher G. Blake;Frank R. Kschischang;
Pages: 5656 - 5673 Abstract: It is shown that all polar encoding schemes using a standard encoding matrix with rate R>1/2 and block length N have energy within the Thompson circuit model that scales at least as E ≥ Ω (N3/2). This lower bound is achievable up to polylogarithmic factors using a mesh network topology defined by Thompson and the encoding algorithm defined by Arıkan. A general class of circuits that compute successive cancellation decoding adapted from Arıkan's butterfly network algorithm is defined. It is shown that such decoders implemented on a rectangle grid for codes of rate R> 2/3 must take energy E ≥ Ω (N3/2). The energy of a Mead memory architecture and a mesh network memory architecture are analyzed and it is shown that a processor architecture using these memory elements can reach the decoding energy lower bounds to within a polylogarithmic factor. Similar scaling rules are derived for polar list decoders and belief propagation decoders. Capacity approaching sequences of energy optimal polar encoders and decoders, as a function of reciprocal gap to capacity χ = (1- R/C)-1 (where R is rate C and is channel capacity), have energy that scales as Ω (χ5.3685) ≤ E ≤ O (χ7.071 log4 (χ)). Known results in constant depth circuit complexity theory imply that no polynomial size classical circuits can compute polar encoding, but this is possible in quantum circuits that include a constant depth quantum fan-out gate. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Juan Pablo Vigneaux;
Pages: 5674 - 5687 Abstract: Whereas Shannon entropy is related to the growth rate of multinomial coefficients, we show that the quadratic entropy (Tsallis 2-entropy) is connected to their $ {q}$ -deformation; when $ {q}$ is a prime power, these $ {q}$ -multinomial coefficients count flags of finite vector spaces with prescribed length and dimensions. In particular, the $ {q}$ -binomial coefficients count vector subspaces of a given dimension. We obtain in this way a combinatorial explanation for the nonadditivity of the quadratic entropy, which arises from a recursive counting of flags. We show that the statistical systems whose configurations are described by flags provide a frequentist justification for the maximum entropy principle with Tsallis statistics. We then introduce a discrete-time stochastic process associated to the $ {q}$ -binomial probability distribution, that generates at time $ {n}$ a vector subspace of $mathbb {F}_{ {q}}^{ {n}}$ (here $mathbb {F}_{ {q}}$ is the finite field of order $ {q}$ ). The concentration of measure on certain “typical subspaces” allows us to extend the asymptotic equipartition property to this setting. The size of the typical set is quantified by the quadratic entropy. We discuss the applications to Shannon theory, particularly to source coding, when messages c-rrespond to vector spaces. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Urs Niesen;
Pages: 5688 - 5704 Abstract: Deduplication finds and removes long-range data duplicates. It is commonly used in cloud and enterprise server settings and has been successfully applied to primary, backup, and archival storage. Despite its practical importance as a source-coding technique, its analysis from the point of view of information theory is missing. This paper provides such an information-theoretic analysis of data deduplication. It introduces a new source model adapted to the deduplication setting. It formalizes the two standard fixed-length and variable-length deduplication schemes, and it introduces a novel multi-chunk deduplication scheme. It then provides an analysis of these three deduplication variants, emphasizing the importance of boundary synchronization between source blocks and deduplication chunks. In particular, under fairly mild assumptions, the proposed multi-chunk deduplication scheme is shown to be order optimal. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Gonzalo Vazquez-Vilar;Albert Guillén i Fàbregas;Sergio Verdú;
Pages: 5705 - 5717 Abstract: We introduce a definition of perfect and quasi-perfect codes for discrete symmetric channels based on the packing and covering properties of generalized spheres whose shape is tilted using an auxiliary probability measure. This notion generalizes previous definitions of perfect and quasi-perfect codes and encompasses maximum distance separable codes. The error probability of these codes, whenever they exist, is shown to coincide with the estimate provided by the meta-converse lower bound. We illustrate how the proposed definition naturally extends to cover almost-lossless source-channel coding and lossy compression. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Bikash Kumar Dey;Sidharth Jaggi;Michael Langberg;
Pages: 5718 - 5736 Abstract: We consider a communication problem in which a sender, Alice, wishes to communicate with a receiver, Bob, over a channel controlled by an adversarial jammer, James, who is myopic. Specifically, for blocklength n, the codeword Xn transmitted by Alice is corrupted by James who must base his adversarial decisions (of which locations of Xn to corrupt and how to corrupt them) on the non-causal observation Zn of Xn obtained through a noisy memoryless channel. More specifically, our communication model may be described by two channels. A memoryless channel pZ X from Alice to James, and an arbitrarily varying channel from Alice to Bob, pY XS governed by a state Sn determined by James. In standard adversarial channels, the states Sn may depend on the codeword Xn, but in our setting Sn depends non-causally only on James's view Zn. We present upper and lower bounds on the capacity of myopic channels. For a number of special cases of interest we show that our bounds are tight. We then extend our results to the setting of secure communication, in which we require that the transmitted message remains secret from James. For example, we show that if 1i) James may flip at most a p fraction of the bits communicated between Alice and Bob and 2) James views Xn through a binary symmetric channel with crossover probability q, then once James is “sufficiently myopic” (in this case, when p H(p)), then the optimal communication rate is that of an adversary who is “blind” (that is, an adversary that does not have any knowledge of Xn at all), which is 1- H(p) for standard communication, and H(q)- H(p) for secure communication. A similar phenomenon exists for more general models of communication. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Sudheer Poojary;Sanidhay Bhambay;Parimal Parag;
Pages: 5737 - 5749 Abstract: For timely sensor update, the traditional approach is to send new information at every available opportunity. Recent research has shown that with limited receiver feedback, sensors can improve the update timeliness by transmitting differential information for slowly varying correlated sources. One can elect to transmit either the actual or the differential state information based on a differential encoding threshold for a general Markov source. This threshold captures the natural trade-off between differential transmission opportunities and the coding gains. Using matrix-geometric method, we find the limiting age distribution for a Markov source as a function of the encoding threshold, from which several other performance metrics of interest, such as mean age, peak age, and the probability of decoding failure can be derived. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Ryo Yaguchi;Masahito Hayashi;
Pages: 5750 - 5770 Abstract: We derive the optimal second-order rates in joint source-channel coding when the channel is a general discrete memoryless channel and the source is an irreducible and ergodic Markov process. In contrast, previous studies solved it only when the channel satisfies a certain unique-variance condition and the source is subject to an independent and identical distribution. We also compare the joint source-channel scheme with the separation scheme in the second-order regime, while a previous study made a notable comparison with numerical calculation. To discuss these two topics, we introduce two kinds of new distribution families, switched Gaussian convolution distribution and *-product distribution, which are defined by modifying the Gaussian distribution. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Chong Li;Yingbin Liang;H. Vincent Poor;Shlomo Shamai Shitz;
Pages: 5771 - 5782 Abstract: In this paper, the finite-order autoregressive moving average (ARMA) Gaussian wiretap channel with noiseless causal feedback is considered, in which an eavesdropper receives noisy observations of signals in both forward and feedback channels. It is shown that the generalized Schalkwijk-Kailath scheme, a capacity-achieving coding scheme for the Gaussian feedback channel, achieves the same maximum rate for the same channel even with the presence of an eavesdropper. Therefore, the secrecy capacity is equal to the feedback capacity without the presence of an eavesdropper for the Gaussian feedback channel. Furthermore, the results are extended to the additive white Gaussian noise (AWGN) channel with quantized feedback. It is shown that the proposed coding scheme achieves a positive secrecy rate. Our result implies that as the amplitude of the quantization noise decreases to zero, the secrecy rate converges to the capacity of the AWGN channel. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Zhuqing Jia;Hua Sun;Syed Ali Jafar;
Pages: 5783 - 5798 Abstract: X-secure and T-private information retrieval (XSTPIR) is a form of private information retrieval where data security is guaranteed against collusion among up to X servers and the user's privacy is guaranteed against collusion among up to T servers. The capacity of XSTPIR is characterized for an arbitrary number of servers N and arbitrary security and privacy thresholds X and T, in the limit as the number of messages K → ∞. Capacity is also characterized for any number of messages if either N = 3, X = T = 1 or if N ≤ X +T. Insights are drawn from these results, about aligning versus decoding noise, dependence of PIR rate on field size, and robustness to symmetric security constraints. In particular, the idea of cross subspace alignment, i.e., introducing a subspace dependence between Reed-Solomon code parameters, emerges as the optimal way to align undesired terms while keeping desired terms resolvable. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Enrico Piovano;Hamdi Joudeh;Bruno Clerckx;
Pages: 5799 - 5815 Abstract: We consider the cache-aided MISO broadcast channel (BC) in which a multi-antenna transmitter serves K single-antenna receivers, each equipped with a cache memory. The transmitter has access to partial knowledge of the channel state information. For a symmetric setting, in terms of channel strength levels, partial channel knowledge levels and cache sizes, we characterize the generalized degrees of freedom (GDoF) up to a constant multiplicative factor. The achievability scheme exploits the interplay between spatial multiplexing gains and coded-multicasting gain. On the other hand, a cut-set-based argument in conjunction with a GDoF outer bound for a parallel MISO BC under channel uncertainty is used for the converse. We further show that the characterized order-optimal GDoF is also attained in a decentralized setting, where no coordination is required for content placement in the caches. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Meghana Bande;Aly El Gamal;Venugopal V. Veeravalli;
Pages: 5816 - 5832 Abstract: Degrees of freedom (DoFs) gains are studied in wireless networks with cooperative transmission under a backhaul load constraint that limits the average number of messages that can be delivered from a centralized controller to base station transmitters. The backhaul load is defined as the sum of all the messages available at all the transmitters per channel use, normalized by the number of users. For Wyner’s linear interference network, where each transmitter is connected to the receiver having the same index as well as one succeeding receiver, the per user DoF is characterized and the optimal scheme is presented. Furthermore, it is shown that the optimal assignment of messages to transmitters is asymmetric and satisfies a local cooperation constraint and the optimal coding scheme relies only on one-shot cooperative zero-forcing transmit beamforming. Using insights from the analysis of Wyner’s linear interference network, the results are extended to the more practical hexagonal sectored cellular network, and coding schemes based on cooperative zero-forcing are shown to deliver significant DoF gains. It is established that by allowing for cooperative transmission and a flexible message assignment that is constrained only by an average backhaul load, one can deliver the rate gains promised by information-theoretic upper bounds with practical one-shot schemes that incur little or no additional load on the backhaul. Finally, useful upper bounds on the per user DoF for schemes based on cooperative zero-forcing are presented for lower values of the average backhaul load constraint, and an optimization framework is formulated for the general converse problem. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Shihui Fu;Xiutao Feng;Qiang Wang;Claude Carlet;
Pages: 5833 - 5845 Abstract: In 2007, Carlet and Ding introduced two parameters, denoted by NbF and NBF, quantifying respectively the balancedness of general functions F between finite Abelian groups and the (global) balancedness of their derivatives DaF(x) = F(x + a) - F(x), a ∈ G {0} (providing an indicator of the nonlinearity of the functions). These authors studied the properties and cryptographic significance of these two measures. They provided inequalities relating the nonlinearity NL(F) to NBF for S-box and specifically obtained an upper bound on the nonlinearity that unifies Sidelnikov-Chabaud-Vaudenay's bound and the covering radius bound. At the Workshop WCC 2009 and in its postproceedings in 2011, a further study of these parameters was made; in particular, the first parameter was applied to the functions F + L, where L is affine, providing more nonlinearity parameters. In 2010, motivated by the study of Costas arrays, two parameters called ambiguity and deficiency were introduced by Panario et al. for permutations over finite Abelian groups to measure the injectivity and surjectivity of the derivatives, respectively. These authors also studied some fundamental properties and cryptographic significance of these two measures. Further studies followed without comparing the second pair of parameters to the first one. In this paper, we observe that ambiguity is the same parameter as NBF up to additive and multiplicative constants (i.e., up to rescaling). We perform the necessary work of comparison and unification of the results on NBF and on ambiguity, which have been obtained in the five papers devoted to these parameters. We generalize some known results to any finite Abelian groups. More importantly, we derive many new results on these parameters. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Xianhua Niu;Chaoping Xing;
Pages: 5846 - 5855 Abstract: In this paper, a general framework of constructing the optimal frequency-hopping sequence (FHS) sets is presented based on the designated direct product. Under this framework, we obtain infinitely many new optimal FHS sets by combining some one-coincide (OC) sequence sets that are newly constructed in this paper with some known optimal FHS sets. Our constructions are also based on extension method. However, our constructions give new and flexible parameters due to the free choice of OC sequence set. As a result, our constructions allow a great flexibility of choosing parameters of FHS sets for a given frequency-hopping spread spectrum system. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
WeiGuo Zhang;
Pages: 5856 - 5864 Abstract: This paper considers the construction of resilient Boolean functions on an odd number of variables with strictly almost optimal (SAO) nonlinearity. Through introducing the fragmentary Walsh transform, a construction technique called “High-Meets-Low” is proposed. The detailed design procedures of a 39-variable 3-resilient Boolean function with SAO nonlinearity 238 - 219 + 216 + 214 are given. It is shown that the nonlinearity of an n-variable t-resilient Boolean function can reach 2n-1-2(n-1)/2+5·2(n-11)/2 or 2n-1-2(n-1)/2+2(n-7)/2, which are the largest known values for the corresponding n and t values. Finally, by constructing a 29-variable balanced Boolean function with SAO nonlinearity 228 -214 + 210 + 29, we show an alternative method to realize the High-Meets-Low construction technique. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Samir Hodžić;Enes Pasalic;Yongzhuang Wei;Fengrong Zhang;
Pages: 5865 - 5879 Abstract: The design of plateaued functions over GF(2)n, also known as 3-valued Walsh spectra functions (taking the values from the set {0, ±2Γ(n+s/2)1}), has been commonly approached by specifying a suitable algebraic normal form which then induces this particular Walsh spectral characterization. In this paper, we consider the reversed design method which specifies these functions in the spectral domain by specifying a suitable allocation of the nonzero spectral values and their signs. We analyze the properties of trivial and nontrivial plateaued functions (as affine inequivalent distinct subclasses), which are distinguished by their Walsh support Sf (the subset of GF(2)n having the nonzero spectral values) in terms of whether it is an affine subspace or not. The former class exactly corresponds to partially bent functions and admits linear structures, whereas the latter class may contain functions without linear structures. A simple sufficient condition on Sf , which ensures the nonexistence of linear structures, is derived and some generic design methods of nontrivial plateaued functions without linear structures are given. The extended affine equivalence of plateaued functions is also addressed using the concept of dual of plateaued functions. Furthermore, we solve the problem of specifying disjoint spectra (non)trivial plateaued functions of maximal cardinality whose concatenation can be used to construct bent functions in a generic manner. This approach may lead to new classes of bent functions due to large variety of possibilities to select underlying duals that define these disjoint spectra plateaued functions. An additional method of specifying affine in equivalent plateaued functions, obtained by applying a nonlinear transform to their input domain, is also given. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Gilad Gour;
Pages: 5880 - 5904 Abstract: We extend the definition of the conditional min-entropy from bipartite quantum states to bipartite quantum channels. We show that many of the properties of the conditional min-entropy carry over to the extended version, including an operational interpretation as a guessing probability when one of the subsystems is classical. We then show that the extended conditional min-entropy can be used to fully characterize when two bipartite quantum channels are related to each other via a superchannel (also known as supermap or a comb) that is acting on one of the subsystems. This relation is a pre-order that extends the definition of “quantum majorization” from bipartite states to bipartite channels, and can also be characterized with semidefinite programming. As a special case, our characterization provides necessary and sufficient conditions for when a set of quantum channels is related to another set of channels via a single superchannel. We discuss the applications of our results to channel discrimination, and to resource theories of quantum processes. Along the way we study channel divergences, entropy functions of quantum channels, and noise models of superchannels, including random unitary superchannels and doubly-stochastic superchannels. For the latter we give a physical meaning as being completely-uniformity preserving. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Anurag Anshu;Rahul Jain;Naqueeb Ahmad Warsi;
Pages: 5905 - 5924 Abstract: This paper concerns the problem of quantum measurement compression with side information in the one-shot setting with shared-randomness. In this problem, Alice shares a pure quantum state with Bob and the reference system. She performs a measurement on her registers and wishes to communicate the outcome to Bob using shared-randomness and classical communication. The outcome that Bob receives must be correctly correlated with the reference system and his own registers. Our goal is to concurrently minimize the classical communication and shared-randomness cost. The suggested protocol presented in this paper is based on convex-split and position based decoding. The communication is upper bounded in terms of smooth max and hypothesis testing relative entropies. A second protocol addresses the task of strong randomness extraction in the presence of quantum side information. The protocol provides an error guarantee in terms of relative entropy (as opposed to trace distance) and extracts close to the optimal number of uniform bits. As an application, we provide a new achievability result for the task of quantum measurement compression without feedback, in which Alice does not need to know the outcome of the measurement. The result achieves the optimal number of bits communicated and the required number of bits of shared-randomness, for the same task in the asymptotic and i.i.d. setting. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Samuel Epstein;
Pages: 5925 - 5930 Abstract: We introduce notions of algorithmic mutual information and deficiency of randomness of quantum states. These definitions enjoy conservation inequalities over unitary transformations and partial traces. We show that a large majority of pure states have minute self-algorithmic information. We provide an algorithmic variant to the no-cloning theorem, by showing that only a small minority of quantum pure states can clone a nonnegligible amount of algorithmic information. We also provide a chain rule inequality for quantum algorithmic entropy. We show that deficiency of randomness does not increase under POVM measurements. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Marco Fanizza;Andrea Mari;Vittorio Giovannetti;
Pages: 5931 - 5944 Abstract: We consider the problem of correctly classifying a given quantum two-level system (qubit) which is known to be in one of two equally probable quantum states. We assume that this task should be performed by a quantum machine which does not have at its disposal a complete classical description of the two template states, but can only have partial prior information about their level of purity and mutual overlap. Moreover, similarly to the classical supervised learning paradigm, we assume that the machine can be trained by n qubits prepared in the first template state and by n more qubits prepared in the second template state. In this situation, we are interested in the optimal process which correctly classifies the input qubit with the largest probability allowed by quantum mechanics. The problem is studied in its full generality for a number of different prior information scenarios and for an arbitrary size n of the training data. Finite size corrections around the asymptotic limit n → ∞ are derived. When the states are assumed to be pure, with known overlap, the problem is also solved in the case of d-level systems. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Péter Vrana;Matthias Christandl;
Pages: 5945 - 5958 Abstract: We prove a lower bound on the rate of Greenberger-Horne-Zeilinger states distillable from pure multipartite states by local operations and classical communication (LOCC). Our proof is based on a modification of a combinatorial argument used in the fast matrix multiplication algorithm of Coppersmith and Winograd. Previous use of methods from algebraic complexity in quantum information theory concerned transformations with stochastic LOCC (SLOCC), resulting in an asymptotically vanishing success probability. In contrast, our new protocol works with an asymptotically vanishing error. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)

Authors:
Giacomo De Palma;
Pages: 5959 - 5968 Abstract: We prove that quantum thermal Gaussian input states minimize the output entropy of the multi-mode quantum Gaussian attenuators and amplifiers that are entanglement breaking and of the multi-mode quantum Gaussian phase contravariant channels among all the input states with an given entropy. This is the first time that this property is proven for a multi-mode channel without restrictions on the input states. A striking consequence of this result is a new lower bound on the output entropy of all the multi-mode quantum Gaussian attenuators and amplifiers in terms of the input entropy. We apply this bound to determine new upper bounds to the communication rates in two different scenarios. The first is classical communication to two receivers with the quantum degraded Gaussian broadcast channel. The second is the simultaneous classical communication, quantum communication and entanglement generation or the simultaneous public classical communication, private classical communication, and quantum key distribution with the Gaussian quantum-limited attenuator. PubDate:
Sept. 2019
Issue No:Vol. 65, No. 9 (2019)