Submatrix localization via message passing

zbMath1468.68155arXiv1510.09219MaRDI QIDQ4558513

Bruce Hajek, Jiaming Xu, Yihong Wu

Publication date: 22 November 2018

Full work available at URL: https://arxiv.org/abs/1510.09219

zbMATH Keywords

message passinghigh-dimensional statisticsbiclusteringsubmatrix localizationspectral algorithms computational complexity

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)

Related Items

Computational barriers to estimation from low-degree polynomials, Unnamed Item, Optimal rates for community estimation in the weighted stochastic block model, A goodness-of-fit test on the number of biclusters in a relational data matrix, Distribution-Free, Size Adaptive Submatrix Detection with Acceleration, Convex optimization for the densest subgraph and densest submatrix problems

Uses Software

• LAS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pseudo-likelihood methods for community detection in large sparse networks
• Consistency thresholds for the planted bisection model
• Belief propagation, robust reconstruction and optimal recovery of block models
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Finding large average submatrices in high dimensional data
• Computational barriers in minimax submatrix detection
• Computational and statistical boundaries for submatrix localization in a large noisy matrix
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• The largest eigenvalue of rank one deformation of large Wigner matrices
• Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• The Isotropic Semicircle Law and Deformation of Wigner Matrices
• Exact Recovery in the Stochastic Block Model
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank One Perturbations of Gaussian Tensors
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• Probability Inequalities for Sums of Bounded Random Variables
• Information Limits for Recovering a Hidden Community
• The Rotation of Eigenvectors by a Perturbation. III
• Perturbation bounds in connection with singular value decomposition