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:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Abstract: These instructions give guidelines for preparing papers for this publication. Presents information for authors publishing in this journal. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Ron M. Roth;Alexander Zeh;
Pages: 2637 - 2647 Abstract: A method is provided for constructing upper triangular square matrices over the univariate polynomial ring over a finite field, under certain constraints on the eigenvalues of the matrices. In some cases of interest, the degree of the determinant of such matrices is shown to be the smallest possible. The method is then applied to construct generator polynomial matrices of quasi-cyclic codes for correcting phased burst errors. Finally, an interpolation-based list decoding algorithm is presented for these codes, which, for a wide range of code parameters, is shown to outperform existing list decoding schemes. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Natalia Silberstein;Tuvi Etzion;Moshe Schwartz;
Pages: 2648 - 2660 Abstract: We study array codes which are based on subspaces of a linear space over a finite field, using spreads, $q$ -Steiner systems, and subspace transversal designs. We present several constructions of such codes which are $q$ -analogs of some known block codes, such as the Hamming and simplex codes. We examine the locality and availability of the constructed codes. In particular, we distinguish between two types of locality and availability: node versus symbol. The resulting codes have distinct symbol/node locality/availability, allowing a more efficient repair process for a single symbol stored in a storage node of a distributed storage system, compared with the repair process for the whole node. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Jay Mardia;Burak Bartan;Mary Wootters;
Pages: 2661 - 2672 Abstract: In distributed storage, erasure codes (like Reed–Solomon Codes) are often employed to provide reliability. In this setting, it is desirable to be able to repair one or more failed nodes while minimizing the repair bandwidth. In this paper, motivated by Reed-Solomon codes, we study the problem of repairing multiple failed nodes in a scalar MDS code. We extend the framework of (Guruswami and Wootters, 2017) to give a framework for constructing repair schemes for multiple failures in general scalar MDS codes in the centralized repair model. We then specialize our framework to Reed–Solomon codes, and also extend and improve upon recent results of (Dau et al., 2017). PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Itzhak Tamo;Min Ye;Alexander Barg;
Pages: 2673 - 2695 Abstract: The repair problem in distributed storage addresses recovery of the data encoded using an erasure code, for instance, a Reed–Solomon (RS) code. We consider the problem of repairing a single node or multiple nodes in RS-coded storage systems using the smallest possible amount of inter-nodal communication. According to the cut-set bound, communication cost of repairing $hgeqslant 1$ failed nodes for an $(n,k=n-r)$ maximum distance separable (MDS) code using $d$ helper nodes is at least $dhl/(d+h-k)$ , where $l$ is the size of the node. Guruswami and Wootters (2016) initiated the study of efficient repair of RS codes, showing that they can be repaired using a smaller bandwidth than under the trivial approach. At the same time, their work as well as follow-up papers stopped short of constructing RS codes (or any scalar MDS codes) that meet the cut-set bound with equality. In this paper, we construct the families of RS codes that achieve the cut-set bound for repair of one or several nodes. In the single-node case, we present the RS codes of length $n$ over the field ${mathbb F}_{q^{l}}, l=exp ((1+o(1))nlog n)$ that meet the cut-set bound. We also prove an almost matching lower bound on $l$ , showing that super-exponential scaling is both necessary and sufficient for scalar MDS codes to achieve the cut-set bound using linear repair schemes. For the case of multiple nodes, we c-nstruct a family of RS codes that achieve the cut-set bound universally for the repair of any $h=1,2, {dots },r$ failed nodes from any subset of $d$ helper nodes, $kleqslant dleqslant n-h$ . For a fixed number of parities $r$ , the node size of the constructed codes is close to the smallest possible node size for codes with such properties. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

${mathbb{F}_{q}}+u{mathbb{F}_{q}}$+
&rft.title=IEEE+Transactions+on+Information+Theory&rft.issn=0018-9448&rft.date=2019&rft.volume=65&rft.spage=2696&rft.epage=2703&rft.aulast=Maouche;&rft.aufirst=Hongwei&rft.au=Hongwei+Liu;Youcef+Maouche;">Two or Few-Weight Trace Codes over ${mathbb{F}_{q}}+u{mathbb{F}_{q}}$

Authors:
Hongwei Liu;Youcef Maouche;
Pages: 2696 - 2703 Abstract: Let $p$ be a prime number and $q=p^{s}$ for a positive integer $s$ . For any positive divisor $e$ of $q-1$ , we construct infinite families of codes $mathcal {C}$ of size $q^{2m}$ with few Lee-weight. These codes are defined as trace codes over the ring $R= mathbb {F}_{q} + u mathbb {F}_{q}$ , $u^{2} = 0$ . Using Gaussian sums, their Lee weight distributions are provided. In particular, when $gcd (e,m)=1$ , under the Gray map, the images of all codes in $mathcal {C}$ are of two-weight over the finite field $mathbb {F}_{q}$ , which meet the Griesmer bound. Moreover, when $gcd (e,m)=2, 3$ , or 4, all codes in $mathcal {C}$ are of most five-weight codes. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Masato Tajima;
Pages: 2704 - 2722 Abstract: We introduce the notion of innovations for Viterbi decoding of convolutional codes. First, we define a kind of innovation corresponding to the received data, i.e., the input to a Viterbi decoder. Then, the structure of a scarce-state-transition (SST) Viterbi decoder is derived in a natural manner. It is shown that the newly defined innovation is just the input to the main decoder in an SST Viterbi decoder and generates the same syndrome as the original received data does. A similar result holds for quick-look-in codes as well. In this case, however, the precise innovation is not defined. We see that this innovation-like quantity is related to the linear smoothed estimate of the information. The essence of innovations approach to a linear filtering problem is first to whiten the observed data, and then to treat the resulting simpler white-noise observations problem. In our case, this corresponds to the reduction of decoding complexity in the main decoder in an SST Viterbi decoder. We show that the distributions related to the main decoder (i.e., the input distribution and the state distribution in the code trellis for the main decoder) are much biased under moderately noisy conditions. We see that these biased distributions actually lead to the complexity reduction in the main decoder. Furthermore, it is shown that the proposed innovations approach can be extended to maximum-likelihood decoding of block codes as well. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Zhifang Zhang;Jingke Xu;
Pages: 2723 - 2735 Abstract: Suppose $M$ records are replicated in $N$ servers (each storing all $M$ records), a user wants to privately retrieve one record by accessing the servers such that the identity of the retrieved record is secret against any up to $T$ servers. A scheme designed for this purpose is called a $T$ -private information retrieval (PIR) scheme. In practice, capacity-achieving and small sub-packetization are both desired for PIR schemes, because the former implies the highest download rate and the latter means simple realization. Meanwhile, sub-packetization is the key technique for achieving capacity. In this paper, we characterize the optimal sub-packetization for linear capacity-achieving $T$ -PIR schemes. First, a lower bound on the sub-packetization $L$ for linear capacity-achieving $T$ -PIR schemes is proved, i.e., $Lgeq dn^{M-1}$ , where $d={mathrm{ gcd}}(N,T)$ and $n=N/d$ . Then, for general values of $M$ and $N>Tgeq 1$ , a linear capacity-achieving $T$ --IR scheme with sub-packetization $dn^{M-1}$ is designed. Comparing with the first capacity-achieving $T$ -PIR scheme given by Sun and Jafar in 2016, our scheme reduces the sub-packetization from $N^{M}$ to the optimal and further reduces the field size by a factor of $Nd^{M-2}$ . PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Kaveh Mahdaviani;Ashish Khisti;Soheil Mohajer;
Pages: 2736 - 2759 Abstract: Regenerating codes are efficient methods for distributed storage in storage networks, where node failures are common. They guarantee low cost data reconstruction and repair through accessing only a predefined number of arbitrarily chosen storage nodes in the network. In this paper, we consider two simultaneous extensions to the original regenerating codes framework introduced by Dimakis et al.; 1) both data reconstruction and repair are resilient to the presence of a certain number of erroneous nodes in the network and 2) the number of helper nodes in every repair is not fixed, but is a flexible parameter that can be selected during the run-time. We study the fundamental limits of required total repair bandwidth and provide an upper bound for the storage capacity of these codes under these assumptions. We then focus on the minimum repair bandwidth (MBR) case and derive the exact storage capacity by presenting explicit coding schemes with exact repair, which achieve the upper bound of the storage capacity in the considered setup. To this end, we first provide a more natural extension of the well-known product matrix (PM) MBR codes, modified to provide flexibility in choosing the number of helpers in each repair, and simultaneously be robust to erroneous nodes in the network. This is achieved by proving the non-singularity for a family of matrices in large enough finite fields. We next provide another extension of the PM codes, based on a novel repair scheme which enables flexibility in the number of helpers and robustness against erroneous nodes without any extra cost in field size compared with the original PM codes. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Venkata Gandikota;Elena Grigorescu;Sidharth Jaggi;Samson Zhou;
Pages: 2760 - 2773 Abstract: Group testing is the process of pooling arbitrary subsets from a set of $ {n}$ items so as to identify, with a minimal number of tests, a “small” subset of $ {d}$ defective items. In “classical” non-adaptive group testing, it is known that when $ {d}$ is substantially smaller than $ {n}$ , $Theta ( {d}log ( {n}))$ tests are both information-theoretically necessary and sufficient to guarantee recovery with high probability. Group testing schemes in the literature that meet this bound require most items to be tested $ {Omega }(log ( {n}))$ times, and most tests to incorporate $ {Omega }({{n/d}})$ items. Motivated by physical considerations, we study group testing models in which the testing procedure is constrained to be “sparse.” Specifically, we consider (separately) scenarios in which 1) items are finitely divisible and hence may participate in at most $ {gamma } in {o}(log ( {n}))$ tests; or 2) tests are size-constrained to pool no more than $rho in {o}({{n/d}})$ items per test. For both scenarios, we provide information-theoretic lower bounds on the number of tests required to guarantee high probability recovery. In particular, one of our main results shows that $ {gamma }$ -finite divisibility of items forces any non-adaptive group testing algorithm with the probability of recovery error at most $ {epsilon }$ to perform at least $ {gamma } {d}({ {n/d}})^{({1}-{5} {epsilon })/ {gamma }}$ tests. Analogously, for $ {rho }$ -sized constrained tests, we show an information-theoretic lower bound of $ {Omega }( {n}/ {rho })$ tests for high-probability recovery–hence in both settings the number of tests required grows dramatically (relative to the classical setting) as a function of $ {n}$ . In both scenarios, we provide both randomized constructions and explicit constructions of designs with computationally efficient reconstruction algorithms that require a number of tests that is optimal up to constant or small polynomial factors in some regimes of ${{n, d,}} {gamma }$ , and $ {rho }$ . The randomized design/reconstruction algorithm in the $ {rho }$ -sized test scenario is universal–independent of the value of $ {d}$ , as long as $ {rho } in {o}({textbf {n/d}})$ . We also investigate the effect of unreliability/noise in test outcomes, and show that whereas the impact of noise in test out PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Zilin Jiang;Nikita Polyanskii;Ilya Vorobyev;
Pages: 2774 - 2781 Abstract: The exact values of the optimal symmetric rate point in the Cover–Leung capacity region of the two-user union channel with complete feedback were determined by Willems when the size of the input alphabet is 2, and by Vinck et al. when the size is at least 6. We complete this line of research when the size of the input alphabet is 3, 4, or 5. The proof hinges on the technical lemma that concerns the maximal joint entropy of two independent random variables in terms of their probability of equality. For the zero-error capacity region, using superposition coding, we provide a practical near-optimal communication scheme which improves all the previous explicit constructions. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Marco Mondelli;S. Hamed Hassani;Rüdiger L. Urbanke;
Pages: 2782 - 2791 Abstract: Consider the problem of constructing a polar code of block length $N$ for a given transmission channel $W$ . Previous approaches require one to compute the reliability of the $N$ synthetic channels and then use only those that are sufficiently reliable. However, we know from two independent works by Schürch and by Bardet et al. that the synthetic channels are partially ordered with respect to degradation. Hence, it is natural to ask whether the partial order can be exploited to reduce the computational burden of the construction problem. We show that, if we take advantage of the partial order, we can construct a polar code by computing the reliability of roughly a fraction $1/log ^{3/2} N$ of the synthetic channels. In particular, we prove that $N/log ^{3/2} N$ is a lower bound on the number of synthetic channels to be considered and such a bound is tight up to a multiplicative factor $log log N$ . This set of roughly $N/log ^{3/2} N$ synthetic channels is universal, in the sense that it allows one to construct polar codes for any $W$ , and it can be identified by solving a maximum matching problem on a bipartite graph. Our proof technique consists of reducing the construction problem to the problem of computing the maximum cardinality of an antichain for a suitable partially ordered set. As such, this method is general, and it can be used to further impr-ve the complexity of the construction problem, in case a refined partial order on the synthetic channels of polar codes is discovered. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Seyed Pooya Shariatpanahi;Giuseppe Caire;Babak Hossein Khalaj;
Pages: 2792 - 2807 Abstract: We investigate the potentials of applying the coded caching paradigm in wireless networks. In order to do this, we investigate physical layer schemes for downlink transmission from a multiantenna transmitter to several cache-enabled users. As the baseline scheme, we consider employing coded caching on the top of max–min fair multicasting, which is shown to be far from optimal at high-SNR values. Our first proposed scheme, which is near-optimal in terms of DoF, is the natural extension of multiserver coded caching to Gaussian channels. As we demonstrate, its finite SNR performance is not satisfactory, and thus we propose a new scheme in which the linear combination of messages is implemented in the finite field domain, and the one-shot precoding for the MISO downlink is implemented in the complex field. While this modification results in the same near-optimal DoF performance, we show that this leads to significant performance improvement at finite SNR. Finally, we extend our scheme to the previously considered cache-enabled interference channels, and moreover we provide an ergodic rate analysis of our scheme. Our results convey the important message that although directly translating schemes from the network coding ideas to wireless networks may work well at high-SNR values, careful modifications need to be considered for acceptable finite SNR performance. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Venkat Anantharam;François Baccelli;
Pages: 2808 - 2823 Abstract: We analyze a class of vector multiple access channels with additive noise, where the sum of the dimensions of the transmitted signals matches that of the received signal. We first focus on the case without power constraints, in the Poltyrev sense, using point process techniques. We find the Poltyrev capacity region for noise processes that are independent and identically distributed over channel uses. For each rate vector strictly in the Poltyrev capacity region, we study, for each subset of the transmitters, the exponent of the decay in block length of the smallest possible probability that decoding results in error for each transmitter in that subset. In the case of independent and identically distributed Gaussian noise, with arbitrary positive definite covariance matrix, we derive random coding exponents for each type of error event—these are lower bounds to the true error exponents. This also leads to random coding error exponents in the traditional power-constrained case, where the power constraint at each transmitter is defined by an arbitrary positive definite matrix. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Tibor Keresztfalvi;Amos Lapidoth;
Pages: 2824 - 2837 Abstract: Two independent data streams are to be transmitted over a noisy discrete memoryless channel with noiseless (ideal) feedback. Errors are tolerated only in the second stream, provided that they occur with vanishing probability. The rate of the error-free stream cannot, of course, exceed the channel’s zero-error feedback capacity, and nor can the sum of the streams’ rates exceed the channel’s Shannon capacity. Using a suitable coding scheme, these necessary conditions are shown to characterize all the achievable rate pairs. Planning for the worst channel behavior—as is needed to achieve zero-error communication—and planning for the typical channel behavior—as is needed to communicate near the Shannon limit—are thus not incompatible. It is further shown that feedback may be beneficial for the multiplexing problem even on channels on which it does not increase the zero-error capacity. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Longguang Li;Aslan Tchamkerten;
Pages: 2838 - 2849 Abstract: The capacity under strong asynchronism was recently shown to be essentially unaffected by the imposed decoding delay—the elapsed time between when information is available at the transmitter and when it is decoded—and the output sampling rate. This paper shows that, in contrast with capacity, the second-order term in the maximum rate expansion is sensitive to both parameters. When the receiver must locate the sent codeword exactly and therefore achieve minimum delay equal to the blocklength $n$ , the second-order term in the maximum rate expansion is of order $Theta (1/rho)$ for any sampling rate $rho =O(1/sqrt {n})$ (and $rho =omega (1/n)$ for otherwise reliable communication is impossible). Instead, if $rho =omega (1/sqrt {n})$ , then the second-order term is the same as under full sampling and is given by a standard $Theta (sqrt {n})$ term. However, if the delay constraint is only slightly relaxed to $n(1+o(1))$ , then the above order transition (for $rho =O(1/sqrt {n})$ and $rho =omega (1/sqrt {n})$ ) vanishes and the second-order term remains the same as under full sampling for any $rho =omega (1/n)$ . PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Ahmad Beirami;Robert Calderbank;Mark M. Christiansen;Ken R. Duffy;Muriel Médard;
Pages: 2850 - 2871 Abstract: Given a collection of strings, each with an associated probability of occurrence, the guesswork of each of them is their position in a list ordered from most likely to least likely, breaking ties arbitrarily. The guesswork is central to several applications in information theory: average guesswork provides a lower bound on the expected computational cost of a sequential decoder to decode successfully the transmitted message; the complementary cumulative distribution function of guesswork gives the error probability in list decoding; the logarithm of guesswork is the number of bits needed in optimal lossless one-to-one source coding; and the guesswork is the number of trials required of an adversary to breach a password protected system in a brute-force attack. In this paper, we consider memoryless string sources that generate strings consisting of independent and identically distributed characters drawn from a finite alphabet, and characterize their corresponding guesswork. Our main tool is the tilt operation on a memoryless string source. We show that the tilt operation on a memoryless string source parametrizes an exponential family of memoryless string sources, which we refer to as the tilted family of the string source. We provide an operational meaning to the tilted families by proving that two memoryless string sources result in the same guesswork on all strings of all lengths if and only if their respective categorical distributions belong to the same tilted family. Establishing some general properties of the tilt operation, we generalize the notions of weakly typical set and asymptotic equipartition property to tilted weakly typical sets of different orders. We use this new definition to characterize the large deviations for all atypical strings and characterize the volume of tilted weakly typical sets of different orders. We subsequently build on this characterization to prove large deviation bounds on guesswork and prov-de an accurate approximation of its probability mass function. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Hao-Chung Cheng;Min-Hsiu Hsieh;Marco Tomamichel;
Pages: 2872 - 2898 Abstract: We study lower bounds on the optimal error probability in classical coding over classical-quantum channels at rates below the capacity, commonly termed quantum sphere-packing bounds. Winter and Dalai have derived such bounds for classical-quantum channels; however, the exponents in their bounds only coincide when the channel is classical. In this paper, we show that these two exponents admit a variational representation and are related by the Golden–Thompson inequality, reaffirming that Dalai’s expression is stronger in general classical-quantum channels. Second, we establish a finite blocklength sphere-packing bound for classical-quantum channels, which significantly improves Dalai’s prefactor from the order of subexponential to polynomial. Furthermore, the gap between the obtained error exponent for constant composition codes and the best known classical random coding exponent vanishes in the order of $o(log n / n)$ , indicating our sphere-packing bound is almost exact in the high rate regime. Finally, for a special class of symmetric classical-quantum channels, we can completely characterize its optimal error probability without the constant composition code assumption. The main technical contributions are two converse Hoeffding bounds for quantum hypothesis testing and the saddle-point properties of error exponent functions. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Tongyang Li;Xiaodi Wu;
Pages: 2899 - 2921 Abstract: Estimation of Shannon and Rényi entropies of unknown discrete distributions is a fundamental problem in statistical property testing. In this paper, we give the first quantum algorithms for estimating $alpha $ -Rényi entropies (Shannon entropy being 1-Rényi entropy). In particular, we demonstrate a quadratic quantum speedup for Shannon entropy estimation and a generic quantum speedup for $alpha $ -Rényi entropy estimation for all $alpha geq 0$ values, including tight bounds for the Shannon entropy, the Hartley entropy ( $alpha =0$ ), and the collision entropy ( $alpha =2$ ). We also provide quantum upper bounds for estimating min-entropy ( $alpha =+infty $ ) as well as the Kullback–Leibler divergence. We complement our results with quantum lower bounds on $alpha $ -Rényi entropy estimation for all $alpha geq 0$ values. Our approach is inspired by the pioneering work of Bravyi, Harrow, and Hassidim (BHH); however, with many new technical ingredients: 1) we improve the error dependence of the BHH framework by a fine-tuned error analysis together with Montanaro’s approach to estimating the expected output of quantum subroutines for $alpha =0,1$ ; 2) we develop a proce-ure, similar to cooling schedules in simulated annealing, for general $alpha geq 0$ , and 3) in the cases of integer $alpha geq 2$ and $alpha =+infty $ , we reduce the entropy estimation problem to the $alpha $ -distinctness and $lceil log nrceil $ -distinctness problems, respectively. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Holger Boche;Minglai Cai;Ning Cai;
Pages: 2922 - 2943 Abstract: In this paper, a new model for arbitrarily varying classical-quantum channels is proposed. In this model, a jammer has side information. The communication scenario in which a jammer can select only classical inputs as a jamming sequence is considered in the first part of the paper. This situation corresponds to the standard model of arbitrarily varying classical-quantum channels. Two scenarios are considered. In the first scenario, the jammer knows the channel input, while in the second scenario the jammer knows both the channel input and the message. The transmitter and receiver share a secret random key with a vanishing key rate. The capacity for both average and maximum error criteria for both scenarios is determined in this paper. A strong converse is also proved. It is shown that all these corresponding capacities are equal, which means that additionally revealing the message to the jammer does not change the capacity. The communication scenario with a fully quantum jammer is considered in the second part of the paper. A single letter characterization for the capacity with secret random key as assistance for both average and maximum error criteria is derived in the paper. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Gaojun Luo;Xiwang Cao;Xiaojing Chen;
Pages: 2944 - 2952 Abstract: The hull of linear codes has promising utilization in coding theory and quantum coding theory. In this paper, we study the hull of generalized Reed–Solomon codes and extended generalized Reed–Solomon codes over finite fields with respect to the Euclidean inner product. Several infinite families of MDS codes with hulls of arbitrary dimensions are presented. As an application, using these MDS codes with hulls of arbitrary dimensions, we construct several new infinite families of entanglement-assisted quantum error-correcting codes with flexible parameters. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Benjamin Mark;Garvesh Raskutti;Rebecca Willett;
Pages: 2953 - 2975 Abstract: Consider observing a collection of discrete events within a network that reflect how network nodes influence one another. Such data are common in spike trains recorded from biological neural networks, interactions within a social network, and a variety of other settings. Data of this form may be modeled as self-exciting point processes, in which the likelihood of future events depends on the past events. This paper addresses the problem of estimating self-excitation parameters and inferring the underlying functional network structure from self-exciting point process data. Past work in this area was limited by strong assumptions which are addressed by the novel approach here. Specifically, in this paper we 1) incorporate saturation in a point process model which both ensures stability and models non-linear thresholding effects; 2) impose general low-dimensional structural assumptions that include sparsity, group sparsity, and low-rankness that allows bounds to be developed in the high-dimensional setting; and 3) incorporate long-range memory effects through moving average and higher-order auto-regressive components. Using our general framework, we provide a number of novel theoretical guarantees for high-dimensional self-exciting point processes that reflect the role played by the underlying network structure and long-term memory. We also provide simulations and real data examples to support our methodology and main results. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Jinchi Chen;Yulong Liu;
Pages: 2976 - 2994 Abstract: This paper studies the problem of accurately recovering a structured signal from a small number of corrupted sub-Gaussian measurements. We consider three different procedures to reconstruct signal and corruption when different kinds of prior knowledge are available. In each case, we provide conditions (in terms of the number of measurements) for stable signal recovery from structured corruption with added unstructured noise. Our results theoretically demonstrate how to choose the regularization parameters in both partially and fully penalized recovery procedures and shed some light on the relationships among the three procedures. The key ingredient in our analysis is an extended matrix deviation inequality for isotropic sub-Gaussian matrices, which implies a tight lower bound for the restricted singular value of the extended sensing matrix. Numerical experiments are presented to verify our theoretical results. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Yunwen Lei;Ürün Dogan;Ding-Xuan Zhou;Marius Kloft;
Pages: 2995 - 3021 Abstract: In this paper, we study data-dependent generalization error bounds that exhibit a mild dependency on the number of classes, making them suitable for multi-class learning with a large number of label classes. The bounds generally hold for empirical multi-class risk minimization algorithms using an arbitrary norm as the regularizer. Key to our analysis is new structural results for multi-class Gaussian complexities and empirical $ell _infty $ -norm covering numbers, which exploit the Lipschitz continuity of the loss function with respect to the $ell _{2}$ - and $ell _infty $ -norm, respectively. We establish data-dependent error bounds in terms of the complexities of a linear function class defined on a finite set induced by training examples, for which we show tight lower and upper bounds. We apply the results to several prominent multi-class learning machines and show a tighter dependency on the number of classes than the state of the art. For instance, for the multi-class support vector machine of Crammer and Singer (2002), we obtain a data-dependent bound with a logarithmic dependency, which is a significant improvement of the previous square-root dependency. The experimental results are reported to verify the effectiveness of our theoretical findings. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Tony Yaacoub;George V. Moustakides;Yajun Mei;
Pages: 3022 - 3033 Abstract: We propose an optimal sequential methodology for obtaining confidence intervals for a binomial proportion $theta$ . Assuming that an independent and identically distributed sequence of Bernoulli ( $theta$ ) trials is observed sequentially, we are interested in designing: 1) a stopping time $T$ that will decide the best time to stop sampling the process and 2) an optimum estimator $hat{{theta}}_{{T}}$ that will provide the optimum center of the interval estimate of $theta$ . We follow a semi-Bayesian approach, where we assume that there exists a prior distribution for $theta$ , and our goal is to minimize the average number of samples while we guarantee a minimal specified coverage probability level. The solution is obtained by applying standard optimal stopping theory and computing the optimum pair $(T,hat{{theta }}_{{T}})$ numerically. Regarding the optimum stopping time component $T$ , we demonstrate that it enjoys certain very interesting characteristics not commonly encountered in solutions of other classical optimal stopping problems. In particular, we prove that, for a particular prior (beta density), the optimum stopping time is always bounded from above and below; it needs to first accumulate a sufficient amount of information before deciding whether or not to stop, and it will always terminate before some finite deterministic time. We also conjecture that these properti-s are present with any prior. Finally, we compare our method with the optimum fixed-sample-size procedure as well as with existing alternative sequential schemes. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Jie Ding;Jiawei Zhou;Vahid Tarokh;
Pages: 3034 - 3067 Abstract: We develop a methodology (referred to as kinetic prediction) for predicting time series undergoing unknown changes in their data generating distributions. Based on Kolmogorov-Tikhomirov’s ${varepsilon }$ -entropy, we propose a concept called ${varepsilon }$ -predictability that quantifies the size of a model class (which can be parametric or nonparametric) and the maximal number of abrupt structural changes that guarantee the achievability of asymptotically optimal prediction. Moreover, for parametric distribution families, we extend the aforementioned kinetic prediction with discretized function spaces to its counterpart with continuous function spaces, and propose a sequential Monte Carlo-based implementation. We also extend our methodology for predicting smoothly varying data generating distributions. Under reasonable assumptions, we prove that the average predictive performance converges almost surely to the oracle bound, which corresponds to the case that the data generating distributions are known in advance. The results also shed some light on the so called “prediction-inference dilemma.” Various examples and numerical results are provided to demonstrate the wide applicability of our methodology. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Felix Abramovich;Vadim Grinshtein;
Pages: 3068 - 3079 Abstract: We consider high-dimensional binary classification by sparse logistic regression. We propose a model/feature selection procedure based on penalized maximum likelihood with a complexity penalty on the model size and derive the non-asymptotic bounds for its misclassification excess risk. To assess its tightness, we establish the corresponding minimax lower bounds. The bounds can be reduced under the additional low-noise condition. The proposed complexity penalty is remarkably related to the Vapnik-Chervonenkis-dimension of a set of sparse linear classifiers. Implementation of any complexity penalty-based criterion, however, requires a combinatorial search over all possible models. To find a model selection procedure computationally feasible for high-dimensional data, we extend the Slope estimator for logistic regression and show that under an additional weighted restricted eigenvalue condition it is rate-optimal in the minimax sense. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Narayanaswamy Balakrishnan;Elena Castilla;Nirian Martín;Leandro Pardo;
Pages: 3080 - 3096 Abstract: This paper develops a new family of estimators, the minimum density power divergence estimators (MDPDEs), for the parameters of the one-shot device model as well as a new family of test statistics, Z-type test statistics based on MDPDEs, for testing the corresponding model parameters. The family of MDPDEs contains as a particular case the maximum likelihood estimator (MLE) considered in Balakrishnan and Ling (2012). Through a simulation study, it is shown that some MDPDEs have a better behavior than the MLE in terms of robustness. At the same time, it can be seen that some Z-type tests based on MDPDEs have a better behavior than the classical Z-test statistic in terms of robustness, as well. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Yanjun Li;Kiryung Lee;Yoram Bresler;
Pages: 3097 - 3123 Abstract: Blind gain and phase calibration (BGPC) is a bilinear inverse problem involving the determination of unknown gains and phases of the sensing system, and the unknown signal, jointly. BGPC arises in numerous applications, e.g., blind albedo estimation in inverse rendering, synthetic aperture radar autofocus, and sensor array auto-calibration. In some cases, sparse structure in the unknown signal alleviates the ill-posedness of BGPC. Recently, there has been renewed interest in solutions to BGPC with careful analysis of error bounds. In this paper, we formulate BGPC as an eigenvalue/eigenvector problem and propose to solve it via power iteration, or in the sparsity or joint sparsity case, via truncated power iteration. Under certain assumptions, the unknown gains, phases, and the unknown signal can be recovered simultaneously. Numerical experiments show that power iteration algorithms work not only in the regime predicted by our main results, but also in regimes where theoretical analysis is limited. We also show that our power iteration algorithms for BGPC compare favorably with competing algorithms in adversarial conditions, e.g., with noisy measurement or with a bad initial estimate. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Abiy Tasissa;Rongjie Lai;
Pages: 3124 - 3144 Abstract: The Euclidean distance geometry problem arises in a wide variety of applications, from determining molecular conformations in computational chemistry to localization in sensor networks. When the distance information is incomplete, the problem can be formulated as a nuclear norm minimization problem. In this paper, this minimization program is recast as a matrix completion problem of a low-rank $r$ Gram matrix with respect to a suitable basis. The well-known restricted isometry property cannot be satisfied in this scenario. Instead, a dual basis approach is introduced to theoretically analyze the reconstruction problem. If the Gram matrix satisfies certain coherence conditions with parameter $nu $ , the main result shows that the underlying configuration of $n$ points can be recovered with very high probability from $O(nrnu log ^{2}(n))$ uniformly random samples. Computationally, simple and fast algorithms are designed to solve the Euclidean distance geometry problem. Numerical tests on different 3-D data and protein molecules validate the effectiveness and efficiency of the proposed algorithms. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Lin Zhou;Vincent Y. F. Tan;Mehul Motani;
Pages: 3145 - 3159 Abstract: The rate-distortion saddle-point problem considered by Lapidoth (1997) consists in finding the minimum rate to compress an arbitrary ergodic source when one is constrained to use a random Gaussian codebook and minimum (Euclidean) distance encoding is employed. We extend Lapidoth’s analysis in several directions in this paper. First, we consider refined asymptotics. In particular, when the source is stationary and memoryless, we establish the second-order, moderate, and large deviation asymptotics of the problem. Second, by random Gaussian codebook, Lapidoth referred to a collection of random codewords, each of which is drawn independently and uniformly from the surface of an $n$ -dimensional sphere. To be more precise, we term this as a spherical codebook. We also consider i.i.d. Gaussian codebooks in which each random codeword is drawn independently from a product Gaussian distribution. We derive the second-order, moderate, and large deviation asymptotics when i.i.d. Gaussian codebooks are employed. In contrast to the recent work on the channel coding counterpart by Scarlett, Tan, and Durisi (2017), the dispersions for spherical and i.i.d. Gaussian codebooks are identical. The ensemble excess-distortion exponents for both spherical and i.i.d. Gaussian codebooks are established for all rates. Furthermore, we show that the i.i.d. Gaussian codebook has a strictly larger excess-distortion exponent than its spherical counterpart for any rate greater than the ensemble rate-distortion function derived by Lapidoth. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Carlos Ochoa;Gonzalo Navarro;
Pages: 3160 - 3164 Abstract: Irreducible grammars are a class of context-free grammars with well-known representatives, such as Repair (with a few tweaks), Longest Match, Greedy, and Sequential. We show that a grammar-based compression method described by Kieffer and Yang (2000) is upper bounded by the high-order empirical entropy of the string when the underlying grammar is irreducible. Specifically, given a string $S$ over an alphabet of size $sigma $ , we prove that if the underlying grammar is irreducible, then the length of the binary code output by this grammar-based compression method is bounded by $ S H_{k}(S) + o( S log sigma)$ for any $kin o(log _sigma S )$ , where $H_{k}(S)$ is the $k$ -order empirical entropy of $S$ . This is the first bound encompassing the whole class of irreducible grammars in terms of the high-order empirical entropy, with coefficient 1. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Patrick Ah-Fat;Michael Huth;
Pages: 3165 - 3182 Abstract: The purpose of secure multi-party computation is to enable protocol participants to compute a public function of their private inputs while keeping their inputs secret, without resorting to any trusted third party. However, opening the public output of such computations inevitably reveals some information about the private inputs. We propose a measure generalizing both Rényi entropy and $g$ -entropy so as to quantify this information leakage. In order to control and restrain such information flows, we introduce the notion of function substitution, which replaces the computation of a function that reveals sensitive information with that of an approximate function. We exhibit theoretical bounds for the privacy gains that this approach provides and experimentally show that this enhances the confidentiality of the inputs while controlling the distortion of computed output values. Finally, we investigate the inherent compromise between accuracy of computation and privacy of inputs and we demonstrate how to realize such optimal trade-offs. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Qiwen Wang;Mikael Skoglund;
Pages: 3183 - 3197 Abstract: We consider the problem of private information retrieval (PIR) and symmetric private information retrieval (SPIR) from replicated databases with colluding servers, in the presence of Byzantine adversaries and eavesdroppers. Specifically, there are $K$ messages replicatively stored at $N$ databases. A user wants to retrieve one message by communicating with the databases, without revealing the identity of the message retrieved. For $T$ -colluding databases, any $T$ out of $N$ databases may communicate their interactions with the user to guess the identity of the requested message. We consider the situation where the communication system can be vulnerable to attachers, namely, there is an adversary in the system that can tap in on or even try to corrupt the communication. The capacity is defined as the maximum number of information bits of the desired message retrieved per downloaded bit. For SPIR, it is further required that the user learns nothing about the other $K-1$ messages in the database. Three types of adversaries are considered: a Byzantine adversary who can overwrite the transmission of any $B$ servers to the user; a passive eavesdropper who can tap in on the incoming and outgoing transmissions of any $E$ servers; and a combination of both -- an adversary who can tap in on a set of any PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Qiwen Wang;Hua Sun;Mikael Skoglund;
Pages: 3198 - 3214 Abstract: We consider the problem of private information retrieval (PIR) with colluding servers and eavesdroppers (abbreviated as ETPIR). The ETPIR problem is comprised of ${K}$ messages and ${N}$ servers where each server stores all ${K}$ messages, a user who wants to retrieve one of the ${K}$ messages without revealing the desired message index to any set of ${T}$ colluding servers, and an eavesdropper who can listen to the queries and answers of any ${E}$ servers but is prevented from learning any information about the messages. The information theoretic capacity of ETPIR is defined to be the maximum number of desired message symbols retrieved privately per information symbol downloaded. We show that the capacity of ETPIR is $ {C} = ({1}- ({{E}}/{{N}})) ({1} + ({ {T}- {E}}/{ {N}- {E}}) + cdots + (({ {T}-boldsymbol {E}}/{ {N}-{E}}))^{ {K}-{1}})^{-{1}}$ when $ {E} < {T}$ , and $ {C} = ({1} - ({ {E}}/{ {N}}))$ when $ {E} geq {T}$ . To achieve the capacity, the servers need to share a common random variable (independent of the messages), and its size must be at least $({{E}}/{ {N}}) cdot ({{1}}/{ {C}})$ symbols per message symbol. Otherwise, with less amount of shared com-on randomness, ETPIR is not feasible and the capacity reduces to zero. An interesting observation is that the ETPIR capacity expression takes different forms in two regimes. When $ {E} < {T}$ , the capacity equals the inverse of a sum of a geometric series with ${K}$ terms and decreases with ${K}$ ; this form is typical for capacity expressions of PIR. When ${E} geq {T}$ , the capacity does not depend on $ {K}$ , a typical form for capacity expressions of SPIR (symmetric PIR, which further requires data-privacy, i.e., the user learns no information about other undesired messages); the capacity does not depend on $ {T}$ either. In addition, the ETPIR capacity result includes multiple previous PIR and SPIR capacity results as special cases. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Yi-Peng Wei;Karim Banawan;Sennur Ulukus;
Pages: 3215 - 3232 Abstract: We consider the problem of private information retrieval (PIR) from $N$ non-colluding and replicated databases when the user is equipped with a cache that holds an uncoded fraction $r$ from each of the $K$ stored messages in the databases. We assume that the databases are unaware of the cache content. We investigate $D^{*}(r)$ the optimal download cost normalized with the message size as a function of $K$ , $N$ , and $r$ . For a fixed $K$ and $N$ , we develop an inner bound (converse bound) for the $D^{*}(r)$ curve. The inner bound is a piece-wise linear function in $r$ that consists of $K$ line segments. For the achievability, we develop explicit schemes that exploit the cached bits as side information to achieve $K-1$ non-degenerate corner points. These corner points differ in the number of cached bits that are used to generate the one-side information equation. We obtain an outer bound (achievability) for any caching ratio by memory sharing between these corner points. Thus, the outer bound is also a piece-wise linear function in $r$ that consists of $K$ line segments. The inner and the outer bounds match in general for the cases of very low-caching ratio and very high-caching ratio. As a corollary, we fully characterize the optimal download cost caching ratio tradeoff for $K=3$ . For general $K$ , $N$ , and $r$ , we show that the largest gap between the achievability and the converse bounds is 1/6. Our results show that the download cost can be reduced beyond memory sharing if the databases are unaware of the cached content. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Maki Yoshida;Satoshi Obana;
Pages: 3233 - 3245 Abstract: A $d$ -multiplicative secret sharing ( $d$ -MSS) scheme allows the players to multiply $d$ shared secrets without recovering the secrets by converting their shares locally into an additive sharing of the product. It has been proved that the $d$ -MSS among $n$ players is possible if and only if no $d$ unauthorized sets of players cover the whole set of players (type $Q_{d}$ ). Although this result implies some limitations on SS in the context of MPC, the $d$ -multiplicative property is still useful for simplifying complex tasks of MPC by computing the product of $d$ field elements directly and non-interactively without any setup. This paper aims to improve the usefulness of the $d$ -MSS by enhancing the security against malicious adversaries. First, we introduce the notion of verifiably multiplicative SS, verifiably MSS for short, which is mainly formalized for detecting malicious behaviors. Informally, an SS scheme is verifiably $d$ -multiplicative if the scheme is $d$ -multiplicative and further enables the players to loca-ly generate a share of a proof that the summed value is correct (i.e., the product of $d$ shared secrets). Secondly, we prove that there is no error-free verifiably MSS scheme whose decoder of the proof is additive, and that by accepting an error probability that can be chosen arbitrarily, there exists a verifiably $d$ -MSS scheme realizing a given access structure if and only if the access structure is of type $Q_{d}$ . In the proposed construction, each share of a proof consists of only two field elements. This result means that we can efficiently achieve the optimal resiliency of the standard $d$ -MSS even against malicious adversaries. We note that by allowing a general class of decoders that includes a linear one, there is an error-free verifiably $d$ -MSS scheme if the access structure is of type $Q_{d+1}$ . Finally, we generalize the $d$ -multiplicative property to a $d$ -or-less version where the number $d'$ of multiplied secrets with $d'leq d$ is not known in advance. We show that a $d$ -or-less MSS scheme can be constructed from any $d$ -MSS scheme of the same PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Paulo Ricardo Branco da Silva;Danilo Silva;
Pages: 3246 - 3260 Abstract: Lattice codes are elegant and powerful structures that not only achieve the capacity of the additive white Gaussian noise (AWGN) channel but are also a key ingredient to many multiterminal schemes that exploit linearity properties. However, constructing lattice codes that can realize these benefits with low complexity is still a challenging problem. In this paper, efficient encoding and decoding algorithms are proposed for multilevel binary low-density parity-check (LDPC) lattices constructed via Construction $text{D}'$ whose complexity is linear in the total number of coded bits. Moreover, a generalization of Construction $text{D}'$ is proposed, which relaxes some of the nesting constraints on the parity-check matrices of the component codes, leading to a simpler and improved design. Based on this construction, low-complexity multilevel LDPC lattices are designed whose performance under multistage decoding is comparable to that of polar lattices and close to that of low-density lattice codes on the power-unconstrained AWGN channel. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Kaniska Mohanty;Mahesh K. Varanasi;
Pages: 3261 - 3277 Abstract: The generalized degrees of freedom (GDoF) of the two-user multiple-input multiple-output interference channel is studied under the assumption of delayed channel state information at the transmitters. In particular, with $M$ antennas at each transmitter and $N$ antennas at each receiver, and in the non-trivial case when $M>N$ (with the case of $Mleq N$ not needing any CSIT), new lower and upper bounds on the symmetric GDoF are obtained that are parameterized by $alpha $ , which links the interference-to-noise ratio (INR) and the signal-to-noise ratio (SNR) at each receiver via $mathrm {INR}=mathrm {SNR}^{{alpha }}$ . A new upper bound for the symmetric GDoF is obtained by maximizing a bound on the weighted sum rate, which in turn is obtained from a combination of genie-aided side-information and an extremal inequality. The maximum weighted sum rate in the high SNR regime is shown to occur when the transmit covariance matrix at each transmitter is full rank. An achievability scheme is developed that is based on block-Markov encoding and backward decoding, and which incorporates channel statistics through interference quantization and digital multicasting. This symmetric GDoF lower bound is maximized separately for different ranges of ${alpha }$ , by optimizing the transmit power levels in the achievability scheme separately in the very weak $[0leq {alpha }leq ({1}/{2})]$ , w-ak $[({1}/{2}) < {alpha }leq 1]$ , and strong $({alpha }>1)$ interference regimes. The lower and upper bounds coincide when ${alpha }geq [({{r}+1})/({{r}+2})]$ , where ${r}=min (2,{M}/{N})$ , thus characterizing the symmetric GDoF completely for strong interference and a range of values of weak interference. It is also shown that treating interference as noise is strictly sub-optimal from a GDoF perspective even when the interference is very weak. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Cynthia Rush;Ramji Venkataramanan;
Pages: 3278 - 3303 Abstract: Sparse superposition codes, or sparse regression codes, are a recent class of codes for reliable communication over the AWGN channel at rates approaching the channel capacity. Approximate message passing (AMP) decoding, a computationally efficient technique for decoding SPARCs, has been proven to be asymptotically capacity-achieving for the AWGN channel. In this paper, we refine the asymptotic result by deriving a large deviation bound on the probability of an AMP decoding error. This bound gives insight into the error performance of the AMP decoder for large but finite problem sizes, giving an error exponent as well as guidance on how the code parameters should be chosen at finite block lengths. For an appropriate choice of code parameters, we show that for any fixed rate less than the channel capacity, the decoding error probability decays exponentially in $n/(log n)^{2T}$ , where $T$ , the number of AMP iterations required for successful decoding, is bounded in terms of the gap from capacity. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)

Authors:
Yansheng Wu;Qin Yue;Fengwei Li;
Pages: 3304 - 3314 Abstract: Let $Bbb F_{p}$ be a finite field with $p$ elements, where $p$ is a prime. Let $N ge 2$ be an integer and $d$ be the least positive integer satisfying $p^{d} equiv -1 pmod N$ . Let $q = p^{2sd}$ for some integers $s$ . In some special cases, we obtain the explicit evaluation of the following exponential sums: $S(a,b)=sum _{xin Bbb F_{q}^{*}}zeta _{p}^{ mathrm {Tr}_{q/p}(ax^{(({q-1})/{N})}+bx)}$ . As applications, Walsh spectrums of the monomial functions $mathrm {Tr}_{q/p}(x^{(({q-1})/{N})})$ in three cases are investigated. Our results show that Walsh spectrums of the monomial functions have at most four, five, or seven distinct values. Furthermore, three families of the monomial functions with three-valued Walsh spectrums are presented, see Corollaries 12, 21, 31, and 32. Consequently, certain previously known results by Li and Yue and Moisio are extended. PubDate:
May 2019
Issue No:Vol. 65, No. 5 (2019)