Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices

Yudong Chen, Jiaming Xu

Type: Preprint

Publication Date: 2014-01-01

Citations: 158

DOI: https://doi.org/10.48550/arxiv.1402.1267

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices	2014	Yudong Chen Jiaming Xu
+	Statistical-Computational Phase Transitions in Planted Models: The High-Dimensional Setting	2014	Yudong Chen Jiaming Xu
+	Semidefinite Programs for Exact Recovery of a Hidden Community	2016	Bruce Hajek Yihong Wu Jiaming Xu
+	Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices	2016	ChenYudong XuJiaming
+	Universality of Computational Lower Bounds for Submatrix Detection	2019	Matthew Brennan Guy Bresler Wasim Huleihel
+	Universality of Computational Lower Bounds for Submatrix Detection	2019	Matthew Brennan Guy Bresler Wasim Huleihel
+ PDF Chat	Statistical Problems with Planted Structures: Information-Theoretical and Computational Limits	2021	Yihong Wu Jiaming Xu
+	Statistical Problems with Planted Structures: Information-Theoretical and Computational Limits	2018	Yihong Wu Jiaming Xu
+	Clustering Sparse Graphs	2012	Yudong Chen Sujay Sanghavi Huan Xu
+	Detection and Recovery of Hidden Submatrices	2023	Marom Dadon Wasim Huleihel Tamir Bendory
+	Spectral Algorithms Optimally Recover Planted Sub-structures	2022	Souvik Dhara Julia Gaudio Elchanan Mossel Colin Sandon
+	Clustering Without an Eigengap	2023	Matthew Zurek Yudong Chen
+	Statistical and Computational Limits of Detecting and Recovering Hidden Submatrices	2024	Marom Dadon Wasim Huleihel Tamir Bendory
+	Information Limits for Recovering a Hidden Community	2015	Bruce Hajek Yihong Wu Jiaming Xu
+	Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization	2018	Jess Banks Cristopher Moore Roman Vershynin Nicolas Verzélen Jiaming Xu
+ PDF Chat	Improved Graph Clustering	2014	Yudong Chen Sujay Sanghavi Huan Xu
+ PDF Chat	Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization	2017	Jess Banks Cristopher Moore Roman Vershynin Nicolas Verzélen Jiaming Xu
+	Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization	2016	Jess Banks Cristopher Moore Nicolas Verzélen Roman Vershynin Jiaming Xu
+	Statistical and computational thresholds for the planted $k$-densest sub-hypergraph problem	2020	Luca Corinzia P. La Penna Wojciech Szpankowski Joachim M. Buhmann
+ PDF Chat	Improved graph clustering	2013	Yudong Chen Sujay Sanghavi Huan Xu

Works That Cite This (127)

Action	Title	Year	Authors
+	Information Limits for Recovering a Hidden Community	2017	Bruce Hajek Yihong Wu Jiaming Xu
+	Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization	2018	Jess Banks Cristopher Moore Roman Vershynin Nicolas Verzélen Jiaming Xu
+	Exact recovery in the hypergraph stochastic block model: A spectral algorithm	2020	Sam Cole Yizhe Zhu
+ PDF Chat	Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisons	2019	Nihar B. Shah Sivaraman Balakrishnan Martin J. Wainwright
+	Crossing the KS threshold in the stochastic block model with information theory	2016	Emmanuel Abbé Colin Sandon
+	Exact recovery in the binary stochastic block model with binary side information	2017	Hussein Saad Ahmed Attia Abotabl Aria Nosratinia
+	Universality of Computational Lower Bounds for Submatrix Detection	2019	Matthew Brennan Guy Bresler Wasim Huleihel
+	Sharp Computational-Statistical Phase Transitions via Oracle Computational Model	2015	Zhaoran Wang Quanquan Gu Han Liu
+	The Overlap Gap Property in Principal Submatrix Recovery	2019	David Gamarnik Aukosh Jagannath Subhabrata Sen
+	Exponential error rates of SDP for block models: Beyond Grothendieck's inequality	2017	Yingjie Fei Yudong Chen

Works Cited by This (65)

Action	Title	Year	Authors
+	A simple SVD algorithm for finding hidden partitions	2014	Van Vu
+	Random graph dynamics	2007	Richard Durrett
+	Computational barriers in minimax submatrix detection	2015	Zongming Ma Yihong Wu
+	Random Laplacian matrices and convex relaxations	2015	Afonso S. Bandeira
+	Spectral partitioning of random graphs	2001	Frank McSherry
+	Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms.	2015	Emmanuel Abbé Colin Sandon
+	Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions	2015	Bruce Hajek Yihong Wu Jiaming Xu
+ PDF Chat	Energy landscape for large average submatrix detection problems in Gaussian random matrices	2017	Shankar Bhamidi Partha S. Dey Andrew B. Nobel
+ PDF Chat	Reconstruction and estimation in the planted partition model	2014	Elchanan Mossel Joseph Neeman Allan Sly
+	Matrix estimation by Universal Singular Value Thresholding	2014	Sourav Chatterjee