Detection of a sparse submatrix of a high-dimensional noisy matrix
Authors:
- Yuri I. IngsterYIYuri I. Ingster
Preprint
Abstract
We observe a $N\times M$ matrix $Y_{ij}=s_{ij}+\xi_{ij}$ with $\xi_{ij}\sim\CN(0,1)$ i.i.d. in $i,j$, and $s_{ij}\in\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 test procedures and compute asymptotical detection boundary $a$ in order to have maximal test errors tending 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 $(n,m)$, which is unknown but belongs to 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, second, to matrices of random variables having a distribution from an exponential family (non Gaussian) and, third, to a two-sided alternative for matrices with Gaussian elements.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- On the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrixBernoulli, 2013
- Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticismThe Annals of Statistics, 2011
- Nuclear-norm penalization and optimal rates for noisy low-rank matrix completionThe Annals of Statistics, 2011
- Detection of an anomalous cluster in a networkThe Annals of Statistics, 2011
- Finding large average submatrices in high dimensional dataThe Annals of Applied Statistics, 2009
- Simultaneous analysis of Lasso and Dantzig selectorThe Annals of Statistics, 2009
- Detection of a signal of known shape in a multichannel systemJournal of Mathematical Sciences, 2005
- Higher criticism for detecting sparse heterogeneous mixturesThe Annals of Statistics, 2004