We study the problem of recovering a hidden community of cardinality @math from an @math symmetric data matrix @math , where for distinct indices @math , @math if @math both belong to the community and @math otherwise, for two known probability distributions @math and @math depending on @math . If @math and @math with @math , it reduces to the problem of finding a densely-connected @math -subgraph planted in a large Erd "os-R 'enyi graph; if @math and @math with @math , it corresponds to the problem of locating a @math principal submatrix of elevated means in a large Gaussian random matrix. We focus on two types of asymptotic recovery guarantees as @math : (1) weak recovery: expected number of classification errors is @math ; (2) exact recovery: probability of classifying all indices correctly converges to one. Under mild assumptions on @math and @math , and allowing the community size to scale sublinearly with @math , we derive a set of sufficient conditions and a set of necessary conditions for recovery, which are asymptotically tight with sharp constants. The results hold in particular for the Gaussian case, and for the case of bounded log likelihood ratio, including the Bernoulli case whenever @math and @math are bounded away from zero and infinity. An important algorithmic implication is that, whenever exact recovery is information theoretically possible, any algorithm that provides weak recovery when the community size is concentrated near @math can be upgraded to achieve exact recovery in linear additional time by a simple voting procedure.
The paper of @cite_0 gives sharp results for a Gaussian submatrix recovery problem similar to the one considered here -- see rmk:Butucea_sharp for details.
@cite_0
2963050003
We observe a N × M matrix of independent, identically distributed Gaussian random variables which are centered except for elements of some submatrix of size n × m where the mean is larger than some a > 0. The submatrix is sparse in the sense that n N and m M tend to 0, whereas n, m, N and M tend to infinity. We consider the problem of selecting the random variables with significantly large mean values, as was also considered by [M. Kolar, S. Balakrishnan, A. Rinaldo and A. Singh, NIPS (2011)]. We give sufficient conditions on a as a function of n, m, N and M and construct a uniformly consistent procedure in order to do sharp variable selection. We also prove the minimax lower bounds under necessary conditions which are complementary to the previous conditions. The critical values a ∗ separating the necessary and sufficient conditions are sharp (we show exact constants), whereas [M. Kolar, S. Balakrishnan, A. Rinaldo and A. Singh, NIPS (2011)] only prove rate optimality and focus on suboptimal computationally feasible selectors. Note that rate optimality in this problem leaves out a large set of possible parameters, where we do not know whether consistent selection is possible.