Universal outlier hypothesis testing

Yun Li, Sirin Nitinawarat, Venugopal V. Veeravalli

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

Abstract

The following outlier hypothesis testing problem is studied in a universal setting. Vector observations are collected each with M ≥ 3 coordinates. When a given coordinate is the outlier, the observations in that coordinate are assumed to be distributed according to the 'outlier' distribution, distinct from the common 'typical' distribution governing the observations in all the other coordinates. Nothing is known about the outlier and the typical distributions except that they are distinct and have full supports. The goal is to design a universal test to best discern the outlier coordinate. A universal test based on the generalized likelihood principle is proposed and is shown to be universally exponentially consistent, and a single-letter characterization of the error exponent achievable by the test is derived. It is shown that as the number of coordinates approaches infinity, our universal test is asymptotically efficient. Specifically, it achieves a limiting error exponent that is equal to the largest achievable error exponent when the outlier and typical distributions are both known.

Original languageEnglish (US)
Title of host publication2013 IEEE International Symposium on Information Theory, ISIT 2013
Pages2666-2670
Number of pages5
DOIs
StatePublished - Dec 19 2013
Event2013 IEEE International Symposium on Information Theory, ISIT 2013 - Istanbul, Turkey
Duration: Jul 7 2013Jul 12 2013

Publication series

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

Other

Other2013 IEEE International Symposium on Information Theory, ISIT 2013
CountryTurkey
CityIstanbul
Period7/7/137/12/13

Fingerprint

Hypothesis Testing
Outlier
Error Exponent
Testing
Likelihood Principle
Distinct
Limiting
Infinity
Observation

ASJC Scopus subject areas

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

Cite this

Li, Y., Nitinawarat, S., & Veeravalli, V. V. (2013). Universal outlier hypothesis testing. In 2013 IEEE International Symposium on Information Theory, ISIT 2013 (pp. 2666-2670). [6620710] (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2013.6620710

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

2013 IEEE International Symposium on Information Theory, ISIT 2013. 2013. p. 2666-2670 6620710 (IEEE International Symposium on Information Theory - Proceedings).

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

Li, Y, Nitinawarat, S & Veeravalli, VV 2013, Universal outlier hypothesis testing. in 2013 IEEE International Symposium on Information Theory, ISIT 2013., 6620710, IEEE International Symposium on Information Theory - Proceedings, pp. 2666-2670, 2013 IEEE International Symposium on Information Theory, ISIT 2013, Istanbul, Turkey, 7/7/13. https://doi.org/10.1109/ISIT.2013.6620710
Li Y, Nitinawarat S, Veeravalli VV. Universal outlier hypothesis testing. In 2013 IEEE International Symposium on Information Theory, ISIT 2013. 2013. p. 2666-2670. 6620710. (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2013.6620710
Li, Yun ; Nitinawarat, Sirin ; Veeravalli, Venugopal V. / Universal outlier hypothesis testing. 2013 IEEE International Symposium on Information Theory, ISIT 2013. 2013. pp. 2666-2670 (IEEE International Symposium on Information Theory - Proceedings).
@inproceedings{784ac654244c41899ce2c468b3046e57,
title = "Universal outlier hypothesis testing",
abstract = "The following outlier hypothesis testing problem is studied in a universal setting. Vector observations are collected each with M ≥ 3 coordinates. When a given coordinate is the outlier, the observations in that coordinate are assumed to be distributed according to the 'outlier' distribution, distinct from the common 'typical' distribution governing the observations in all the other coordinates. Nothing is known about the outlier and the typical distributions except that they are distinct and have full supports. The goal is to design a universal test to best discern the outlier coordinate. A universal test based on the generalized likelihood principle is proposed and is shown to be universally exponentially consistent, and a single-letter characterization of the error exponent achievable by the test is derived. It is shown that as the number of coordinates approaches infinity, our universal test is asymptotically efficient. Specifically, it achieves a limiting error exponent that is equal to the largest achievable error exponent when the outlier and typical distributions are both known.",
author = "Yun Li and Sirin Nitinawarat and Veeravalli, {Venugopal V.}",
year = "2013",
month = "12",
day = "19",
doi = "10.1109/ISIT.2013.6620710",
language = "English (US)",
isbn = "9781479904464",
series = "IEEE International Symposium on Information Theory - Proceedings",
pages = "2666--2670",
booktitle = "2013 IEEE International Symposium on Information Theory, ISIT 2013",

}

TY - GEN

T1 - Universal outlier hypothesis testing

AU - Li, Yun

AU - Nitinawarat, Sirin

AU - Veeravalli, Venugopal V.

PY - 2013/12/19

Y1 - 2013/12/19

N2 - The following outlier hypothesis testing problem is studied in a universal setting. Vector observations are collected each with M ≥ 3 coordinates. When a given coordinate is the outlier, the observations in that coordinate are assumed to be distributed according to the 'outlier' distribution, distinct from the common 'typical' distribution governing the observations in all the other coordinates. Nothing is known about the outlier and the typical distributions except that they are distinct and have full supports. The goal is to design a universal test to best discern the outlier coordinate. A universal test based on the generalized likelihood principle is proposed and is shown to be universally exponentially consistent, and a single-letter characterization of the error exponent achievable by the test is derived. It is shown that as the number of coordinates approaches infinity, our universal test is asymptotically efficient. Specifically, it achieves a limiting error exponent that is equal to the largest achievable error exponent when the outlier and typical distributions are both known.

AB - The following outlier hypothesis testing problem is studied in a universal setting. Vector observations are collected each with M ≥ 3 coordinates. When a given coordinate is the outlier, the observations in that coordinate are assumed to be distributed according to the 'outlier' distribution, distinct from the common 'typical' distribution governing the observations in all the other coordinates. Nothing is known about the outlier and the typical distributions except that they are distinct and have full supports. The goal is to design a universal test to best discern the outlier coordinate. A universal test based on the generalized likelihood principle is proposed and is shown to be universally exponentially consistent, and a single-letter characterization of the error exponent achievable by the test is derived. It is shown that as the number of coordinates approaches infinity, our universal test is asymptotically efficient. Specifically, it achieves a limiting error exponent that is equal to the largest achievable error exponent when the outlier and typical distributions are both known.

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

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

U2 - 10.1109/ISIT.2013.6620710

DO - 10.1109/ISIT.2013.6620710

M3 - Conference contribution

AN - SCOPUS:84890340522

SN - 9781479904464

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2666

EP - 2670

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

ER -