Active Sampling for Binary Gaussian Model Testing in High Dimensions

A sample $X\in\R^{p}$ is generated according to one of the two known $p$-dimensional Gaussian models. This paper establishes the information-theoretic limits of {\bf actively} sampling the one-dimensional coordinates of $X$ for detecting its true model as $p\to\infty$. We address three questions pertinent to active model detecting. First, we establish conditions under which the problem is feasible under controlled error rates. Secondly, we characterize the information-theoretic lower bound on the coordinate-level sample complexity for model detection. Finally, we provide an active sampling algorithm that progressively identifies the coordinates to be sampled, and prove that this algorithm's sample complexity meets the information-theoretic limit in the asymptote of large $p$.