Statistical Problems with Planted Structures: Information-Theoretical and Computational Limits
Statistical Problems with Planted Structures: Information-Theoretical and Computational Limits
This chapter provides a survey of the common techniques for determining the sharp statistical and computational limits in high-dimensional statistical problems with planted structures, using community detection and submatrix detection problems as illustrative examples. We discuss tools including the first- and second-moment methods for analyzing the maximum-likelihood estimator, information-theoretic methods …