Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
arXiv:1502.01988 · doi:10.1214/16-AOS1488
Abstract
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 ) contaminated with a noise matrix (of size ), we establish two transition thresholds for the signal to noise ratio in terms of , , , and . The first threshold, , corresponds to the computational boundary. Below this threshold, it is shown that no polynomial time algorithm can succeed in identifying the submatrix, under the \textit{hidden clique hypothesis}. We introduce adaptive linear time spectral algorithms that identify the submatrix with high probability when the signal strength is above the threshold . The second threshold, , 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 is always significantly larger than , which implies an essential gap between statistical optimality and computational efficiency for submatrix localization.
arXiv comment37 pages, 1 figure
References in corpus (17)
- The Convex Geometry of Linear Inverse Problems
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Higher criticism for detecting sparse heterogeneous mixtures
- Sparse PCA: Optimal rates and adaptive estimation
- Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions
- Optimal detection of sparse principal components in high dimension
- Detection of an anomalous cluster in a network
- Computational and Statistical Tradeoffs via Convex Relaxation
- Finding large average submatrices in high dimensional data
- Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
- Minimax risk of matrix denoising by singular value thresholding
- Computational barriers in minimax submatrix detection
- Detection of a sparse submatrix of a high-dimensional noisy matrix
- Phase Transitions in Semidefinite Relaxations
- Lower bounds on the performance of polynomial-time algorithms for sparse linear regression
- Computational Lower Bounds for Sparse PCA
- Statistical and computational trade-offs in estimation of sparse principal components