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

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

Authors:
Lei Yu;Vincent Y. F. Tan;
Pages: 1321 - 1344 Abstract: A coupling of two distributions $P_{X}$ and $P_{Y}$ is a joint distribution $P_{XY}$ with marginal distributions equal to $P_{X}$ and $P_{Y}$ . Given marginals $P_{X}$ and $P_{Y}$ and a real-valued function $f$ of the joint distribution $P_{XY}$ , what is its minimum over all couplings $P_{XY}$ of $P_{X}$ and $P_{Y}$ ' We study the asymptotics of such coupling problems with different $f$ ’s and with $X$ and $Y$ replaced by $X^{n}=(X_{1},ldots ,X_{n})$ and $Y^{n}=(Y_{1},ldots ,Y_{n})$ where $X_{i}$ and $Y_{i}$ are i.i.d. copies of random variables PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Shengtian Yang;Rui Xu;Jun Chen;Jian-Kang Zhang;
Pages: 1345 - 1360 Abstract: Every channel can be expressed as a convex combination of deterministic channels with each deterministic channel corresponding to one particular intrinsic state. Such convex combinations are, in general, not unique, each giving rise to a specific intrinsic-state distribution. In this paper, we study the maximum and minimum capacities of a channel when the realization of its intrinsic state is causally available at the encoder and/or the decoder. Several conclusive results are obtained for binary-input channels and binary-output channels. By-products of our investigation include a generalization of the Birkhoff–von Neumann theorem and a condition on the uselessness of causal state information at the encoder. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Venkat Anantharam;Amin Gohari;Chandra Nair;
Pages: 1361 - 1371 Abstract: Marton’s inner bound is the best known achievable rate region for a general two-receiver discrete memoryless broadcast channel. In this paper, we establish improved bounds on the cardinalities of the auxiliary random variables appearing in this inner bound to the true rate region. We combine a perturbation technique, along with a representation using concave envelopes of information-theoretic functions that involve the use of auxiliary random variables, to achieve this improvement. The new cardinality bounds lead to a proof that a randomized-time-division strategy achieves every rate triple in Marton’s region for binary input broadcast channels. This extends the result by Hajek and Pursley which showed that the Cover-van der Muelen region was exhausted by the randomized-time-division strategy. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Chandra Nair;David Ng;
Pages: 1372 - 1374 Abstract: We establish that the multi-letter extension of the Han–Kobayashi achievable region with temporally correlated vector Gaussian inputs matches the Han–Kobayashi achievable region with scalar Gaussian inputs for the Gaussian interference channel. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Mokshay Madiman;Farhad Ghassemi;
Pages: 1375 - 1386 Abstract: We initiate the study of the Stam region, defined as the subset of the positive orthant in ${R}^{2^{n}-1}$ that arises from considering the entropy powers of subset sums of $n$ independent random vectors in a Euclidean space of finite dimension. We show that the class of fractionally superadditive set functions provides an outer bound to the Stam region, resolving a conjecture of Barron and Madiman. On the other hand, the entropy power of a sum of independent random vectors is not supermodular in any dimension. We also develop some qualitative properties of the Stam region, showing for instance that its closure is a logarithmically convex cone. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Arnaud Marsiglietti;James Melbourne;
Pages: 1387 - 1396 Abstract: Using a sharp version of the reverse Young inequality, and a Rényi entropy comparison result due to Fradelizi, Madiman, and Wang (2016), the authors derive Rényi entropy power inequalities for log-concave random vectors when Rényi parameters belong to [0, 1]. Furthermore, the estimates are shown to be sharp up to absolute constants. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Shaofeng Zou;Georgios Fellouris;Venugopal V. Veeravalli;
Pages: 1397 - 1412 Abstract: The problem of quickest change detection under transient dynamics is studied, where the change from the initial distribution to the final persistent distribution does not happen instantaneously, but after a series of transient phases. The observations within the different phases are generated by different distributions. The objective is to detect the change as quickly as possible, while controlling the average run length (ARL) to false alarm, when the durations of the transient phases are completely unknown. Two algorithms are considered: the dynamic Cumulative Sum (CuSum) algorithm, proposed in earlier work, and a newly constructed weighted dynamic CuSum algorithm. Both algorithms admit recursions that facilitate their practical implementation, and they are adaptive to the unknown transient durations. Specifically, their asymptotic optimality is established with respect to both Lorden’s and Pollak’s criteria as the ARL to false alarm and the durations of the transient phases go to infinity at any relative rate. Numerical results are provided to demonstrate the adaptivity of the proposed algorithms and to validate the theoretical results. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Alexander G. Tartakovsky;
Pages: 1413 - 1429 Abstract: The paper addresses a sequential changepoint detection problem for a general stochastic model, assuming that the observed data may be non-i.i.d. (i.e., dependent and non-identically distributed) and prior distribution of the change point is arbitrary. Tartakovsky and Veeravalli (2005), Baron and Tartakovsky (2006), and, more recently, Tartakovsky (2017) developed a general asymptotic theory of changepoint detection for non-i.i.d. stochastic models, assuming certain stability of the log-likelihood ratio process, in the case of simple hypotheses when both pre-change and post-change models are completely specified. However, in most applications, the post-change distribution is not completely known. In the present paper, we generalize previous results to the case of parametric uncertainty, assuming that the parameter of the post-change distribution is unknown. We introduce two detection rules based on mixtures–the mixture Shiryaev rule and the mixture Shiryaev–Roberts rule–and study their asymptotic properties in the Bayesian context. In particular, we provide sufficient conditions under which these rules are first-order asymptotically optimal, minimizing moments of the delay to detection as the probability of false alarm approaches zero. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Dong Yin;Ramtin Pedarsani;Yudong Chen;Kannan Ramchandran;
Pages: 1430 - 1451 Abstract: In this paper, we consider the mixture of sparse linear regressions model. Let $boldsymbol {beta }^{(1)},ldots, boldsymbol {beta }^{(L)}in mathbb {C} ^{n}$ be $L $ unknown sparse parameter vectors with a total of $K $ non-zero elements. Noisy linear measurements are obtained in the form $y_{i} = boldsymbol {x}_{i} ^{mathrm{ H}} boldsymbol {beta }^{(ell _{i})} + w_{i}$ , each of which is generated randomly from one of the sparse vectors with the label $ell _{i} $ unknown. The goal is to estimate the parameter vectors efficiently with low sample and computational costs. This problem presents significant challenges as one needs to simultaneously solve the demixing problem of recovering the labels $ell _{i} $ as well as the estimation problem of recovering the sparse vectors $boldsymbol {beta }^{(ell)} $ . Our solution to the problem leverages the connection between modern coding theory and statistical inference. We introduce a new algorithm, Mixed-Coloring, which samples the mixture strategically using query vectors $boldsymbol {x}_{i} $ constructed based on ideas from sparse graph codes. Our novel code design allows for both efficient demixing and parameter estimation. To find $K$ non-zero elements, it is clear that we need at least $Theta (K)$ measurements, and thus the time complexity is at least $Theta (K)$ . In the noiseless setting, for a constant number of sparse parameter vectors, our algorithm achieves the order-optimal sample and time complexities of $Theta (K)$ . In the presence of Gaussian noise,1 for the problem with two parameter vectors (i.e., $L = 2$ ), we show that the Robust Mixed-Coloring algorithm achieves near-optimal $Theta (K mathop {mathrm {polylog}}nolimits (n))$ sample and time complexities. When $K = mathcal {O}(n^{alpha })$ for some constant $alpha in (0,1)$ (i.e., $K$ is sublinear in $n$ ), we can achieve sample and time complexities both sublinear in the ambient dimension. In one of our experiments, to recover a mixture of two regressions with dimension $n = 500$ and sparsity $K = 50$ , our algorithm is more than 300 times faster than EM algorithm, with about one third of its sample cost.1The proposed algorithm works even when the noise is non-Gaussian in nature, but the guarantees on sample and time complexities are difficult to obtain. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Andreas Elsener;Sara van de Geer;
Pages: 1452 - 1472 Abstract: Many statistical estimation procedures lead to nonconvex optimization problems. Algorithms to solve these problems are often guaranteed to output a stationary point of the optimization problem. Oracle inequalities are an important theoretical instrument to assess the statistical performance of an estimator. Oracle results have focused on the theoretical properties of the uncomputable (global) minimum or maximum. In this paper, a general framework used for convex optimization problems to derive oracle inequalities for stationary points is extended. A main new ingredient of these oracle inequalities is that they are sharp: they show closeness to the best approximation within the model plus a remainder term. We apply this framework to different estimation problems. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Hao Henry Zhou;Garvesh Raskutti;
Pages: 1473 - 1492 Abstract: Consider a multi-variate time series ${(X_{t})}_{t=0}^{T}$ , where $X_{t} in mathbb {R}^{d}$ which may represent spike train responses for multiple neurons in a brain, crime event data across multiple regions, and many others. An important challenge associated with these time series models is to estimate an influence network between the $d$ variables, especially when $d$ is large, meaning we are in the high-dimensional setting. Prior work has focused on parametric vector auto-regressive models. However, parametric approaches are somewhat restrictive in practice. In this paper, we use the non-parametric sparse additive model (SpAM) framework to address this challenge. Using a combination of $beta $ and $phi $ -mixing properties of Markov chains and empirical process techniques for reproducing kernel Hilbert spaces (RKHSs), we provide upper bounds on mean-squared error in terms of the sparsity $s$ , the logarithm of the dimension $log ~d$ , the number of time points $T$ , and the smoothness of the RKHSs. Our rates are sharp up to logarithm factors in many cases. We also provide numerical experiments that support our theoretical results and display the potential advantages of using our non-parametric SpAM framework for a Chicago crime data set. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Raymond W. Yeung;Ali Al-Bashabsheh;Chao Chen;Qi Chen;Pierre Moulin;
Pages: 1493 - 1511 Abstract: Let $X_{i}, i~in V$ form a Markov random field (MRF) represented by an undirected graph $G = (V,E)$ , and $V'$ be a subset of $V$ . We determine the smallest graph that can always represent the subfield $X_{i}, i~in V'$ as an MRF. Based on this result, we obtain a necessary and sufficient condition for a subfield of a Markov tree to be also a Markov tree. When $G$ is a path so that $X_{i}, i~in V$ form a Markov chain, it is known that the $I$ -Measure is always nonnegative (Kawabata and Yeung in 1992). We prove that Markov chain is essentially the only MRF such that the $I$ -Measure is always nonnegative. By applying our characterization of the smallest graph representation of a subfield of an MRF, we develop a recursive approach for constructing information diagrams for MRFs. Our work is built on the set-theoretic characterization of an MRF (Yeung et al. in 2002). PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Shahab Asoodeh;Mario Diaz;Fady Alajaji;Tamás Linder;
Pages: 1512 - 1534 Abstract: We investigate the problem of estimating a random variable $Y$ under a privacy constraint dictated by another correlated random variable $X$ . When $X$ and $Y$ are discrete, we express the underlying privacy-utility tradeoff in terms of the privacy-constrained guessing probability ${mathcal {h}}(P_{XY}, varepsilon)$ , and the maximum probability $mathsf {P}_{mathsf {c}}(Y Z)$ of correctly guessing $Y$ given an auxiliary random variable $Z$ , where the maximization is taken over all $P_{Z Y}$ ensuring that $mathsf {P}_{mathsf {c}}(X Z)leq varepsilon $ for a given privacy threshold $varepsilon geq 0$ . We prove that ${mathcal {h}}(P_{XY}, cdot)$ is concave and piecewise linear, which allows us to derive its expression in closed form for any $varepsilon $ when $X$ and $Y$ are binary. In the non-binary case, we derive ${mathcal {h}}(P_{XY}, -arepsilon)$ in the high-utility regime (i.e., for sufficiently large, but nontrivial, values of $varepsilon $ ) under the assumption that $Y$ and $Z$ have the same alphabets. We also analyze the privacy-constrained guessing probability for two scenarios in which $X$ , $Y$ , and $Z$ are binary vectors. When $X$ and $Y$ are continuous random variables, we formulate the corresponding privacy-utility tradeoff in terms of ${mathsf {sENSR}}(P_{XY}, varepsilon)$ , the smallest normalized minimum mean squared-error (mmse) incurred in estimating $Y$ from a Gaussian perturbation $Z$ . Here, the minimization is taken over a family of Gaussian perturbations $Z$ for which the mmse of $f(X)$ given $Z$ is within a factor $1- varepsilon $ from the variance of $f(X)$ for any non-constant real-valued function PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Michael Kohler;Adam Krzyżak;
Pages: 1535 - 1546 Abstract: Uncertainty quantification of a technical system can be done using density estimation. We usually start with a stochastic model, which is fitted to the technical system, and the density estimation is done using data from this stochastic model. However, in any application, such a stochastic model will not be perfect, and the estimation of the density should take into account the inadequacy of the stochastic model. In this paper, we show how observed data of the real system together with an imperfect simulation model can be used to derive confidence bands for the density of the technical system. Our main result is that the newly introduced confidence bands allow to derive lower and upper bounds on the probability of intervals in the technical system. Furthermore, we present an upper bound on the area of the confidence band in case of a smooth density. The results are illustrated by applying the estimates to simulated and real data. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Praneeth Narayanamurthy;Namrata Vaswani;
Pages: 1547 - 1577 Abstract: Dynamic robust principal component analysis (PCA) refers to the dynamic (time-varying) extension of robust PCA (RPCA). It assumes that the true (uncorrupted) data lie in a low-dimensional subspace that can change with time, albeit slowly. The goal is to track this changing subspace over time in the presence of sparse outliers. We develop and study a novel algorithm, which we call simple-ReProCS, based on the recently introduced Recursive Projected Compressive Sensing (ReProCS) framework. This paper provides the first guarantee for dynamic RPCA that holds under weakened versions of standard RPCA assumptions, slow subspace change, and a lower bound assumption on most outlier magnitudes. Our result is significant because: 1) it removes the strong assumptions needed by the two previous complete guarantees for ReProCS-based algorithms; 2) it shows that it is possible to achieve significantly improved outlier tolerance, compared with all existing RPCA or dynamic RPCA solutions by exploiting the above-mentioned two simple extra assumptions; and 3) it proves that simple-ReProCS is online (after initialization), fast, and, has near-optimal memory complexity. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Ahmed Elzanaty;Andrea Giorgetti;Marco Chiani;
Pages: 1578 - 1588 Abstract: One of the key issues in the acquisition of sparse data by means of compressed sensing is the design of the measurement matrix. Gaussian matrices have been proven to be information-theoretically optimal in terms of minimizing the required number of measurements for sparse recovery. In this paper, we provide a new approach for the analysis of the restricted isometry constant (RIC) of finite dimensional Gaussian measurement matrices. The proposed method relies on the exact distributions of the extreme eigenvalues for Wishart matrices. First, we derive the probability that the restricted isometry property is satisfied for a given sufficient recovery condition on the RIC, and propose a probabilistic framework to study both the symmetric and asymmetric RICs. Then, we analyze the recovery of compressible signals in noise through the statistical characterization of stability and robustness. The presented framework determines limits on various sparse recovery algorithms for finite size problems. In particular, it provides a tight lower bound on the maximum sparsity order of the acquired data allowing signal recovery with a given target probability. Also, we derive simple approximations for the RICs based on the Tracy–Widom distribution. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Xin Jiang Hunt;Patricia Reynaud-Bouret;Vincent Rivoirard;Laure Sansonnet;Rebecca Willett;
Pages: 1589 - 1613 Abstract: Sparse linear inverse problems appear in a variety of settings, but often the noise contaminating observations cannot accurately be described as bounded by or arising from a Gaussian distribution. Poisson observations in particular are a characteristic feature of several real-world applications. Previous work on sparse Poisson inverse problems encountered several limiting technical hurdles. This paper describes a novel alternative analysis approach for sparse Poisson inverse problems that 1) sidesteps the technical challenges present in previous work, 2) admits estimators that can readily be computed using off-the-shelf LASSO algorithms, and 3) hints at a general framework for broad classes of noise in sparse linear inverse problems. At the heart of this new approach lies a weighted LASSO estimator for which data-dependent weights are based on Poisson concentration inequalities. Unlike previous analyses of the weighted LASSO, the proposed analysis depends on conditions which can be checked or shown to hold in general settings with high probability. 2000 Math Subject Classification: 60E15, 62G05, 62G08, and 94A12. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Simon R. Blackburn;Jessica Claridge;
Pages: 1614 - 1625 Abstract: In 2010, Silva et al. studied certain classes of finite-field matrix channels in order to model random linear network coding where exactly $t$ random errors are introduced. In this paper, we consider a generalization of these matrix channels where the number of errors is not required to be constant, indeed the number of errors may follow any distribution. We show that a capacity-achieving input distribution can always be taken to have a very restricted form (the distribution should be uniform given the rank of the input matrix). This result complements, and is inspired by a paper of Nobrega et al., which establishes a similar result for a class of matrix channels that model network coding with link erasures. Our result shows that the capacity of our channels can be expressed as maximization over probability distributions on the set of possible ranks of input matrices: a set of linear rather than exponential size. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Urs Niesen;Shrinivas Kudekar;
Pages: 1626 - 1638 Abstract: Communication in integrated circuits faces two major impediments: inter-wire capacitive coupling and noise. Coding can be used to address both these problems. So-called crosstalk-avoidance codes mitigate capacitive coupling, and traditional error-correction codes introduce resilience against channel errors. Unfortunately, crosstalk-avoidance and error-correction codes cannot be combined in a straightforward manner. On the one hand, crosstalk-avoidance encoding followed by error-correction encoding destroys the crosstalk-avoidance property. On the other hand, error-correction encoding followed by crosstalk-avoidance encoding causes the crosstalk-avoidance decoder to fail in the presence of errors. Existing approaches circumvent this difficulty by using additional bus wires to protect the parities generated from the output of the error-correction encoder, and are therefore inefficient. In this paper, we propose a novel joint crosstalk-avoidance and error-correction coding and decoding scheme that provides higher bus transmission rates compared with existing approaches. Our joint approach carefully embeds the parities such that the crosstalk-avoidance property is preserved. We analyze the rate and minimum distance of the proposed scheme. We also provide a density evolution analysis and predict iterative decoding thresholds for reliable communication under random bus erasures. This density evolution analysis is nonstandard, since the crosstalk-avoidance constraints are inherently nonlinear. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Min Ye;Alexander Barg;
Pages: 1639 - 1656 Abstract: Two widely studied models of multiple-node repair in distributed storage systems are centralized repair and cooperative repair. The centralized model assumes that all the failed nodes are recreated in one location, while the cooperative one stipulates that the failed nodes may communicate but are distinct, and the amount of data exchanged between them is included in the repair bandwidth. As our first result, we prove a lower bound on the minimum bandwidth of cooperative repair. We also show that the cooperative model is stronger than the centralized one, in the sense that any maximum distance separable (MDS) code with optimal repair bandwidth under the former model also has optimal bandwidth under the latter one. These results were previously known under the additional “uniform download” assumption, which is removed in our proofs. As our main result, we give explicit constructions of MDS codes with optimal cooperative repair for all possible parameters. More precisely, given any $n,k,h,d$ such that $2le h le n-dle n-k$ we construct $(n,k)$ MDS codes over the field $F$ of size $ F ge (d+1-k)n$ that can optimally repair any $h$ erasures from any $d$ helper nodes. The repair scheme of our codes involves two rounds of communication. In the first round, each failed node downloads information from the helper nodes, and in the second one, each failed node downloads additional information from the-other failed nodes. This implies that our codes achieve the optimal repair bandwidth using the smallest possible number of rounds. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Noga Alon;Boris Bukh;Yury Polyanskiy;
Pages: 1657 - 1667 Abstract: We consider list decoding in the zero-rate regime for two cases—the binary alphabet and the spherical codes in Euclidean space. Specifically, we study the maximal $tau in [{0,1}]$ for which there exists an arrangement of $M$ balls of relative Hamming radius $tau $ in the binary hypercube (of arbitrary dimension) with the property that no point of the latter is covered by $L$ or more of them. As $Mto infty $ the maximal $tau $ decreases to a well-known critical value $tau _{L}$ . In this paper, we prove several results on the rate of this convergence. For the binary case, we show that the rate is $Theta (M^{-1})$ when $L$ is even, thus extending the classical results of Plotkin and Levenshtein for $L=2$ . For $L=3$ , the rate is shown to be $Theta (M^{-({2}/{3})})$ . For the similar question about spherical codes, we prove the rate is $Omega (M^{-1})$ and $O(M^{-({2L}/{L^{2}-L+2})})$ . PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Chengju Li;Peng Zeng;
Pages: 1668 - 1676 Abstract: The hull of a linear code is defined to be the intersection of the code and its dual, and was originally introduced to classify finite projective planes. The hull plays an important role in determining the complexity of algorithms for checking permutation equivalence of two linear codes and computing the automorphism group of a linear code. It has been shown that these algorithms are very effective in general if the size of the hull is small. The objective of this paper is to present some sufficient and necessary conditions that linear codes and cyclic codes have one-dimensional hull. It is shown that there are no such binary or ternary cyclic codes. Based on these characterizations, some constructions of linear codes with one-dimensional hull were given by employing quadratic number fields, partial difference sets, and difference sets. We also construct cyclic codes with one-dimensional hull. Some optimal codes with one-dimensional hull are obtained. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Irina E. Bocharova;Boris D. Kudryashov;Vitaly Skachek;Yauhen Yakimenka;
Pages: 1677 - 1693 Abstract: A new method is presented for low-complexity near-maximum-likelihood (ML) decoding of low-density parity-check (LDPC) codes over the additive white Gaussian noise channel. The proposed method termed belief-propagation–list erasure decoding (BP-LED) is based on erasing carefully chosen unreliable bits performed in case of BP decoding failure. A strategy of introducing erasures into the received vector and a new erasure decoding algorithm are proposed. The new erasure decoding algorithm, called list erasure decoding, combines ML decoding over the BEC with list decoding applied if the ML decoder fails to find a unique solution. The asymptotic exponent of the average list size for random regular LDPC codes from the Gallager ensemble is analyzed. Furthermore, a few examples of irregular quasi-cyclic LDPC as well as randomly constructed regular LDPC codes of short and moderate lengths are studied by simulations and their performance is compared to the tightened upper bound on the LDPC ensemble-average performance and the upper bound on the average performance of random linear codes under ML decoding. A comparison of the BP decoding and BP-LED performance of the WiMAX standard codes and performance of the near-ML BEAST decoding are presented. The new algorithm is applied to decoding a short nonbinary (NB) LDPC code over extensions of the binary Galois field. The obtained simulation results are compared to the tightened upper bound on the ensemble-average performance of the binary image of regular NB LDPC codes. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Claude Carlet;Sihem Mesnager;Chunming Tang;Yanfeng Qi;
Pages: 1694 - 1704 Abstract: Linear complementary pairs (LCPs) of codes play an important role in armoring implementations against side-channel attacks and fault injection attacks. One of the most common ways to construct LCP of codes is to use Euclidean linear complementary dual (LCD) codes. In this paper, we first introduce the concept of linear codes with $sigma $ complementary dual ( $sigma $ -LCD), which includes known Euclidean LCD codes, Hermitian LCD codes, and Galois LCD codes. Like Euclidean LCD codes, $sigma $ -LCD codes can also be used to construct LCP of codes. We show that for $q> 2$ , all $q$ -ary linear codes are $sigma $ -LCD, and for every binary linear code $mathcal C$ , the code ${0}times mathcal C$ is $sigma $ -LCD. Furthermore, we study deeply $sigma $ -LCD generalized quasi-cyclic (GQC) codes. In particular, we provide the characterizations of $sigma $ -LCD GQC codes, self-orthogonal GQC codes, and self-dual GQC codes, respectively. Moreover, we provide the constructions of asymptotically good $sigma $ -LCD GQC codes. Finally, we focus on $sigma $ -LCD abelian codes and prove that all abelian codes in a semi-simple group algebra are $sigma $ -LCD. The results derived in this paper extend those on the classical LCD codes and show that $sigma $ -LCD codes allow the construction of LCP of codes more easily and with more flexibility. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Michal Horovitz;Tuvi Etzion;
Pages: 1705 - 1713 Abstract: Local rank modulation (LRM) scheme was suggested for representing the information in flash memories in order to overcome the drawbacks of rank modulation. For $0 < sleq tleq n$ with $s$ dividing $n$ , an $(s,t,n)$ -LRM scheme is a LRM scheme where the $n$ cells are locally viewed cyclically through a sliding window of size $t$ resulting in a sequence of small permutations, which requires less comparisons and less distinct values. The gap between two such windows equals to $s$ . In this paper, encoding, decoding, and asymptotic enumeration of the $(1,t,n)$ -LRM scheme are studied. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Mohammad Ali Maddah-Ali;Urs Niesen;
Pages: 1714 - 1724 Abstract: Over the past decade, the bulk of wireless traffic has shifted from speech to content. This shift creates the opportunity to cache part of the content in memories closer to the end users, for example in base stations. Most previous paper focuses on the reduction of load in the backhaul and core networks due to caching, i.e., on the benefits caching offers for the wireline communication link between the origin servers and the caches. In this paper, we are instead interested in the benefits caching can offer for the wireless communication link between the caches and the end users. To quantify the gains of caching for this wireless link, we consider an interference channel in which each transmitter is equipped with an isolated cache memory. Communication takes place in two phases, a content placement phase followed by a content delivery phase. The objective is to design both the placement and the delivery phases to maximize the rate in the delivery phase in response to any possible user demands. Focusing on the three-user case, we show that through careful joint design of these phases, we can reap three distinct benefits from caching: a load balancing gain, an interference cancellation gain, and an interference alignment gain. In our proposed scheme, load balancing is achieved through a specific file splitting and placement, producing a particular pattern of content overlap at the caches. This overlap allows to implement interference cancellation. Furthermore, it allows us to create several virtual transmitters, each transmitting a part of the requested content, which increases interference-alignment possibilities. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Min Li;Lawrence Ong;Sarah J. Johnson;
Pages: 1725 - 1739 Abstract: In this paper, we propose a new coding scheme and establish new bounds on the capacity region for the multi-sender unicast index-coding problem. We revisit existing partitioned distributed composite coding (DCC) proposed by Sadeghi et al. and identify its limitations in the implementation of multi-sender composite coding and in the strategy of sender partitioning. We then propose two new coding components to overcome these limitations and develop a multi-sender cooperative composite coding (CCC). We show that CCC can strictly improve upon partitioned DCC, and is the key to achieve optimality for a number of index-coding instances. The usefulness of CCC and its special cases is illuminated via non-trivial examples, and the capacity region is established for each example. Comparisons between CCC and other non-cooperative schemes in recent works are also provided to further demonstrate the advantage of CCC. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Yansheng Wu;Qin Yue;
Pages: 1740 - 1751 Abstract: Constacyclic codes are well-known generalizations of cyclic and negacyclic codes. Due to their rich algebraic structure, constacyclic codes are used to construct quantum codes and symbol-pair codes. Let ${mathbb {F}}_{q}$ be a finite field with order $q$ , where $q$ is a positive power of a prime $p$ . Suppose that $n$ is a positive integer and the product of distinct prime factors of $n$ divides $q-1$ , i.e., $rad(n)mid (q-1)$ . In this paper, we explicitly factorize the polynomial $x^{n}-lambda $ for each $lambda in {mathbb {F}}_{q}^{*}$ . As applications, first, we obtain all repeated-root $lambda $ -constacyclic codes and their dual codes of length $np^{s}$ over ${mathbb {F}}_{q}$ ; second, we determine all simple-root LCD cyclic codes and LCD negacyclic codes of length $n$ over ${mathbb {F}}_{q}$ ; third, we list all self-dual repeated-root negacyclic codes of l-ngth $np^{s}$ over ${mathbb {F}}_{q}$ . In contrast to known results, the lengths of constacyclic codes in this paper have more flexible parameters. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
J. J. Bernal;M. Guerreiro;J. J. Simón;
Pages: 1752 - 1763 Abstract: In this paper, we develop a technique to extend any bound for the minimum distance of cyclic codes constructed from its defining sets (ds-bounds) to Abelian (or multivariate) codes through the notion of ${mathbb B}$ -apparent distance. We also study conditions for an Abelian code to verify that its ${mathbb B}$ -apparent distance reaches its (true) minimum distance. Then, we construct some codes as an application. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Dania Elzouki;Sorina Dumitrescu;Jun Chen;
Pages: 1764 - 1781 Abstract: In this paper, we propose a lattice-based robust distributed source coding system for two correlated sources and provide a detailed performance analysis under the high resolution assumption. It is shown, among other things, that, in the asymptotic regime where: 1) the side distortion approaches 0 and 2) the ratio between the central and side distortions approaches 0, our scheme is capable of achieving the information-theoretic limit of quadratic multiple description coding when the two sources are identical, whereas a variant of the random coding scheme by Chen and Berger with Gaussian codes has a performance loss of 0.5 bits relative to this limit. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Sangsin Na;David L. Neuhoff;
Pages: 1782 - 1792 Abstract: For generalized gamma probability densities, this paper studies the monotonicity of step sizes of optimal symmetric uniform scalar quantizers with respect to mean squared-error distortion. The principal results are that for the special cases of Gaussian, Laplacian, two-sided Rayleigh, and gamma densities, optimal step size monotonically decreases when the number of levels $N$ increases by two, and that for any generalized gamma density and all sufficiently large $N$ , optimal step size again decreases when $N$ increases by two. Also, it is shown that for a Laplacian density and sufficiently large $N$ , optimal step size decreases when $N$ increases by just one. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Álvaro Martín;Gadiel Seroussi;Luciana Vitale;
Pages: 1793 - 1806 Abstract: We study the maximum Markov model order that can be estimated for an (individual) input sequence $x$ of length $n$ over a finite alphabet of size $alpha $ , for popular estimators of tree models, where the estimated order is determined by the depth of a context tree estimate, and in the special case of plain Markov models, where the tree is constrained to be perfect (with all leaves at the same depth). First, we consider penalized maximum likelihood estimators where a context tree $hat {T}$ is obtained by minimizing a cost of the form $-log hat {P}_{T}(x) + f(n) S_{T} $ , where $hat {P}_{T}(x)$ is the ML of $x$ under a model with context tree $T$ , $S_{T}$ is the set of leaves of $T$ , and $f(n)$ is an increasing (penalization) function of $n$ (the popular BIC estimator is a special case with $f(n)=frac {alpha -1}{2}log n$ ). For plain Markov models, a simple argument yields a known upper bound $overline {k}(n) = O(log n)$ on the maximum order that can be es-imated for $x$ , and we show that, in fact, this simple bound is not far from tight. For general context trees, we derive an asymptotic upper bound, $n^{1/2 - o(1)}$ , on the estimated depth, and we exhibit explicit input sequences that asymptotically attain the bound up to a multiplicative constant factor. We show that a similar upper bound applies also to MDL estimators based on the KT probability assignment and, moreover, the same example sequences asymptotically approach the upper bound also in this case. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Roy D. Yates;Sanjit K. Kaul;
Pages: 1807 - 1827 Abstract: We examine multiple independent sources providing status updates to a monitor through simple queues. We formulate an age of information (AoI) timeliness metric and derive a general result for the AoI that is applicable to a wide variety of multiple source service systems. For first-come first-served and two types of last-come first-served systems with Poisson arrivals and exponential service times, we find the region of feasible average status ages for multiple updating sources. We then use these results to characterize how a service facility can be shared among multiple updating sources. A new simplified technique for evaluating the AoI in finite-state continuous-time queuing systems is also derived. Based on stochastic hybrid systems, this method makes AoI evaluation to be comparable in complexity to finding the stationary distribution of a finite-state Markov chain. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Xing Liu;Liang Zhou;Shengqiang Li;
Pages: 1828 - 1844 Abstract: In order to evaluate the goodness of frequency hopping (FH) sequence design, the periodic Hamming correlation function is used as an important measure. Usually, the length of correlation window is shorter than the period of the chosen FH sequence, so the study of the partial Hamming correlation of FH sequence is particularly important. If an FH sequence or an FH sequence set has an optimal partial Hamming correlation with respect to the partial Hamming correlation bound for all length of correlation window, then the FH sequence or the FH sequence set is said to be strictly optimal. In this paper, we first prove that there is no strictly optimal FH sequence set of family size $M$ and sequence length $N$ over a frequency slot set of size $q$ with respect to the partial Hamming correlation bound derived by Niu et al. when $N>{q^{2}}/{M}$ and $qgeq 2$ , and that by Cai et al. when $N>{q^{2}}/{M}$ and $qgeq {2N}/({N-2})$ . Furthermore, we define a special partition-type difference packing (DP) called $[N,nabla,H_{a}^{l}]$ PDP and give several classes of $[N,nabla,H_{a}^{l}]$ PDPs. Then, we present a new construction of strictly optimal FH sequences. By choosing different PDPs, the FH sequences constructed can give new and flexible parameters. By utilizing this -onstruction method recursively, we can obtain new $[N,nabla,H_{a}^{l}]$ PDPs, which lead to infinitely many classes of strictly optimal FH sequences with new parameters. Moreover, based upon an $[N,nabla,H_{a}^{l}]$ PDP, we present a construction of strictly optimal FH sequence sets. By preceding construction method and recursive construction, we can also obtain infinite classes of strictly optimal FH sequence sets which can give new and flexible parameters. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Qian Guo;Thomas Johansson;Paul Stankovski Wagner;
Pages: 1845 - 1861 Abstract: Algorithms for secure encryption in a post-quantum world are currently receiving a lot of attention in the research community. One of the most promising such algorithms is the code-based scheme called QC-MDPC, which has excellent performance and a small public key size. In this paper, we present a very efficient key recovery attack on the QC-MDPC scheme using the fact that decryption uses an iterative decoding step, and this can fail with some small probability. We identify a dependence between the secret key and the failure in decoding. This can be used to build what we refer to as a distance spectrum for the secret key, which is the set of all distances between any two ones in the secret key. In a reconstruction step, we then determine the secret key from the distance spectrum. The attack has been implemented and tested on a proposed instance of QC-MDPC for 80-bit security. It successfully recovers the secret key in minutes. A slightly modified version of the attack can be applied on proposed versions of the QC-MDPC scheme that provides IND-CCA security. The attack is a bit more complex in this case, but still very much below the security level. The reason why we can break schemes with proved CCA security is that the model for these proofs typically does not include the decoding error possibility. At last, we present several algorithms for key reconstruction from an empirical distance spectrum. We first improve the naïve algorithm for key reconstruction by a factor of about 3 0000, when the parameters for 80-bit security are implemented. We further develop the algorithm to deal with errors in the distance spectrum. This ultimately reduces the requirement on the number of ciphertexts that need to be collected for a successful key recovery. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Lei Yu;Vincent Y. F. Tan;
Pages: 1862 - 1897 Abstract: The conventional channel resolvability problem refers to the determination of the minimum rate required for an input process so that the output distribution approximates a target distribution in either the total variation distance or the relative entropy. In contrast to previous works, in this paper, we use the (normalized or unnormalized) Rényi divergence (with the Rényi parameter in $[{0,2}]cup {infty }$ ) to measure the level of approximation. We also provide asymptotic expressions for normalized Rényi divergence when the Rényi parameter is larger than or equal to 1 as well as (lower and upper) bounds for the case when the same parameter is smaller than 1. We characterize the Rényi resolvability, which is defined as the minimum rate required to ensure that the Rényi divergence vanishes asymptotically. The Rényi resolvabilities are the same for both the normalized and unnormalized divergence cases. In addition, when the Rényi parameter smaller than 1, consistent with the traditional case where the Rényi parameter is equal to 1, the Rényi resolvability equals the minimum mutual information over all input distributions that induce the target output distribution. When the Rényi parameter is larger than 1 the Rényi resolvability is, in general, larger than the mutual information. The optimal Rényi divergence is proven to vanish at least exponentially fast for both of these two cases, as long as the code rate is larger than the Rényi resolvability. The optimal exponential rate of decay for i.i.d. random codes is also characterized exactly. We apply these results to the wiretap channel, and completely characterize the optimal tradeof- between the rates of the secret and non-secret messages when the leakage measure is given by the (unnormalized) Rényi divergence. This tradeoff differs from the conventional setting when the leakage is measured by the traditional mutual information. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Yimin Pang;Mahesh K. Varanasi;
Pages: 1898 - 1920 Abstract: Approximate capacity regions are established for a class of interfering multiple access channels consisting of two multiple-access channels (MACs), each with an arbitrary number of transmitters, with one transmitter in each MAC causing interference to the receiver of the other MAC, a channel we refer to henceforth as the MAC-IC-MAC. For the discrete memory-less (DM) MAC-IC-MAC, two inner bounds are obtained that are generalizations of prior inner bounds for the two-user DM interference channel (IC) due to Chong et al. For the semi-deterministic MAC-IC-MAC, it is shown that single-user coding at the non-interfering transmitters and superposition coding at the interfering transmitter of each MAC achieves a rate region that is within a quantifiable gap of the capacity region, thereby extending such a result for the two-user semi-deterministic IC by Telatar and Tse. For the Gaussian MAC-IC-MAC, an approximate capacity region that is within a constant gap of the capacity region is obtained, generalizing such a result for the two-user Gaussian IC by Etkin et al. On contrary to the aforementioned approximate capacity results for the two-user IC, whose achievability requires the union of all admissible input distributions, our gap results on the semi-deterministic and the Gaussian MAC-IC-MAC are achievable by only a subset and one of all admissible coding distributions, respectively. The symmetric generalized degrees of freedom (GDoFs) of the symmetric Gaussian MAC-IC-MAC with more than one user per cell, which is a function of the interference strength (the ratio of INR to SNR at high SNR, both expressed in dB) and the numbers of users in each cell, are V-shaped with flat shoulders. An analysis based on signal-level partitions shows that the non-interfering transmitters utilize the signal-level partitions at the receiver where they are intended that cannot be accessed by the interfering transmitters (due to the restriction of superpositio- coding), thereby improving the sum symmetric GDoF of up to one degree of freedom per cell under a range of SINR exponent levels, which in turn becomes wider as the number of transmitters in each cell increases. Consequently, time-sharing between interfering and non-interfering transmitters is GDoF-suboptimal in general, as is time-sharing between the two embedded MAC-Z-MACs. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Jinming Wen;Xiao-Wen Chang;
Pages: 1921 - 1935 Abstract: The Korkine–Zolotareff (KZ) reduction is one of the often used reduction strategies for lattice decoding. In this paper, we first investigate some important properties of KZ reduced matrices. Specifically, we present a linear upper bound on the Hermit constant which is around 7/8 times of the existing sharpest linear upper bound, and an upper bound on the KZ constant which is polynomially smaller than the existing sharpest one. We also propose upper bounds on the lengths of the columns of KZ reduced matrices, and an upper bound on the orthogonality defect of KZ reduced matrices which are even polynomially and exponentially smaller than those of boosted KZ reduced matrices, respectively. Then, we derive upper bounds on the magnitudes of the entries of any solution of a shortest vector problem (SVP) when its basis matrix is LLL reduced. These upper bounds are useful for analyzing the complexity and understanding numerical stability of the basis expansion in a KZ reduction algorithm. Finally, we propose a new KZ reduction algorithm by modifying the commonly used Schnorr–Euchner search strategy for solving SVPs and the basis expansion method proposed by Zhang et al. Simulation results show that the new KZ reduction algorithm is much faster and more numerically reliable than the KZ reduction algorithm proposed by Zhang et al., especially when the basis matrix is ill conditioned. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Ezio Biglieri;Emanuele Viterbo;
Pages: 1936 - 1947 Abstract: Using an algebraic approach based on the theory of Coxeter groups, we design, and describe the performance of, a class of line codes derived from permutation modulation, useful for parallel transmission of $b$ bits over $b+1$ wires, and admitting especially simple encoding and decoding algorithms. With these codes, resistance to common-mode noise is obtained by using codewords whose components sum to zero, simultaneous switching output noise is reduced by using constant-energy signals, and the effects of intersymbol interference are reduced by having decisions based on only two values at the input of the final slicers. Codebook design is based on the theory of Group Codes for the Gaussian Channel, as specialized to Coxeter matrix groups generated by reflections in orthogonal hyperplanes. A number of designs are exhibited, some of them being novel or improving on previously obtained codes. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Ather Gattami;
Pages: 1948 - 1960 Abstract: In this paper, we revisit the problem of finding the average capacity of the Gaussian feedback channel. First, we consider the problem of finding the average capacity of the analog Gaussian noise channel, where the noise has an arbitrary spectral density. We introduce a new approach to the problem, where we solve the problem over a finite number of transmissions and then consider the limit of an infinite number of transmissions. Furthermore, we consider the important special case of stationary Gaussian noise with finite memory. We show that the channel capacity at stationarity can be found by solving a semi-definite program, and hence computationally tractable. We also give new proofs and results of the non-stationary solution which bridges the gap between results in the literature for the stationary and non-stationary feedback channel capacities. It is shown that a linear communication feedback strategy is optimal. Similar to the solution of the stationary problem, it is shown that the optimal linear strategy is to transmit a linear combination of the information symbols to be communicated and the innovations for the estimation error of the state of the noise process. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)

Authors:
Antonio Campello;Daniel Dadush;Cong Ling;
Pages: 1961 - 1971 Abstract: In this paper, we show that any sequence of infinite lattice constellations which is good for the unconstrained Gaussian channel can be shaped into a capacity-achieving sequence of codes for the power-constrained Gaussian channel under lattice decoding and non-uniform signaling. Unlike previous results in the literature, our scheme holds with no extra condition on the lattices (e.g., quantization-goodness or vanishing flatness factor), thus establishing a direct implication between AWGN-goodness, in the sense of Poltyrev and capacity-achieving codes. Our analysis uses properties of the discrete Gaussian distribution in order to obtain precise bounds on the probability of error and achievable rates. In particular, we obtain a simple characterization of the finite-blocklength behavior of the scheme, showing that it approaches the optimal dispersion coefficient for high signal-to-noise ratio. We further show that for low signal-to-noise ratio, the discrete Gaussian over centered lattice constellations cannot achieve capacity, and thus a shift (or “dither”) is essentially necessary. PubDate:
March 2019
Issue No:Vol. 65, No. 3 (2019)