Distribution-Free, Size Adaptive Submatrix Detection with Acceleration

Abstract

Given a large matrix containing independent data entries, we consider the problem of detecting a submatrix inside the data matrix that contains larger-than-usual values. Different from previous literature, we do not have exact information about the dimension of the potential elevated submatrix. We propose a Bonferroni type testing procedure based on permutation tests, and show that our proposed test loses no first-order asymptotic power compared to tests with full knowledge of potential elevated submatrix. In order to speed up the calculation during the test, an approximation net is constructed and we show that Bonferroni type permutation test on the approximation net loses no power on the first order asymptotically.

References in corpus (6)

• 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
• Computational barriers in minimax submatrix detection
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Submatrix localization via message passing
• Information Limits for Recovering a Hidden Community