We propose two fast algorithms for abrupt change detection in streaming data that can operate on arbitrary unknown data distributions before and after the change. The first algorithm, $\textsf{MB-GT}$ , computes efficiently the average Euclidean distance between all pairs of data points before and after the hypothesized change. The second algorithm, $\textsf{MB-CUSUM}$ , computes the log-likelihood ratio statistic for the data distributions before and after the change, similarly to the classical CUSUM algorithm, but unlike that algorithm, $\textsf{MB-CUSUM}$ does not need to know the exact distributions, and uses kernel density estimates instead. Although a straightforward computation of the two change statistics would have computational complexity of O(N 4) with respect to the size N of the streaming data buffer, the proposed algorithms are able to use the computational structure of these statistics to achieve a computational complexity of only O(N 2) and memory requirement of O(N). Furthermore, the algorithms perform surprisingly well on dependent observations generated by underlying dynamical systems, unlike traditional change detection algorithms.
['Daniel Nikovski', 'Ankur Jain']
Fast adaptive algorithms for abrupt change detection