Recently, a new adaptive path interpolation method has been developed as a simple and versatile scheme to calculate exactly the asymptotic mutual information of Bayesian inference problems defined on dense factor graphs. These include random linear and generalized estimation, sparse superposition codes, and low-rank matrix / tensor estimation. For all these systems, the adaptive interpolation method directly proves that the replica-symmetric prediction is exact, in a simple and unified manner. When the underlying factor graph of the inference problem is sparse the replica prediction is considerably more complicated, and rigorous results are often lacking or obtained by rather complicated methods. In this work we show how to extend the adaptive path interpolation method to sparse systems. We concentrate on a censored block model, where hidden variables are measured through a binary erasure channel, for which we fully prove the replica prediction.

We rigorously derive a single-letter variational expression for the mutual information of the asymmetric two-groups stochastic block model in the dense graph regime. Existing proofs in the literature are indirect, as they involve mapping the model to a rank-one matrix estimation problem whose mutual information is then determined by a combination of methods (e.g., interpolation, cavity, algorithmic, spatial coupling). In this contribution we provide a self-contained direct method using only the recently introduced adaptive interpolation method.

A new adaptive path interpolation method has been recently developed as a simple and versatile scheme to calculate exactly the asymptotic mutual information of Bayesian inference problems defined on dense factor graphs. These include random linear and generalized estimation, superposition codes, or low rank matrix and tensor estimation. For all these systems the method directly proves in a unified manner that the replica symmetric prediction is exact. When the underlying factor graph of the inference problem is sparse the replica prediction is considerably more complicated and rigorous results are often lacking or obtained by rather complicated methods. In this contribution we extend the adaptive path interpolation method to sparse systems. We concentrate on a Censored Block Model, where hidden variables are measured through a binary erasure channel, for which we fully prove the replica prediction.

The generalized censored block model considers the problem of inferring hidden binary variables from observations that are outputs of pairwise measurements from a symmetric channel. We give an exact formula for the stability threshold of density evolution by using an analysis of the potential functional of the model. In this model the phase transition is continuous so that this threshold is also the one for partial recovery of hidden variables. The formula is valid for all symmetric channels and generalizes the one already known for binary symmetric channels. We also give a bound on the finite slope of the Bhattacharyya parameter at the stability threshold. Finally, we briefly discuss implications for a heuristic derivation of the replica formula for the conditional entropy of the model.

The pattern maximum likelihood (PML) estimate, introduced by Orlitsky et al., is an estimate of the multiset of probabilities in an unknown probability distribution $\mathbf{p}$, the estimate being obtained from $n$ independent and identically distributed samples drawn from $\mathbf{p}$. The PML estimate involves solving a difficult optimization problem over the set of all probability mass functions of finite support. In this paper, we describe an interesting phase transition phenomenon in the PML estimate: at a certain sharp threshold, the uniform distribution goes from being a local maximum to being a local minimum for the optimization problem in the estimate. We go on to consider the question of whether a similar phase transition phenomenon also exists in the Bethe approximation of the PML estimate, the latter being an approximation method with origins in statistical physics. We show that the answer to this question is a qualified “yes.” Our analysis involves the computation of the mean and variance of the $(i,j)$th entry, $a_{i,j}$, in a random $k \times k$ nonnegative integer matrix $A$ with row and column sums all equal to $M$, drawn according to a distribution that assigns to $A$ a probability proportional to $\Pi_{i,j} \frac{(M-a_{i,j})!}{a_{i,j}!}$.

Recent empirical results have demonstrated that generalized belief propagation (GBP) can be used to closely estimate the capacity of certain 2D runlength-limited constraints. We provide a partial analytical validation of these observations by showing that GBP yields a lower bound on the partition function of 2D Ising models with restricted grid size. While previous papers have proved that belief propagation (BP) can be used to obtain a lower bound on the partition function of 2D Ising models, this paper is the first work that analyzes GBP-based partition function approximations of 2D Ising models.

We consider a new group testing model wherein each item is a binary random variable defined by an a priori probability of being defective. We assume that each probability is small and that items are independent, but not necessarily identically distributed. The goal of group testing algorithms is to identify with high probability the subset of defectives via non-linear (disjunctive) binary measurements. Our main contributions are two classes of algorithms: (1) adaptive algorithms with tests based either on a maximum entropy principle, or on a Shannon-Fano/Huffman code; (2) non-adaptive algorithms. Under loose assumptions and with high probability, our algorithms only need a number of measurements that is close to the information-theoretic lower bound, up to an explicitly-calculated universal constant factor.

We consider some computationally efficient and provably correct algorithms with near-optimal sample complexity for the problem of noisy nonadaptive group testing. Group testing involves grouping arbitrary subsets of items into pools. Each pool is then tested to identify the defective items, which are usually assumed to be sparse. We consider nonadaptive randomly pooling measurements, where pools are selected randomly and independently of the test outcomes. We also consider a model where noisy measurements allow for both some false negative and some false positive test outcomes (and also allow for asymmetric noise, and activation noise). We consider three classes of algorithms for the group testing problem (we call them specifically the coupon collector algorithm, the column matching algorithms, and the LP decoding algorithms-the last two classes of algorithms (versions of some of which had been considered before in the literature) were inspired by corresponding algorithms in the compressive sensing literature. The second and third of these algorithms have several flavors, dealing separately with the noiseless and noisy measurement scenarios. Our contribution is novel analysis to derive explicit sample-complexity bounds-with all constants expressly computed-for these algorithms as a function of the desired error probability, the noise parameters, the number of items, and the size of the defective set (or an upper bound on it). We also compare the bounds to information-theoretic lower bounds for sample complexity based on Fano's inequality and show that the upper and lower bounds are equal up to an explicitly computable universal constant factor (independent of problem parameters).

We formulate and analyze a stochastic threshold group testing problem motivated by biological applications. Here a set of n items contains a subset of d ≪ C n defective items. Subsets (pools) of the n items are tested. The test outcomes are negative if the number of defectives in a pool is no larger than l; positive if the pool contains more than u defectives, and stochastic (negative/positive with some probability) if the number of defectives in the pool is in the interval [l, u]. The goal of our stochastic threshold group testing scheme is to identify the set of d defective items via a “small” number of such tests with high probability. In the regime that l = o(d) we present schemes that are computationally feasible to design and implement, and require near-optimal number of tests. Our schemes are robust to a variety of models for probabilistic threshold group testing.

We present computationally efficient and provably correct algorithms with near-optimal sample-complexity for noisy non-adaptive group testing. Group testing involves grouping arbitrary subsets of items into pools. Each pool is then tested to identify the defective items, which are usually assumed to be sparsely distributed. We consider random non-adaptive pooling where pools are selected randomly and independently of the test outcomes. Our noisy scenario accounts for both false negatives and false positives for the test outcomes. Inspired by compressive sensing algorithms we introduce four novel computationally efficient decoding algorithms for group testing, CBP via Linear Programming (CBP-LP), NCBP-LP (Noisy CBP-LP), and the two related algorithms NCBP-SLP+ and NCBP-SLP- (“Simple” NCBP-LP). The first of these algorithms deals with the noiseless measurement scenario, and the next three with the noisy measurement scenario. We derive explicit sample-complexity bounds - with all constants made explicit - for these algorithms as a function of the desired error probability; the noise parameters; the number of items; and the size of the defective set (or an upper bound on it). We show that the sample-complexities of our algorithms are near-optimal with respect to known information-theoretic bounds.