We study the problem of recovering a hidden binary @math -sparse @math -dimensional vector @math from @math noisy linear observations @math where @math are i.i.d. @math and @math are i.i.d. @math . A closely related hypothesis testing problem is to distinguish the pair @math generated from this structured model from a corresponding null model where @math consist of purely independent Gaussian entries. In the low sparsity @math and high signal to noise ratio @math regime, we establish an All-or-Nothing' information-theoretic phase transition at a critical sample size @math , resolving a conjecture of gamarnikzadik . Specifically, we show that if @math , then the maximum likelihood estimator almost perfectly recovers the hidden vector with high probability and moreover the true hypothesis can be detected with a vanishing error probability. Conversely, if @math , then it becomes information-theoretically impossible even to recover an arbitrarily small but fixed fraction of the hidden vector support, or to test hypotheses strictly better than random guess. Our proof of the impossibility result builds upon two key techniques, which could be of independent interest. First, we use a conditional second moment method to upper bound the Kullback-Leibler (KL) divergence between the structured and the null model. Second, inspired by the celebrated area theorem, we establish a lower bound to the minimum mean squared estimation error of the hidden vector in terms of the KL divergence between the two models.
For the impossibility direction, previous work [Theorem 5.2] aeron:2010 has established that as @math , achieving @math for any @math is information-theoretically impossible if @math where @math for @math is the binary entropy function. This converse result is proved via a simple rate-distortion argument (see, e.g. @cite_4 for an exposition). In particular, given any estimator @math with @math , we have @math Notice that since @math the result implies that if @math , recovery, that is @math , is information-theoretically impossible and if @math , recovery, that is @math for an arbitrary @math , is impossible.
@cite_4
2805892743
Over the past few years, insights from computer science, statistical physics, and information theory have revealed phase transitions in a wide array of high-dimensional statistical problems at two distinct thresholds: One is the information-theoretical (IT) threshold below which the observation is too noisy so that inference of the ground truth structure is impossible regardless of the computational cost; the other is the computational threshold above which inference can be performed efficiently, i.e., in time that is polynomial in the input size. In the intermediate regime, inference is information-theoretically possible, but conjectured to be computationally hard. This article provides a survey of the common techniques for determining the sharp IT and computational limits, using community detection and submatrix detection as illustrating examples. For IT limits, we discuss tools including the first and second moment method for analyzing the maximal likelihood estimator, information-theoretic methods for proving impossibility results using rate-distortion theory, and methods originated from statistical physics such as interpolation method. To investigate computational limits, we describe a common recipe to construct a randomized polynomial-time reduction scheme that approximately maps instances of the planted clique problem to the problem of interest in total variation distance.