Detection of sparse mixtures: fundamental limits and algorithms

In this thesis, we study the sparse mixture detection problem as a binary hypothesis testing problem. Under the null hypothesis, we observe i.i.d. samples from a known noise distribution. Under the alternative hypothesis, we observe i.i.d. samples from a mixture of the noise distribution and signal distribution. The noise and signal distributions, as well as the proportion of signal (sparsity level), are allowed to depend on the sample size such that the proportion of signal in the mixture tends to zero as the sample size tends to infinity. The sparse mixture detection problem has applications in areas such as astrophysics, covert communications, biology and machine learning. There are two basic questions in the sparse mixture detection problem, studied in the large sample size regime: 1. Under what conditions do there exist algorithms that can distinguish pure noise from the presence of signal with vanishing error probability? 2. Can one detect the presence of a signal without knowledge of the particular signal distribution or sparsity level, with vanishing error probability? The first question is that of consistent testing, while the second question is that of adaptive testing. While previous works have studied consistency and adaptivity, particularly in the case of Gaussian signal and noise distributions, it has been shown that different consistent adaptive tests can have very different error probabilities at finite sample sizes. This thesis contributes a more refined look at consistency by studying the fundamental rates at which the error probabilities for the sparse mixture detection problem can be driven to zero with the sample size under mild assumptions on the signal and noise distributions. The fundamental rates of decay of the error probabilities are derived by characterizing the error probabilities of the oracle likelihood ratio test. We illustrate our theory on the Gaussian location model, where the noise distribution is standard Gaussian and the signal distribution is a Gaussian with unit variance and positive mean. This thesis also contributes to the field of adaptive test design. We show that when the signal and noise distributions are specified under a finite alphabet, a variant of Hoeffding's test is adaptive with rates matching the oracle likelihood ratio test. We leverage our results on finite alphabet sparse mixture detection problems to study the general sparse mixture detection problem via quantization. We build adaptive tests for general sparse mixture detection problems by studying tests which quantize the data to two levels via a sample size dependent quantizer, which we term 1-bit quantized tests. As the 1-bit quantized tests have data on a binary alphabet, we are able to precisely analyze the fundamental rate of decay of error probabilities under both hypotheses using our theory. A key contribution of our work is constructing adaptive tests for the sparse mixture detection problem by combining 1-bit quantized tests using different quantizers. The first advantage of our proposed test is that it has lower time and space complexity than other known adaptive tests for the sparse mixture detection problem. The second advantage is ease of theoretical analysis. We show that unlike existing tests such as the Higher Criticism test, our adaptive test construction offers tight control of the rate of decay for the false alarm probability under mild assumptions on the quantizers and noise distribution. We show our proposed test construction is adaptive against all possible signals in Generalized Gaussian location models. Furthermore, in the special case of a Gaussian location model, we show that the proposed adaptive test has near-optimal rate of decay of the miss detection probability, as compared with the oracle likelihood ratio test when both hypotheses are assumed to be equally likely. Numerical results show our test performs competitively with existing state-of-the-art tests