Low-Rank Methods in Event Detection

Jakub Marecek, Stathis Maroulis, Vana Kalogeraki, Dimitrios Gunopulos

Abstract

Monitoring of streamed data to detect abnormal behaviour (variously known as event detection, anomaly detection, change detection, or outlier detection) underlies many applications of the Internet of Things. There, one often collects data from a variety of sources, with asynchronous sampling, and missing data. In this setting, one can predict abnormal behavior using low-rank techniques. In particular, we assume that normal observations come from a low-rank subspace, prior to being corrupted by a uniformly distributed noise. Correspondingly, we aim to recover a representation of the subspace, and perform event detection by running point-to-subspace distance query for incoming data. In particular, we use a variant of low-rank factorisation, which considers interval uncertainty sets around "known entries", on a suitable flattening of the input data to obtain a low-rank model. On-line, we compute the distance of incoming data to the low-rank normal subspace and update the subspace to keep it consistent with the seasonal changes present. For the distance computation, we suggest to consider subsampling. We bound the one-sided error as a function of the number of coordinates employed using techniques from learning theory and computational geometry. In our experimental evaluation, we have tested the ability of the proposed algorithm to identify samples of abnormal behavior in induction-loop data from Dublin, Ireland.

Introduction

The Internet of Things (IoT) generates a massive "firehose" of information. In smart city applications, thousands of traffic sensors pulse at high frequencies, creating a data stream that is often voluminous, high-velocity, and "messy"—characterized by missing values and measurement noise. Traditional anomaly detection methods often struggle to scale or handle the inherent sparsity of this data. A key challenge is detecting events, such as accidents or equipment failures, in real-time without being overwhelmed by the dimensionality of the feature space.

The MODULoR Framework

The proposed framework, MODULoR (MOnitoring Distributed systems Using Low-Rank methods), addresses these challenges by modeling "normal" system behavior as a low-rank subspace. The approach consists of three primary stages:

  1. Data Flattening: Raw, asynchronous sensor streams are organized into a large matrix where each row represents a system "snapshot" (e.g., one day of traffic).
  2. Matrix Factorization with Interval Uncertainty: Instead of point estimates, the model assumes the "true" value of a sensor reading lies within an interval $[M_{ij} - \Delta, M_{ij} + \Delta]$. This robust factorization identifies the "normal" subspace while accounting for uniform noise and missing data.
  3. Subsampled Proximity Testing: To determine if new data is anomalous, its distance to the learned subspace is measured. Crucially, this test uses only a small random subset $s$ of coordinates, formulated as a Linear Programming (LP) feasibility problem.
The MODULoR framework architecture, illustrating the pipeline from raw sensor readings to anomaly detection.

Theoretical Guarantees

A significant contribution of this work is the proof that the number of samples $s$ required for a reliable proximity test depends on the rank ($r$) of the subspace and the desired error margin ($\epsilon$), but is independent of the total number of sensors ($n$). Using techniques from computational geometry and PAC (Probably Approximately Correct) learning, the authors demonstrate that the subsampled test has a bounded one-sided error. This independence from ambient dimension allows the system to monitor tens of thousands of sensors with the same computational efficiency as a much smaller network.

Experimental Evaluation and Results

The framework was evaluated using induction-loop traffic data from Dublin, Ireland, featuring 3,432 sensors over nearly a year. The system successfully handled 42% data sparsity without pre-imputation.

Performance and Adaptation

In high-dimensional tests (over 299,000 dimensions), the subsampled proximity test executed in approximately 0.009 seconds. The model also incorporates online adaptation, allowing the "normal" subspace to evolve with seasonal changes. As shown in the performance metrics, online factorization methods can maintain or even improve reconstruction accuracy as more samples are processed compared to static offline models.

Comparison of RMSE for offline and online matrix factorization methods over increasing samples, demonstrating the benefits of online adaptation.

The system achieved near-perfect F1-scores (1.0) for moderate noise levels, demonstrating high precision in distinguishing events from normal fluctuations even under synthetic noise injection.

Conclusion

MODULoR provides a scalable, robust solution for IoT event detection by leveraging low-rank structures and randomized subsampling. By decoupling detection complexity from the total number of sensors and providing theoretical guarantees on error bounds, it offers a path forward for real-time monitoring of massive-scale distributed systems.

Reference: Marecek, J., Maroulis, S., Kalogeraki, V., & Gunopoulos, D. (2021). Low-Rank Methods in Event Detection and Subsampled Point-to-Subspace Proximity Tests. arXiv:1802.03649v3.

Summary updated

Abstract

Monitoring of streamed data to detect abnormal behaviour (variously known as event detection, anomaly detection, change detection, or outlier detection) underlies many applications of the Internet of Things. There, one often collects data from a variety of sources, with asynchronous sampling, and missing data. In this setting, one can predict abnormal behavior using low-rank techniques. In particular, we assume that normal observations come from a low-rank subspace, prior to being corrupted by a uniformly distributed noise. Correspondingly, we aim to recover a representation of the subspace, and perform event detection by running point-to-subspace distance query for incoming data. In particular, we use a variant of low-rank factorisation, which considers interval uncertainty sets around "known entries", on a suitable flattening of the input data to obtain a low-rank model. On-line, we compute the distance of incoming data to the low-rank normal subspace and update the subspace to keep it consistent with the seasonal changes present. For the distance computation, we suggest to consider subsampling. We bound the one-sided error as a function of the number of coordinates employed using techniques from learning theory and computational geometry. In our experimental evaluation, we have tested the ability of the proposed algorithm to identify samples of abnormal behavior in induction-loop data from Dublin, Ireland.
BibTeX
@article{marecek2022low,
  author = {Jakub Marecek and Stathis Maroulis and Vana Kalogeraki and Dimitrios Gunopulos},
  title = {{Low-Rank Methods in Event Detection}},
  journal = {IEEE Access},
  year = {2022},
  doi = {10.1109/access.2022.3152206},
}
Figure