# Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix

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

## Key facts

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

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

- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Informative core identification in complex networks](https://mlsanity.com/paper/2101.06388/) (2021)
- [Multi-Slice Clustering for 3-order Tensor Data](https://mlsanity.com/paper/2109.10803/) (2021)
- [Random Subgraph Detection Using Queries](https://mlsanity.com/paper/2110.00744/) (2021)
- [Computational bottlenecks for denoising diffusions](https://mlsanity.com/paper/2503.08028/) (2025)
- [Lattice partition recovery with dyadic CART](https://mlsanity.com/paper/2105.13504/) (2021)
- [Inferring Hidden Structures in Random Graphs](https://mlsanity.com/paper/2110.01901/) (2021)
- [Planted Bipartite Graph Detection](https://mlsanity.com/paper/2302.03658/) (2023)
- [DBSCAN of Multi-Slice Clustering for Third-Order Tensors](https://mlsanity.com/paper/2303.07768/) (2023)
- [A Goodness-of-fit Test on the Number of Biclusters in a Relational Data Matrix](https://mlsanity.com/paper/2102.11658/) (2021)
- [Logspace Reducibility From Secret Leakage Planted Clique](https://mlsanity.com/paper/2107.11886/) (2021)
- [Statistical and computational challenges in ranking](https://mlsanity.com/paper/2512.21111/) (2025)

## Abstract (arXiv)

The interplay between computational efficiency and statistical accuracy in high-dimensional inference has drawn increasing attention in the literature. In this paper, we study computational and statistical boundaries for submatrix localization. Given one observation of (one or multiple non-overlapping) signal submatrix (of magnitude λ and size km × kn) contaminated with a noise matrix (of size m × n), we establish two transition thresholds for the signal to noise λ/σ ratio in terms of m, n, km, and kn. The first threshold, sf SNRc, corresponds to the computational boundary. Below this threshold, it is shown that no polynomial time algorithm can succeed in identifying the submatrix, under the textithidden clique hypothesis. We introduce adaptive linear time spectral algorithms that identify the submatrix with high probability when the signal strength is above the threshold sf SNRc. The second threshold, sf SNRs, captures the statistical boundary, below which no method can succeed with probability going to one in the minimax sense. The exhaustive search method successfully finds the submatrix above this threshold. The results show an interesting phenomenon that sf SNRc is always significantly larger than sf SNRs, which implies an essential gap between statistical optimality and computational efficiency for submatrix localization.