Quickest change detection under post-change non-stationarity and uncertainty

Liang, Yuchen

Permalink

https://hdl.handle.net/2142/121436 Copy

Description

Title

Quickest change detection under post-change non-stationarity and uncertainty

Author(s)

Liang, Yuchen

Issue Date

2023-07-12

Director of Research (if dissertation) or Advisor (if thesis)

Veeravalli, Venugopal V.

Doctoral Committee Chair(s)

Veeravalli, Venugopal V.

Committee Member(s)

• Fellouris, Georgios
• Bose, Subhonmesh
• Moustakides, George V.

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Quickest change detection (QCD)
• non-stationary observations
• non-parametric methods
• density estimation
• minimax robust detection
• Wasserstein distance

Abstract

The problem of quickest change detection in a sequence of independent observations is considered. Given sequential observations, the problem aims to detect the change after it occurs as quickly as possible, subject to false alarm constraints. The goal of this dissertation is to extend classical theories of quickest change detection for cases where the post-change observations are non-stationary, and/or where the post-change distribution is not fully known nor belongs to known parametric families. The first problem considered is the mean-change detection problem, where a change in the mean of an observation sequence above some threshold is of interest. The post-change observations are allowed to be non-stationary, and no knowledge of the post-change distribution is assumed other than that its mean is above the threshold. The problem is formulated as a robust change detection problem, and the Mean-Change Test (MCT) is derived, which is shown to be asymptotically close to the minimax robust solution. In the second problem, the post-change observations are assumed non-stationary with possible parametric uncertainty in their distribution, where this non-stationarity is characterized by the cumulative Kullback-Leibler divergence between the post- and the pre-change distributions. A universal asymptotic lower bound on the delay is derived. For the case where the post-change distributions have parametric uncertainty, a window-limited (WL) generalized likelihood-ratio (GLR) CuSum test is developed which is shown to be asymptotically optimal. The use of the WL-GLR-CuSum test in monitoring pandemics is also demonstrated. The next two problems focus on observation models where there is a lack of concrete knowledge of the post-change distribution. In the third problem, it is assumed that the only information about the post-change distribution is through a (small) set of training data. The problem is formulated as a data-driven robust change detection problem, where the post-change uncertainty set is constructed using the Wasserstein distance from the empirical distribution. The distributionally robust (DR) CuSum test is constructed and is shown to be asymptotically minimax robust. The size of the uncertainty set is theoretically characterized using Wasserstein concentration bounds. In the last problem, it is assumed that the post-change distribution is completely unknown. Two tests, the window-limited non-parametric generalized likelihood ratio (NGLR) CuSum test and the non-parametric window-limited adaptive (NWLA) CuSum test, are developed with generic density estimators. Both tests do not require any pre-collected training samples. The tests are shown to achieve first-order asymptotic optimality under certain convergence conditions on the density estimator.

Graduation Semester

2023-08

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Yuchen Liang

Owning Collections