Linear-Complexity Exponentially-Consistent Tests for Universal Outlying Sequence Detection

Yuheng Bu, Shaofeng Zou, Venugopal V. Veeravalli

Research output: Contribution to journalArticlepeer-review


The problem of universal outlying sequence detection is studied, where the goal is to detect outlying sequences among M sequences of samples. A sequence is considered as outlying if the observations therein are generated by a distribution different from those generating the observations in the majority of the sequences. In the universal setting, we are interested in identifying all the outlying sequences without knowing the underlying generating distributions. We consider the outlying sequence detection problem in three different scenarios: first, known number of outlying sequences; second, unknown number of identical outlying sequences; and finally, typical and outlying distributions forming clusters. In this paper, a class of tests based on distribution clustering is proposed. These tests are shown to be exponentially consistent with linear time complexity in M. Numerical results demonstrate that our clustering-based tests achieve similar performance to existing tests, while being considerably more computationally efficient.

Original languageEnglish (US)
Article number8651359
Pages (from-to)2115-2128
Number of pages14
JournalIEEE Transactions on Signal Processing
Issue number8
StatePublished - Apr 15 2019


  • Anomaly detection
  • clustering algorithm
  • exponential consistency
  • outlier detection
  • universal outlier hypothesis testing

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering

Cite this