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

By Cristina Butucea, Yu. I. Ingster. 2011

136 citations recorded by the source corpus.

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\to0$, $q=m/M\to0$. 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.

Subfields: Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/c71039eb13bd739df0374240cdbc393e527bb73e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistics and Probability

Citations in the corpus

Finding and Leveraging Structure in Learning Problems (2012, methodology): “When data matrix is observed directly, Butucea and Ingster [37] study the problem of detection, while Kolar et al.”
High-dimensional change-point detection with sparse alternatives (2013, result): “Recently, Butucea and Ingster (2013) obtained similar results for the problem of detection of a sparse submatrix of a noisy matrix of growing size.”