SHARP VARIABLE SELECTION OF A SPARSE SUBMATRIX IN A HIGH-DIMENSIONAL NOISY MATRIX

We observe a N x M matrix of independent, identically distributed Gaussian random variables which are centered except for elements of some submatrix of size n x m where the mean is larger than some a > 0. The submatrix is sparse in the sense that n/N and m/M tend to 0, whereas n, m, N and M tend to infinity. We consider the problem of selecting the random variables with significantly large mean values, as was also considered by [M. Kolar, S. Balakrishnan, A Rinaldo and A. Singh, NIPS (2011)]. We give sufficient conditions on a as a function of n, m, N and M and construct a uniformly consistent procedure in order to do sharp variable selection. We also prove the minimax lower bounds under necessary conditions which are complementary to the previous conditions. The critical values a* separating the necessary and sufficient conditions are sharp (we show exact constants), whereas [M. Kolar, S. Balakrishnan, A. Rinaldo and A. Singh, NIPS (2011)] only prove rate optimality and focus on suboptimal computationally feasible selectors. Note that rate optimality in this problem leaves out a large set of possible parameters, where we do not know whether consistent selection is possible.