TY - JOUR
T1 - Linear-Complexity Exponentially-Consistent Tests for Universal Outlying Sequence Detection
AU - Bu, Yuheng
AU - Zou, Shaofeng
AU - Veeravalli, Venugopal V.
N1 - This work was supported in part by the National Science Foundation under Grants NSF 11-11342 and 1617789, through the University of Illinois at Urbana-Champaign.
Manuscript received December 4, 2017; revised September 10, 2018, November 13, 2018, and January 3, 2019; accepted February 13, 2019. Date of publication February 25, 2019; date of current version March 15, 2019. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Romain Couillet. This work was supported in part by the National Science Foundation under Grants NSF 11-11342 and 1617789, through the University of Illinois at Urbana-Champaign. This paper was presented in part at the IEEE International Symposium on Information Theory, Aachen, Germany, June 2017 [1]. (Corresponding author: Venugopal V. Veeravalli.) Y. Bu and V. V. Veeravalli are with the ECE Department and the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA (e-mail:,[email protected]; [email protected]).
PY - 2019/4/15
Y1 - 2019/4/15
N2 - 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.
AB - 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.
KW - Anomaly detection
KW - clustering algorithm
KW - exponential consistency
KW - outlier detection
KW - universal outlier hypothesis testing
UR - http://www.scopus.com/inward/record.url?scp=85063258202&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85063258202&partnerID=8YFLogxK
U2 - 10.1109/TSP.2019.2901364
DO - 10.1109/TSP.2019.2901364
M3 - Article
AN - SCOPUS:85063258202
SN - 1053-587X
VL - 67
SP - 2115
EP - 2128
JO - IEEE Transactions on Signal Processing
JF - IEEE Transactions on Signal Processing
IS - 8
M1 - 8651359
ER -