Date of Award

December 2019

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Electrical Engineering and Computer Science

Advisor(s)

Pramod K. Varshney

Keywords

non-parametric Hypothesis Testing, random distortion testing, Sequential testing

Subject Categories

Engineering

Abstract

In today’s world, many applications are characterized by the availability of large amounts of complex-structured data. It is not always possible to fit the data to predefined models or distributions. Model dependent signal processing approaches are often susceptible to mismatches between the data and the assumed model. In cases where the data does not conform to the assumed model, providing sufficient performance guarantees becomes a challenging task. Therefore, it is important to devise methods that are model-independent, robust, provide sufficient performance guarantees for the task at hand and, at the same time, are simple to implement. The goal of this dissertation is to develop such algorithms for two-sided sequential binary hypothesis testing.

In this dissertation, we propose two algorithms for sequential non-parametric hypothesis testing. The proposed algorithms are based on the random distortion testing (RDT) framework. The RDT framework addresses the problem of testing whether a random signal observed in additive noise deviates by more than a specified tolerance from a fixed model. The data-based approach is non-parametric in the sense that the underlying signal distributions under each hypothesis are assumed to be unknown. Importantly, we show that the proposed algorithms are not only robust but also provide performance guarantees in the non-asymptotic regimes in contrast to the popular non-parametric likelihood ratio based approaches which provide only asymptotic

performance guarantees.

In the first part of the dissertation, we develop a sequential algorithm SeqRDT. We first introduce a few mild assumptions required to control the error probabilities of the algorithm. We then analyze the asymptotic properties of the algorithm along with the behavior of the thresholds. Finally, we derive the upper bounds on the probabilities of false alarm (PFA) and missed detection (PMD) and demonstrate how to choose the algorithm parameters such that PFA and PMD can be guaranteed to stay below pre-specified levels. Specifically, we present two ways to design the algorithm: We first introduce the notion of a buffer and show that with the help of a few mild assumptions we can choose an appropriate buffer size such that PFA and PMD can be controlled. Later, we eliminate the buffer by introducing additional parameters and show that with the choice of appropriate parameters we can still control the probabilities of error of the algorithm.

In the second part of the dissertation, we propose a truncated (finite horizon) algorithm, TSeqRDT, for the two-sided binary hypothesis testing problem. We first present the optimal fixed-sample-size (FSS) test for the hypothesis testing problem and present a few important preliminary results required to design the truncated algorithm. Similar, to the non-truncated case we first analyze the properties of the thresholds and then derive the upper bounds on PFA and PMD. We then choose the thresholds such that the proposed algorithm not only guarantees the error probabilities to be below pre-specified levels but at the same time makes a decision faster on average compared to its optimal FSS counterpart. We show that the truncated algorithm requires fewer assumptions on the signal model compared to the non-truncated case. We also derive bounds on the average stopping times of the algorithm. Importantly, we study the trade-off between the stopping time and the error probabilities of the algorithm and propose a method to choose the algorithm parameters. Finally, via numerical simulations, we compare the performance of T-SeqRDT and SeqRDT to sequential probability ratio test (SPRT) and composite sequential probability ratio tests. We also show the robustness of the proposed approaches compared to the standard likelihood ratio based approaches.

Access

Open Access

Download

Included in

Engineering Commons

Share

COinS