A Binning Approach to Quickest Change Detection With Unknown Postchange Distribution

Tze Siong Lau, Wee Peng Tay, Venugopal Varadachari Veeravalli

Research output: Contribution to journalArticle

Abstract

The problem of quickest detection of a change in distribution is considered under the assumption that the prechange distribution is known, and the postchange distribution is only known to belong to a family of distributions distinguishable from a discretized version of the prechange distribution. A sequential change detection procedure is proposed that partitions the sample space into a finite number of bins and monitors the number of samples falling into each of these bins to detect the change. A test statistic that approximates the generalized likelihood ratio test is developed. It is shown that the proposed test statistic can be efficiently computed using a recursive update scheme, and a procedure for choosing the number of bins in the scheme is provided. Various asymptotic properties of the test statistic are derived to offer insights into its performance tradeoff between average detection delay and average run length to false alarm. Testing on synthetic and real data demonstrates that our approach is comparable or better in the performance to existing nonparametric change detection methods.

Original languageEnglish (US)
Article number8537967
Pages (from-to)609-621
Number of pages13
JournalIEEE Transactions on Signal Processing
Volume67
Issue number3
DOIs
StatePublished - Feb 1 2019

Fingerprint

Bins
Statistics
Testing

Keywords

  • Quickest change detection
  • average detection delay
  • average run length
  • generalized likelihood ratio test (GLRT)
  • non-parametric test

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering

Cite this

A Binning Approach to Quickest Change Detection With Unknown Postchange Distribution. / Lau, Tze Siong; Tay, Wee Peng; Veeravalli, Venugopal Varadachari.

In: IEEE Transactions on Signal Processing, Vol. 67, No. 3, 8537967, 01.02.2019, p. 609-621.

Research output: Contribution to journalArticle

@article{09a2f6f8cbb44ce2b20f76db13154b1e,
title = "A Binning Approach to Quickest Change Detection With Unknown Postchange Distribution",
abstract = "The problem of quickest detection of a change in distribution is considered under the assumption that the prechange distribution is known, and the postchange distribution is only known to belong to a family of distributions distinguishable from a discretized version of the prechange distribution. A sequential change detection procedure is proposed that partitions the sample space into a finite number of bins and monitors the number of samples falling into each of these bins to detect the change. A test statistic that approximates the generalized likelihood ratio test is developed. It is shown that the proposed test statistic can be efficiently computed using a recursive update scheme, and a procedure for choosing the number of bins in the scheme is provided. Various asymptotic properties of the test statistic are derived to offer insights into its performance tradeoff between average detection delay and average run length to false alarm. Testing on synthetic and real data demonstrates that our approach is comparable or better in the performance to existing nonparametric change detection methods.",
keywords = "Quickest change detection, average detection delay, average run length, generalized likelihood ratio test (GLRT), non-parametric test",
author = "Lau, {Tze Siong} and Tay, {Wee Peng} and Veeravalli, {Venugopal Varadachari}",
year = "2019",
month = "2",
day = "1",
doi = "10.1109/TSP.2018.2881666",
language = "English (US)",
volume = "67",
pages = "609--621",
journal = "IEEE Transactions on Signal Processing",
issn = "1053-587X",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "3",

}

TY - JOUR

T1 - A Binning Approach to Quickest Change Detection With Unknown Postchange Distribution

AU - Lau, Tze Siong

AU - Tay, Wee Peng

AU - Veeravalli, Venugopal Varadachari

PY - 2019/2/1

Y1 - 2019/2/1

N2 - The problem of quickest detection of a change in distribution is considered under the assumption that the prechange distribution is known, and the postchange distribution is only known to belong to a family of distributions distinguishable from a discretized version of the prechange distribution. A sequential change detection procedure is proposed that partitions the sample space into a finite number of bins and monitors the number of samples falling into each of these bins to detect the change. A test statistic that approximates the generalized likelihood ratio test is developed. It is shown that the proposed test statistic can be efficiently computed using a recursive update scheme, and a procedure for choosing the number of bins in the scheme is provided. Various asymptotic properties of the test statistic are derived to offer insights into its performance tradeoff between average detection delay and average run length to false alarm. Testing on synthetic and real data demonstrates that our approach is comparable or better in the performance to existing nonparametric change detection methods.

AB - The problem of quickest detection of a change in distribution is considered under the assumption that the prechange distribution is known, and the postchange distribution is only known to belong to a family of distributions distinguishable from a discretized version of the prechange distribution. A sequential change detection procedure is proposed that partitions the sample space into a finite number of bins and monitors the number of samples falling into each of these bins to detect the change. A test statistic that approximates the generalized likelihood ratio test is developed. It is shown that the proposed test statistic can be efficiently computed using a recursive update scheme, and a procedure for choosing the number of bins in the scheme is provided. Various asymptotic properties of the test statistic are derived to offer insights into its performance tradeoff between average detection delay and average run length to false alarm. Testing on synthetic and real data demonstrates that our approach is comparable or better in the performance to existing nonparametric change detection methods.

KW - Quickest change detection

KW - average detection delay

KW - average run length

KW - generalized likelihood ratio test (GLRT)

KW - non-parametric test

UR - http://www.scopus.com/inward/record.url?scp=85056739268&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85056739268&partnerID=8YFLogxK

U2 - 10.1109/TSP.2018.2881666

DO - 10.1109/TSP.2018.2881666

M3 - Article

AN - SCOPUS:85056739268

VL - 67

SP - 609

EP - 621

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

SN - 1053-587X

IS - 3

M1 - 8537967

ER -