# Submatrix localization via message passing

arXiv: https://arxiv.org/abs/1510.09219 · HTML: https://mlsanity.com/paper/1510.09219/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2015.

## Built on by (most cited first, 4 of 4)

- [Lattice partition recovery with dyadic CART](https://mlsanity.com/paper/2105.13504/) (2021)
- [A pseudo-likelihood approach to community detection in weighted networks](https://mlsanity.com/paper/2303.05909/) (2023)
- [A Goodness-of-fit Test on the Number of Biclusters in a Relational Data Matrix](https://mlsanity.com/paper/2102.11658/) (2021)
- [Statistical and computational challenges in ranking](https://mlsanity.com/paper/2512.21111/) (2025)

## Abstract (arXiv)

The principal submatrix localization problem deals with recovering a K× K principal submatrix of elevated mean μ in a large n× n 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(√n) ≤ K ≤ o(n), the support of the submatrix can be weakly recovered (with o(K) misclassification errors on average) by an optimized message passing algorithm if λ = μ2K2/n, the signal-to-noise ratio, exceeds 1/e. This extends a result by Deshpande and Montanari previously obtained for K=Theta(√n). 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 K ≥ fracnlog n (frac18e + o(1)). The total running time of the algorithm is O(n2log n). Another version of the submatrix localization problem, known as noisy biclustering, aims to recover a K1× K2 submatrix of elevated mean μ in a large n1× n2 Gaussian matrix. The optimized message passing algorithm and its analysis are adapted to the bicluster problem assuming Omega(√ni) ≤ Ki ≤ o(ni) and K1asymp K2. A sharp information-theoretic condition for the weak recovery of both clusters is also identified.