Universal sequential outlier hypothesis testing

Yun Li, Sirin Nitinawarat, Venugopal Varadachari Veeravalli

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Universal outlier hypothesis testing is studied in a sequential setting. Multiple observation sequences are collected, one of which is an outlier. Observations in the outlier sequence are generated by a unique mechanism, different from that generating the observations in all other sequences. The goal is to design a universal test to best discern the outlier sequence with the fewest observations on average. Based on the Multihypothesis Sequential Probability Ratio Test and the generalized likelihood test, a universal test is proposed and shown to be universally exponentially consistent. A lower bound on the achievable error exponents of such a test is derived. The proposed test can be modified to accommodate an additional null hypothesis with no outlier. In particular, it is shown to be consistent under the null hypothesis while retaining universally exponential consistency under all other hypotheses.

Original languageEnglish (US)
Title of host publication2014 IEEE International Symposium on Information Theory, ISIT 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages3205-3209
Number of pages5
ISBN (Print)9781479951864
DOIs
StatePublished - Jan 1 2014
Event2014 IEEE International Symposium on Information Theory, ISIT 2014 - Honolulu, HI, United States
Duration: Jun 29 2014Jul 4 2014

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095

Other

Other2014 IEEE International Symposium on Information Theory, ISIT 2014
CountryUnited States
CityHonolulu, HI
Period6/29/147/4/14

Fingerprint

Hypothesis Testing
Outlier
Testing
Null hypothesis
Error Exponent
Sequential Probability Ratio Test
Likelihood
Lower bound
Observation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Cite this

Li, Y., Nitinawarat, S., & Veeravalli, V. V. (2014). Universal sequential outlier hypothesis testing. In 2014 IEEE International Symposium on Information Theory, ISIT 2014 (pp. 3205-3209). [6875426] (IEEE International Symposium on Information Theory - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2014.6875426

Universal sequential outlier hypothesis testing. / Li, Yun; Nitinawarat, Sirin; Veeravalli, Venugopal Varadachari.

2014 IEEE International Symposium on Information Theory, ISIT 2014. Institute of Electrical and Electronics Engineers Inc., 2014. p. 3205-3209 6875426 (IEEE International Symposium on Information Theory - Proceedings).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Li, Y, Nitinawarat, S & Veeravalli, VV 2014, Universal sequential outlier hypothesis testing. in 2014 IEEE International Symposium on Information Theory, ISIT 2014., 6875426, IEEE International Symposium on Information Theory - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 3205-3209, 2014 IEEE International Symposium on Information Theory, ISIT 2014, Honolulu, HI, United States, 6/29/14. https://doi.org/10.1109/ISIT.2014.6875426
Li Y, Nitinawarat S, Veeravalli VV. Universal sequential outlier hypothesis testing. In 2014 IEEE International Symposium on Information Theory, ISIT 2014. Institute of Electrical and Electronics Engineers Inc. 2014. p. 3205-3209. 6875426. (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2014.6875426
Li, Yun ; Nitinawarat, Sirin ; Veeravalli, Venugopal Varadachari. / Universal sequential outlier hypothesis testing. 2014 IEEE International Symposium on Information Theory, ISIT 2014. Institute of Electrical and Electronics Engineers Inc., 2014. pp. 3205-3209 (IEEE International Symposium on Information Theory - Proceedings).
@inproceedings{36ae7e30f3774868b9224a3174197087,
title = "Universal sequential outlier hypothesis testing",
abstract = "Universal outlier hypothesis testing is studied in a sequential setting. Multiple observation sequences are collected, one of which is an outlier. Observations in the outlier sequence are generated by a unique mechanism, different from that generating the observations in all other sequences. The goal is to design a universal test to best discern the outlier sequence with the fewest observations on average. Based on the Multihypothesis Sequential Probability Ratio Test and the generalized likelihood test, a universal test is proposed and shown to be universally exponentially consistent. A lower bound on the achievable error exponents of such a test is derived. The proposed test can be modified to accommodate an additional null hypothesis with no outlier. In particular, it is shown to be consistent under the null hypothesis while retaining universally exponential consistency under all other hypotheses.",
author = "Yun Li and Sirin Nitinawarat and Veeravalli, {Venugopal Varadachari}",
year = "2014",
month = "1",
day = "1",
doi = "10.1109/ISIT.2014.6875426",
language = "English (US)",
isbn = "9781479951864",
series = "IEEE International Symposium on Information Theory - Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "3205--3209",
booktitle = "2014 IEEE International Symposium on Information Theory, ISIT 2014",
address = "United States",

}

TY - GEN

T1 - Universal sequential outlier hypothesis testing

AU - Li, Yun

AU - Nitinawarat, Sirin

AU - Veeravalli, Venugopal Varadachari

PY - 2014/1/1

Y1 - 2014/1/1

N2 - Universal outlier hypothesis testing is studied in a sequential setting. Multiple observation sequences are collected, one of which is an outlier. Observations in the outlier sequence are generated by a unique mechanism, different from that generating the observations in all other sequences. The goal is to design a universal test to best discern the outlier sequence with the fewest observations on average. Based on the Multihypothesis Sequential Probability Ratio Test and the generalized likelihood test, a universal test is proposed and shown to be universally exponentially consistent. A lower bound on the achievable error exponents of such a test is derived. The proposed test can be modified to accommodate an additional null hypothesis with no outlier. In particular, it is shown to be consistent under the null hypothesis while retaining universally exponential consistency under all other hypotheses.

AB - Universal outlier hypothesis testing is studied in a sequential setting. Multiple observation sequences are collected, one of which is an outlier. Observations in the outlier sequence are generated by a unique mechanism, different from that generating the observations in all other sequences. The goal is to design a universal test to best discern the outlier sequence with the fewest observations on average. Based on the Multihypothesis Sequential Probability Ratio Test and the generalized likelihood test, a universal test is proposed and shown to be universally exponentially consistent. A lower bound on the achievable error exponents of such a test is derived. The proposed test can be modified to accommodate an additional null hypothesis with no outlier. In particular, it is shown to be consistent under the null hypothesis while retaining universally exponential consistency under all other hypotheses.

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

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

U2 - 10.1109/ISIT.2014.6875426

DO - 10.1109/ISIT.2014.6875426

M3 - Conference contribution

AN - SCOPUS:84906535256

SN - 9781479951864

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 3205

EP - 3209

BT - 2014 IEEE International Symposium on Information Theory, ISIT 2014

PB - Institute of Electrical and Electronics Engineers Inc.

ER -