Faster Anomaly Detection via Matrix Sketching

Parikshit Gopalan, Vatsal Sharan, Udi Wieder

Abstract

We consider the problem of finding anomalies in high-dimensional data using popular PCA based anomaly scores. The naive algorithms for computing these scores explicitly compute the PCA of the covariance matrix which uses space quadratic in the dimensionality of the data. We give the first streaming algorithms that use space that is linear or sublinear in the dimension. We prove general results showing that any sketch of a matrix that satisfies a certain operator norm guarantee can be used to approximate these scores. We instantiate these results with powerful matrix sketching techniques such as Frequent Directions and random projections to derive efficient and practical algorithms for these problems, which we validate over real-world data sets. Our main technical contribution is to prove matrix perturbation inequalities for operators arising in the computation of these measures.

Introduction

Anomaly detection in high-dimensional data is a cornerstone of modern system monitoring, from detecting failing servers in a data center to spotting intruders in a network. A popular approach involves using Principal Component Analysis (PCA) to identify a "normal" low-dimensional subspace. Points that are far from this subspace (high projection distance) or look "weird" within it (high leverage scores) are flagged as anomalies.

Geometric representation of PCA-based anomaly scores, illustrating projection distance ($x$) and leverage score ($y$).

However, a major computational hurdle exists: the standard method to find this subspace requires computing a $d \times d$ covariance matrix. For data with a million dimensions ($d = 10^6$), this matrix contains a trillion entries—far too large for most machines to store. Furthermore, in streaming scenarios, we cannot afford to store the entire dataset for a full SVD. This paper introduces the first streaming algorithms for PCA-based anomaly detection that break this "quadratic bottleneck," reducing memory requirements to linear ($O(d)$) or even logarithmic ($O(\text{poly}(k) \log d)$) in the data's dimensionality.

Methodology: Matrix Sketching for Anomalies

The authors bridge the gap between matrix sketching and anomaly detection. A matrix sketch is a compressed version of a large matrix that preserves its essential properties, such as its principal components. Two main algorithmic frameworks are proposed:

  1. Pointwise Guarantees (Algorithm 1): This approach uses sketches like Frequent Directions or random column projections to approximate the row space of the data. It provides a guarantee for every single data point, requiring $O(d)$ memory. The authors prove that any sketch satisfying a specific operator norm guarantee can accurately estimate leverage scores and projection distances.
  2. Average-case Guarantees (Algorithm 2): If preserving most outliers is sufficient, random row projections can reduce memory to $O(\text{poly}(k) \log d)$. This circumvents the theoretical $O(d)$ lower bound necessary for pointwise accuracy.

The core technical contribution involves proving new matrix perturbation inequalities. While classical theory (like Wedin’s Theorem) describes how eigenvectors change under noise, this work extends those results to the specific, more complex operators used for Mahalanobis distances and projection scores.

Experimental Results

The algorithms were evaluated on high-dimensional datasets from the UCI Machine Learning Repository, including p53 mutants (5,409 dimensions), Dorothea (100,000 dimensions), and RCV1 (47,236 dimensions). These represent real-world settings where data typically exhibits a low-rank structure.

Performance of sketching algorithms on the P53 dataset, showing F1 scores for column and row projections across different dimensions.

Key findings include:

  • Space and Speed: On the p53 dataset, the authors achieved $F_1$ scores above 0.8 while using 10x less space than the exact SVD approach. Sketching algorithms were consistently 2x to 6x faster than baseline randomized SVD.
  • Accuracy Trade-offs: Algorithm 1 (Pointwise) generally provided better accuracy, but Algorithm 2 (Average-case) was impressively effective given its tiny memory footprint, which is essentially independent of the input dimension $d$.
  • Robustness: Experiments showed that even when theoretical assumptions (like a large spectral gap) were weakly met, the algorithms performed remarkably well.

Conclusion

The "quadratic wall" in high-dimensional anomaly detection is breakable. By leveraging matrix sketching, it is possible to find the principal subspace and detect outliers with massive speedups and significant space savings. These algorithms are simple to implement and highly practical for production systems, particularly when data is approximately low-rank. Future work may explore these techniques for other anomaly scores and even larger-scale industrial monitoring tasks.

Summary updated

Abstract

We consider the problem of finding anomalies in high-dimensional data using popular PCA based anomaly scores. The naive algorithms for computing these scores explicitly compute the PCA of the covariance matrix which uses space quadratic in the dimensionality of the data. We give the first streaming algorithms that use space that is linear or sublinear in the dimension. We prove general results showing that \emph{any} sketch of a matrix that satisfies a certain operator norm guarantee can be used to approximate these scores. We instantiate these results with powerful matrix sketching techniques such as Frequent Directions and random projections to derive efficient and practical algorithms for these problems, which we validate over real-world data sets. Our main technical contribution is to prove matrix perturbation inequalities for operators arising in the computation of these measures.
BibTeX
@inproceedings{gopalan2018faster,
  author = {Parikshit Gopalan and Vatsal Sharan and Udi Wieder},
  title = {{Faster Anomaly Detection via Matrix Sketching}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=H1Wm-Db_br},
}
Figure