Search

This paper considers “ $\delta $ -almost Reed–Muller codes”, i.e., linear codes spanned by evaluations of all but a $\delta $ fraction of monomials of degree at most $d$. It is shown that for any $\delta > 0$ and any $\varepsilon >0$ , there exists a family of $\delta $ -almost Reed–Muller codes of constant rate that correct $1/2- \varepsilon $ fraction of random errors with high probability. For exact Reed–Muller codes, the analogous result is not known and represents a weaker version of the longstanding conjecture that Reed–Muller codes achieve capacity for random errors (Abbe-Shpilka-Wigderson STOC ’15). Our proof is based on the recent polarization result for Reed–Muller codes, combined with a combinatorial approach to establishing inequalities between the Reed–Muller code entropies. [ABSTRACT FROM AUTHOR]

Reed-Muller (RM) codes are among the oldest, simplest and perhaps most ubiquitous family of codes. They are used in many areas of coding theory in both electrical engineering and computer science. Yet, many of their important properties are still under investigation. This paper covers some of the recent developments regarding the weight enumerator and the capacity-achieving properties of RM codes, as well as some of the algorithmic developments. In particular, the paper discusses the recent connections established between RM codes, thresholds of Boolean functions, polarization theory, hypercontractivity, and the techniques of approximating low weight codewords using lower degree polynomials (when codewords are viewed as evaluation vectors of degree r polynomials in m variables). It then overviews some of the algorithms for decoding RM codes. It covers both algorithms with provable performance guarantees for every block length, as well as algorithms with state-of-the-art performances in practical regimes, which do not perform as well for large block length. Finally, the paper concludes with a few open problems. [ABSTRACT FROM AUTHOR]

Reed-Muller (RM) codes were introduced in 1954 and have long been conjectured to achieve Shannon’s capacity on symmetric channels. The activity on this conjecture has recently been revived with the emergence of polar codes. RM codes and polar codes are generated by the same matrix $\begin{aligned} G_{m}= \left[{\begin{smallmatrix}1 & 0 \\ 1 & 1 \\ \end{smallmatrix}}\right]^{\otimes m} \end{aligned}$ but using different subset of rows. RM codes select simply rows having largest weights. Polar codes select instead rows having the largest conditional mutual information proceeding top to down in $G_{m}$ ; while this is a more elaborate and channel-dependent rule, the top-to-down ordering allows Arıkan to show that the conditional mutual information polarizes, and this gives directly a capacity-achieving code on any symmetric channel. RM codes are yet to be proved to have such a property, despite the recent success for the erasure channel. In this article, we connect RM codes to polarization theory. We show that proceeding in the RM code ordering, i.e., not top-to-down but from the lightest to the heaviest rows in $G_{m}$ , the conditional mutual information again polarizes. Here “polarization” means that almost all the conditional mutual information becomes either very close to 0 or very close to 1. Polarization itself is a necessary condition for RM codes to achieve capacity on symmetric channels while polarization together with a strong order on the conditional mutual information gives a sufficient condition, where strong order means that rows with larger weight always correspond to larger conditional mutual information. Although we are not able to prove the strong order, we establish a partial order on the conditional mutual information, which is a subset of the strong order. While the main results of this article–polarization together with the partial order–provide some advances on the capacity-achieving conjecture of RM codes, we emphasize that our results do not allow us to prove the conjecture. [ABSTRACT FROM AUTHOR]

We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM codes), and aggregating the reconstructions (e.g., using majority votes). We further provide extensions of the algorithms using list-decoding. We run our algorithm for AWGN channels and Binary Symmetric Channels at the short code length (≤ 1024) regime for a wide range of code rates. Simulation results show that in both low code rate and high code rate regimes, the new algorithm outperforms the widely used decoder for polar codes (SCL+CRC) with the same parameters. The performance of the new algorithm for RM codes in those regimes is in fact close to that of the maximal likelihood decoder. Finally, the new decoder naturally allows for parallel implementations. [ABSTRACT FROM AUTHOR]

In the multireference alignment model, a signal is observed by the action of a random circular translation and the addition of Gaussian noise. The goal is to recover the signal’s orbit by accessing multiple independent observations. Of particular interest is the sample complexity, i.e., the number of observations/samples needed in terms of the signal-to-noise ratio (SNR) (the signal energy divided by the noise variance) in order to drive the mean-square error to zero. Previous work showed that if the translations are drawn from the uniform distribution, then, in the low SNR regime, the sample complexity of the problem scales as $\omega (1/ \mathrm {SNR}^{3})$. In this paper, using a generalization of the Chapman–Robbins bound for orbits and expansions of the $\chi ^{2}$ divergence at low SNR, we show that in the same regime the sample complexity for any aperiodic translation distribution scales as $\omega (1/ \mathrm {SNR}^{2})$. This rate is achieved by a simple spectral algorithm. We propose two additional algorithms based on non-convex optimization and expectation–maximization. We also draw a connection between the multireference alignment problem and the spiked covariance model. [ABSTRACT FROM AUTHOR]

In this paper, we show that the Hadamard matrix acts as an extractor over the reals of the Rényi Information Dimension (RID), in an analogous way to how it acts as an extractor of the discrete entropy over finite fields. More precisely, we prove that the RID of an i.i.d. sequence of mixture random variables polarizes to the extremal values of 0 and 1 (corresponding to discrete and continuous distributions) when transformed by a Hadamard matrix. Furthermore, we prove that the polarization pattern of the RID admits a closed form expression and follows exactly the Binary Erasure Channel (BEC) polarization pattern in the discrete setting. We discuss the applications of the RID polarization to Compressed Sensing of i.i.d. sources. In particular, we use the RID polarization to construct a family of deterministic ±1-valued sensing matrices for Compressed Sensing. We run numerical simulations to compare the performance of the resulting matrices with that of the random Gaussian and the random Hadamard matrices. The results indicate that the proposed matrices afford competitive performances, while being explicitly constructed. [ABSTRACT FROM PUBLISHER]

This paper considers the problem of linear Boolean classification, where the goal is to determine in which set, among two given sets of Boolean vectors, an unknown vector belongs to by making linear queries. Finding the least number of queries is equivalent to determining the minimal rank of a matrix over $GF(2)$ , whose kernel does not intersect a given set $S$ . In the case where $S$ is a Hamming ball, this reduces to finding linear codes of largest dimension. For a general set $S$ , this is an instance of the critical problem posed by Crapo and Rota in 1970, open in general. This paper focuses on the case where $S$ is an annulus. As opposed to balls, it is shown that an optimal kernel is composed not only of dense but also of sparse vectors, and the optimal mixture is identified in various cases. These findings corroborate a proposed conjecture that for an annulus of inner and outer radius $nq$ and $np$ respectively, the optimal relative rank is given by the normalized entropy $(1-q)H(p/(1-q))$ , an extension of the Gilbert–Varshamov bound. [ABSTRACT FROM AUTHOR]

The stochastic block model with two communities, or equivalently the planted bisection model, is a popular model of random graph exhibiting a cluster behavior. In the symmetric case, the graph has two equally sized clusters and vertices connect with probability $p$ within clusters and q$ across clusters. In the past two decades, a large body of literature in statistics and computer science has focused on providing lower bounds on the scaling of |p-q|$ to ensure exact recovery. In this paper, we identify a sharp threshold phenomenon for exact recovery: if \alpha =pn/\log (n)$ and \beta =qn/\log (n)$ are constant (with and is impossible if ({\alpha +\beta }/{2}) - \sqrt {\alpha \beta }<1 . In particular, this improves the existing bounds. This also sets a new line of sight for efficient clustering algorithms. While maximum likelihood (ML) achieves the optimal threshold (by definition), it is in the worst case NP-hard. This paper proposes an efficient algorithm based on a semidefinite programming relaxation of ML, which is proved to succeed in recovering the communities close to the threshold, while numerical experiments suggest that it may achieve the threshold. An efficient algorithm that succeeds all the way down to the threshold is also obtained using a partial recovery algorithm combined with a local improvement procedure. [ABSTRACT FROM PUBLISHER]

This paper studies the parameters for which binary Reed–Muller (RM) codes can be decoded successfully on the binary erasure channel and binary symmetry channel, and, in particular, when can they achieve capacity for these two classical channels. Necessarily, this paper also studies the properties of evaluations of multivariate $GF(2)$ polynomials on the random sets of inputs. For erasures, we prove that RM codes achieve capacity both for very high rate and very low rate regimes. For errors, we prove that RM codes achieve capacity for very low rate regimes, and for very high rates, we show that they can uniquely decode at about the square root of the number of errors at capacity. The proofs of these four results are based on different techniques, which we find interesting in their own right. In particular, we study the following questions about $E(m,r)$ , the matrix whose rows are the truth tables of all the monomials of degree $\leq r$ in $m$ variables. What is the most (resp. least) number of random columns in $E(m,r)$ that define a submatrix having full column rank (resp. full row rank) with high probability? We obtain tight bounds for very small (resp. very large) degrees $r$ , which we use to show that RM codes achieve capacity for erasures in these regimes. Our decoding from random errors follows from the following novel reduction. For every linear code $C$ of sufficiently high rate, we construct a new code $C'$ obtained by tensorizing $C$ , such that for every subset $S$ of coordinates, if $C$ can recover from erasures in $S$ , then $C'$ can recover from errors in $S$ . Specializing this to the RM codes and using our results for erasures imply our result on the unique decoding of the RM codes at high rate. Finally, two of our capacity achieving results require tight bounds on the weight distribution of RM codes. We obtain such bounds extending the recent bounds from constant degree to linear degree polynomials. [ABSTRACT FROM PUBLISHER]

The polarization phenomenon for a single source is extended to a framework with multiple correlated sources. It is shown in addition to extracting the randomness of the source, the polar transforms take the original arbitrary dependencies to extremal dependencies. Polar coding schemes for the Slepian–Wolf (SW) coding problem and for secret key generations are then proposed based on this phenomenon. In particular, secret keys achieving the secrecy capacity and compression schemes achieving the SW capacity region are obtained with a complexity of $O(n \log (n))$ . [ABSTRACT FROM AUTHOR]

Polar codes are introduced for discrete memoryless broadcast channels. For m -user deterministic broadcast channels, polarization is applied to map uniformly random message bits from m -independent messages to one codeword while satisfying broadcast constraints. The polarization-based codes achieve rates on the boundary of the private-message capacity region. For two-user noisy broadcast channels, polar implementations are presented for two information-theoretic schemes: 1) Cover’s superposition codes and 2) Marton’s codes. Due to the structure of polarization, constraints on the auxiliary and channel-input distributions are identified to ensure proper alignment of polarization indices in the multiuser setting. The codes achieve rates on the capacity boundary of a few classes of broadcast channels (e.g., binary-input stochastically degraded). The complexity of encoding and decoding is O(n \log n) , where n of the average block error probability where 0 < \beta < {1}/{2} . Reproducible experiments for finite block lengths n = 512, 1024, 2048$ corroborate the theory. [ABSTRACT FROM AUTHOR]

The entropy power inequality (EPI) yields lower bounds on the differential entropy of the sum of two independent real-valued random variables in terms of the individual entropies. Versions of the EPI for discrete random variables have been obtained for special families of distributions with the differential entropy replaced by the discrete entropy, but no universal inequality is known (beyond trivial ones). More recently, the sumset theory for the entropy function yields a sharp inequality H(X+X^\prime)-H(X)\geq1\over2-o(1) when X , X^{\prime} are independent identically distributed (i.i.d.) with high entropy. This paper provides the inequality H(X+X^{\prime})-H(X)\geq g(H(X)) , where X , X^{\prime} are arbitrary i.i.d. integer-valued random variables and where g is a universal strictly positive function on \BBR+ satisfying g(0)=0 . Extensions to nonidentically distributed random variables and to conditional entropies are also obtained. [ABSTRACT FROM AUTHOR]

It is conjectured that the covariance matrices minimizing the outage probability under a power constraint for multiple-input multiple-output channels with Gaussian fading are diagonal with either zeros or constant values on the diagonal. In the multiple-input single-output (MISO) setting, this is equivalent to conjecture that the Gaussian quadratic forms having largest tail probability correspond to such diagonal matrices. This paper provides a proof of the conjecture in this MISO setting. [ABSTRACT FROM PUBLISHER]

In this paper, polar codes for the m-user multiple access channel (MAC) with binary inputs are constructed. It is shown that Arikan's polarization technique applied individually to each user transforms independent uses of an m-user binary input MAC into successive uses of extremal MACs. This transformation has a number of desirable properties: 1) the “uniform sum-rate” of the original MAC is preserved, 2) the extremal MACs have uniform rate regions that are not only polymatroids but matroids, and thus, 3) their uniform sum-rate can be reached by each user transmitting either uncoded or fixed bits; in this sense, they are easy to communicate over. A polar code can then be constructed with an encoding and decoding complexity of O(n \log n) (where n is the block length), a block error probability of o(\exp (- n^1/2 - \varepsilon)), and capable of achieving the uniform sum-rate of any binary input MAC with arbitrary many users. Applications of this polar code construction to channels with a finite field input alphabet and to the additive white Gaussian noise channel are also discussed. [ABSTRACT FROM PUBLISHER]

This paper investigates network information theory problems where the external noise is Gaussian distributed. In particular, the Gaussian broadcast channel with coherent fading and the Gaussian interference channel are considered. It is shown that in these problems, non-Gaussian code ensembles can achieve higher rates than the Gaussian ones. It is also shown that the strong Shamai–Laroia conjecture on the Gaussian ISI channel does not hold. In order to analyze non-Gaussian code ensembles over Gaussian networks, a geometrical tool using the Hermite polynomials is proposed. This tool provides a coordinate system to analyze a class of non-Gaussian input distributions that are invariant over Gaussian networks. [ABSTRACT FROM AUTHOR]

Over discrete memoryless channels (DMC), linear decoders (maximizing additive metrics) afford several nice properties. In particular, if suitable encoders are employed, the use of decoding algorithms with manageable complexities is permitted. For a compound DMC, decoders that perform well without the channel's knowledge are required in order to achieve capacity. Several such decoders have been studied in the literature, however, there is no such known decoder which is linear. Hence, the problem of finding linear decoders achieving capacity for compound DMC is addressed, and it is shown that under minor concessions, such decoders exist and can be constructed. A geometric method based on the very noisy transformation is developed and used to solve this problem. [ABSTRACT FROM PUBLISHER]

Practical implementations of secret-key generation are often based on sequential strategies, which handle reliability and secrecy in two successive steps, called reconciliation and privacy amplification. In this paper, we propose an alternative approach based on polar codes that jointly deals with reliability and secrecy. Specifically, we propose secret-key capacity-achieving polar coding schemes for the following models: (i) the degraded binary memoryless source (DBMS) model with rate-unlimited public communication, (ii) the DBMS model with one-way rate-limited public communication, (iii) the 1-to-m broadcast model and (iv) the Markov tree model with uniform marginals. For models (i) and (ii) our coding schemes remain valid for non-degraded sources, although they may not achieve the secret-key capacity. For models (i), (ii) and (iii), our schemes rely on pre-shared secret seed of negligible rate; however, we provide special cases of these models for which no seed is required. Finally, we show an application of our results to secrecy and privacy for biometric systems. We thus provide the first examples of low-complexity secret-key capacity-achieving schemes that are able to handle vector quantization for model (ii), or multiterminal communication for models (iii) and (iv). [ABSTRACT FROM PUBLISHER]