Real-Time Nonparametric Anomaly Detection in High-Dimensional Settings
  Timely detection of abrupt anomalies is crucial for real-time monitoring and
security of modern systems producing high-dimensional data. With this goal, we
propose effective and scalable algorithms. Proposed algorithms are
nonparametric as both the nominal and anomalous multivariate data distributions
are assumed unknown. We extract useful univariate summary statistics and
perform anomaly detection in a single-dimensional space. We model anomalies as
persistent outliers and propose to detect them via a cumulative sum-like
algorithm. In case the observed data have a low intrinsic dimensionality, we
learn a submanifold in which the nominal data are embedded and evaluate whether
the sequentially acquired data persistently deviate from the nominal
submanifold. Further, in the general case, we learn an acceptance region for
nominal data via Geometric Entropy Minimization and evaluate whether the
sequentially observed data persistently fall outside the acceptance region. We
provide an asymptotic lower bound and an asymptotic approximation for the
average false alarm period of the proposed algorithm. Moreover, we provide a
sufficient condition to asymptotically guarantee that the decision statistic of
the proposed algorithm does not diverge in the absence of anomalies.
Experiments illustrate the effectiveness of the proposed schemes in quick and
accurate anomaly detection in high-dimensional settings.
