Submatrix localization via message passing

MaRDI QIDQ4558513zbMATH OpenFDO

Authors Bruce Hajek, Yihong Wu, Jiaming Xu

Publication date 22 November 2018

Full work available at URL https://arxiv.org/abs/1510.09219, http://jmlr.csail.mit.edu/papers/v18/17-297.html

zbMATH Keywords

biclusteringhigh-dimensional statisticsmessage passingspectral algorithms computational complexitysubmatrix localization

Mathematics Subject Classification ID

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

Abstract: The principal submatrix localization problem deals with recovering a $KimesK$ principal submatrix of elevated mean $mu$ in a large $nimesn$ symmetric matrix subject to additive standard Gaussian noise. This problem serves as a prototypical example for community detection, in which the community corresponds to the support of the submatrix. The main result of this paper is that in the regime $Omega(sqrtn)leqKleqo(n)$, the support of the submatrix can be weakly recovered (with $o(K)$ misclassification errors on average) by an optimized message passing algorithm if $lambda=m{u}^2{K}^2/n$, the signal-to-noise ratio, exceeds $1/e$. This extends a result by Deshpande and Montanari previously obtained for $K=Theta(sqrtn).$ In addition, the algorithm can be extended to provide exact recovery whenever information-theoretically possible and achieve the information limit of exact recovery as long as $Kgeqfracnlogn(frac18e+o(1))$. The total running time of the algorithm is $O(n^{2}logn)$. Another version of the submatrix localization problem, known as noisy biclustering, aims to recover a $K_{1}imes{K}_2$ submatrix of elevated mean $mu$ in a large $n_{1}imes{n}_2$ Gaussian matrix. The optimized message passing algorithm and its analysis are adapted to the bicluster problem assuming $Omega(sqrt{n}_i)leq{K}_{i}leqo(n_i)$ and $K_{1}asymp{K}_2.$ A sharp information-theoretic condition for the weak recovery of both clusters is also identified.

Recommendations

• Computational and statistical boundaries for submatrix localization in a large noisy matrix
• Near-optimal matrix recovery from random linear measurements
• The overlap gap property in principal submatrix recovery
• Recovering a hidden community beyond the Kesten-Stigum threshold in \(O(| E|\log^\ast| V|)\) time
• Estimation of low-rank matrices via approximate message passing

Cites work

• Algorithms for graph partitioning on the planted partition model
• Belief propagation, robust reconstruction and optimal recovery of block models
• Computational and statistical boundaries for submatrix localization in a large noisy matrix
• Computational barriers in minimax submatrix detection
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Exact Recovery in the Stochastic Block Model
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Finding large average submatrices in high dimensional data
• scientific article; zbMATH DE number 3477793 (Why is no real title available?)
• scientific article; zbMATH DE number 1303602 (Why is no real title available?)
• scientific article; zbMATH DE number 741240 (Why is no real title available?)
• scientific article; zbMATH DE number 3228255 (Why is no real title available?)
• scientific article; zbMATH DE number 3043546 (Why is no real title available?)
• Information Limits for Recovering a Hidden Community
• On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank One Perturbations of Gaussian Tensors
• Perturbation bounds in connection with singular value decomposition
• Probability Inequalities for Sums of Bounded Random Variables
• Pseudo-likelihood methods for community detection in large sparse networks
• Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• The isotropic semicircle law and deformation of Wigner matrices
• The largest eigenvalue of rank one deformation of large Wigner matrices
• The Rotation of Eigenvectors by a Perturbation. III

Cited in

(12)

• Convex optimization for the densest subgraph and densest submatrix problems
• The overlap gap property in principal submatrix recovery
• Approximate message passing algorithms for rotationally invariant matrices
• Computational barriers to estimation from low-degree polynomials
• Optimal rates for community estimation in the weighted stochastic block model
• Computational and statistical boundaries for submatrix localization in a large noisy matrix
• Bayesian model selection with graph structured sparsity
• Distribution-free, size adaptive submatrix detection with acceleration
• A goodness-of-fit test on the number of biclusters in a relational data matrix
• Fundamental limits of low-rank matrix estimation with diverging aspect ratios
• A pseudo-likelihood approach to community detection in weighted networks
• A multiscale cavity method for sublinear-rank symmetric matrix factorization

Describes a project that uses

Uses Software

• LAS

This page was built for publication: Submatrix localization via message passing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4558513)