Detection and Localization of a Submatrix: Theory, Methods and Algorithms

摘要

We consider the problem of detecting and localizing an submatrix with larger-than-usual entries inside a large, noisy matrix. This problem arises from analysis of data in genetics, bioinformatics, and social sciences. We consider that entries of the data matrix are independently following distributions from a natural exponential family, which generalizes the common Gaussian assumptions in the literature. In Chapter 2 a permutation test for testing the existence of the elevated submatrix is studied. The test's asymptotic power is illustrated, and its robust variation (rank method) is also studied. In The latter part of Chapter 2 and Chapter 3 we remove the prior knowledge of the submatrix size, aiming to develop adaptive methods for detection and localization. Latter part of Chapter 2 proposes a Bonferroni testing framework based on the permutation scan test, to solve the detection problem. An accelerating framework is also developed without sacricing asymptotic power. In Chapter 3, a new size-adaptive estimator is proposed to solve the localization problem. Its asymptotic performance is studied, and two fast algorithms to approximate the estimator are developed.