Detection of a sparse submatrix of a high-dimensional noisy matrix

Abstract

We observe a $N\times M$ matrix $Y_{ij}=s_{ij}+{\xi }_{ij}$ with ${\xi }_{ij}\sim \mathcal{N}(0,1)$ i.i.d. in $i,j$, and $s_{ij}\in \mathbb{R}$. We test the null hypothesis $s_{ij}=0$ for all $i,j$ against the alternative that there exists some submatrix of size $n\times m$ with significant elements in the sense that $s_{ij}\ge a>0$. We propose a test procedure and compute the asymptotical detection boundary $a$ so that the maximal testing risk tends to 0 as $M\to \infty$, $N\to \infty$, $p=n/N\to 0$, $q=m/M\to 0$. We prove that this boundary is asymptotically sharp minimax under some additional constraints. Relations with other testing problems are discussed. We propose a testing procedure which adapts to unknown $(n,m)$ within some given set and compute the adaptive sharp rates. The implementation of our test procedure on synthetic data shows excellent behavior for sparse, not necessarily squared matrices. We extend our sharp minimax results in different directions: first, to Gaussian matrices with unknown variance, next, to matrices of random variables having a distribution from an exponential family (non-Gaussian) and, finally, to a two-sided alternative for matrices with Gaussian elements.

Published in at http://dx.doi.org/10.3150/12-BEJ470 the Bernoulli (http://isi.cbs.nl/bernoulli/) by the International Statistical Institute/Bernoulli Society (http://isi.cbs.nl/BS/bshome.htm)

References in corpus (2)

• Finding large average submatrices in high dimensional data
• On the maximal size of Large-Average and ANOVA-fit Submatrices in a Gaussian Random Matrix

Cited by in corpus (40)

• Optimal detection of sparse principal components in high dimension
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Higher Criticism for Large-Scale Inference, Especially for Rare and Weak Effects
• Computational barriers in minimax submatrix detection
• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
• Computational Barriers to Estimation from Low-Degree Polynomials
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Computational Lower Bounds for Community Detection on Random Graphs
• Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
• Rate Optimal Denoising of Simultaneously Sparse and Low Rank Matrices
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Detecting positive correlations in a multivariate sample
• Submatrix localization via message passing
• The Overlap Gap Property in Principal Submatrix Recovery
• Adaptive sensing performance lower bounds for sparse signal detection and support estimation
• Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
• Universality of Computational Lower Bounds for Submatrix Detection
• Adaptive Sensing for Estimation of Structured Sparse Signals
• Sharp Computational-Statistical Phase Transitions via Oracle Computational Model
• Energy Landscape for large average submatrix detection problems in Gaussian random matrices
• Volume Ratio, Sparsity, and Minimaxity under Unitarily Invariant Norms
• Information Limits for Recovering a Hidden Community
• Weak Detection in the Spiked Wigner Model with General Rank
• Weak detection in the spiked Wigner model
• Lattice partition recovery with dyadic CART
• Detecting a planted community in an inhomogeneous random graph
• Statistical Limits of Convex Relaxations
• A Multiscale Scan Statistic for Adaptive Submatrix Localization
• Sparse Sliced Inverse Regression Via Lasso
• Distribution-Free, Size Adaptive Submatrix Detection with Acceleration
• Sparse Anomaly Detection Across Referentials: A Rank-Based Higher Criticism Approach
• Detection of Correlations with Adaptive Sensing
• Disagreement-Based Combinatorial Pure Exploration: Sample Complexity Bounds and an Efficient Algorithm
• Quantifying and Reducing Bias in Maximum Likelihood Estimation of Structured Anomalies
• Sharp Signal Detection Under Ferromagnetic Ising Models
• The Sparse Poisson Means Model
• Distribution-free Detection of a Submatrix
• Logspace Reducibility From Secret Leakage Planted Clique
• Random Subgraph Detection Using Queries
• Minimax rates for sparse signal detection under correlation