2016/07/18 by Jess Banks, Cristopher Moore, Banks, Jess +8 · 11 citations
Computer Science · Engineering · Mathematics · Physics and Astronomy · #Algorithm #Artificial intelligence #Cluster analysis #Combinatorics #Complex Network Analysis Techniques #Computer science #Data mining #Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Gaussian #Information Theory (cs.IT) #Mathematical analysis #Mathematics #Matrix (chemical analysis) #Null (SQL) #Pattern recognition (psychology) #Physics #Probability (math.PR) #Random Matrices and Applications #Rank (graph theory) #Sparse PCA #Sparse and Compressive Sensing Techniques #Sparse approximation #Statistical Mechanics (cond-mat.stat-mech) #Statistics #Statistics Theory (math.ST) #Upper and lower bounds #cond-mat.dis-nn #cond-mat.stat-mech #cs.IT #math.IT #math.PR #math.ST #stat.TH
paper · pdf · doi:10.48550/arxiv.1607.05222
published in arXiv (Cornell University) (Cornell University) · For sparse PCA and submatrix localization, we determine the information-theoretic threshold exactly in the limit where the number of blocks is large or the signal matrix is very sparse based on a conditional second moment method, closing the factor of root two gap in the first version
openalex publication_date 2016/07/18 · arxiv created 2017/01/23 · arxiv updated 2017/01/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
We study the problem of detecting a structured, low-rank signal matrix corrupted with additive Gaussian noise. This includes clustering in a Gaussian mixture model, sparse PCA, and submatrix localization. Each of these problems is conjectured to exhibit a sharp information-theoretic threshold, below which the signal is too weak for any algorithm to detect. We derive upper and lower bounds on these thresholds by applying the first and second moment methods to the likelihood ratio between these "planted models" and null models where the signal matrix is zero. Our bounds differ by at most a factor of root two when the rank is large (in the clustering and submatrix localization problems, when the number of clusters or blocks is large) or the signal matrix is very sparse. Moreover, our upper bounds show that for each of these problems there is a significant regime where reliable detection is information- theoretically possible but where known algorithms such as PCA fail completely, since the spectrum of the observed matrix is uninformative. This regime is analogous to the conjectured 'hard but detectable' regime for community detection in sparse graphs.