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.
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:
- 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.
- 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.
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