Files in this item
Files  Description  Format 

application/pdf LIGODISSERTATION2017.pdf (1MB)  (no description provided) 
Description
Title:  Detection of sparse mixtures: fundamental limits and algorithms 
Author(s):  Ligo, Jonathan Gillmore 
Director of Research:  Veeravalli, Venugopal V. 
Doctoral Committee Chair(s):  Veeravalli, Venugopal V. 
Doctoral Committee Member(s):  Moulin, Pierre; Moustakides, George V; Varshney, Lav R. 
Department / Program:  Electrical & Computer Eng 
Discipline:  Electrical & Computer Engr 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Sparse mixture
Hypothesis testing Adaptive testing Error exponents Rate analysis Higher criticism Gaussian mixture model Mixture model 
Abstract:  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 1bit quantized tests. As the 1bit 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 1bit 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 nearoptimal 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 stateoftheart tests. 
Issue Date:  20170922 
Type:  Text 
URI:  http://hdl.handle.net/2142/99295 
Rights Information:  Copyright 2017 Jonathan Gillmore Ligo 
Date Available in IDEALS:  20180313 
Date Deposited:  201712 
This item appears in the following Collection(s)

Dissertations and Theses  Electrical and Computer Engineering
Dissertations and Theses in Electrical and Computer Engineering 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois