Operationally constrained quickest change detection with multiple post-change distributions

• Main Author: Lau, Tze Siong
• Other Authors: Tay, Wee Peng
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2020
• Subjects: Engineering::Electrical and electronic engineering::Electronic systems::Signal processing
• Online Access: https://hdl.handle.net/10356/143188
• Institution: Nanyang Technological University

Quickest change detection (QCD) is the problem of sequentially detecting a change in the statistical properties of a signal. As sensor and computing technology becomes increasingly pervasive and ubiquitous, QCD has found a wide spectrum of applications, from fraud detection to power system line outage detection. In many of these applications, rather than having one distribution, it is more likely that one of the multiple possible distributions generate the signal in the post-change regime. Furthermore, there are additional constraints due to operational requirements that need to be satisfied in addition to traditional QCD constraints. The research goal of this thesis is to study these problems and develop algorithms for QCD under some of these operational constraints. We first consider the problem of QCD when modeling or estimating the post-change distribution is impractical. A sequential change detection procedure that partitions the sample space into a finite number of bins and detects the change by observing the number of samples that fall into each of these bins is proposed. We developed an algorithm to update the test statistic recursively. Asymptotic properties of the test statistics are derived to offer intuition into its performance trade-off between average run length to a false alarm and the worse case average detection delay. Numerical experiments on synthetic and real data suggest that our proposed method is comparable or better in performance to existing non-parametric change detection methods. Next, we study the situation where the signal may undergo two types of change, nuisance and critical. We consider the problem where we are only interested in detecting the critical change as quickly as possible while not raising a false alarm when there is no change or when a nuisance has taken place. We develop a sequential change detection procedure based on the generalized likelihood ratio (GLR) test statistic and derive a recursive update scheme for this procedure. Our proposed stopping time is shown to be asymptotically optimal in the sense of Lorden, where it is not possible to improve the trade-off between the logarithm of the average run length and the worst-case average detection delay, under mild technical conditions. Furthermore, when the post-change distribution belongs to a parameterized family, we proposed a generalized stopping time and provided a lower bound on its average run length. We show that our proposed stopping time outperforms the finite moving average stopping time and the naive 2-stage stopping procedure via experiments on real and synthetic datasets. Another operational constraint that we study is sampling constraints. We consider the problem of QCD for a signal that is not fully observable and can only be observed using a finite set of actions. We propose a static sampling policy and a stopping rule based on the sampling policy. We show that the GLR CuSum achieves asymptotic optimality with a properly designed sampling policy and formulate an optimization problem for which the sampling policy that achieves asymptotic optimality is a solution. Finally, simulation results on partially observed graph signals show that our proposed approach achieves a much lower average detection delay, compared to a random uniform sampling policy, for large average run lengths. Finally, we consider the problem of QCD while taking privacy considerations into account. We formulate the privacy-aware QCD problem by including a privacy constraint to Lorden’s minimax formulation. We show that the GLR CuSum achieves asymptotic optimality with a properly designed sanitization channel and formulate the design of this sanitization channel as an optimization problem. We develop relaxations for the channel design problem to improve its computational tractability.