Efficient Anomaly Detection via Matrix Sketching

Vatsal Sharan, Parikshit Gopalan, Udi Wieder

Introduction

In high-dimensional data analysis, Principal Component Analysis (PCA) is a gold standard for finding anomalies. Two popular metrics are typically used: rank-$k$ leverage scores (which measure how unusual a point's projection is within the main subspace) and rank-$k$ projection distance (which measures how far a point is from that subspace).

However, traditional PCA-based anomaly detection faces a massive scale challenge. If your data has a dimensionality ($d$) of $10^6$, a standard algorithm needs to compute a $d \times d$ covariance matrix. This requires $O(d^2)$ space—roughly 4 terabytes of RAM for a million dimensions—which is impossible for most systems. Furthermore, in streaming scenarios like monitoring a data center, storing all data points to perform multiple passes is infeasible.

This paper introduces the first streaming algorithms for PCA-based anomaly detection that require only linear or even logarithmic space relative to data dimensionality. By leveraging matrix sketching techniques, the authors provide a way to identify outliers in massive, high-dimensional datasets without the quadratic memory bottleneck.

Matrix Sketching to the Rescue

The authors bridge the gap between matrix sketching and anomaly detection. Matrix sketching involves creating a "compressed" version of a large matrix that preserves its essential spectral properties, such as its principal components.

They propose two main algorithmic frameworks:

  1. Row Space Approximation: This method uses techniques like Frequent Directions or random column projections to create a sketch that approximates the covariance matrix of the rows. This provides pointwise guarantees, meaning the anomaly score for every single data point is accurately approximated. This approach requires $O(d)$ space.
  2. Column Space Approximation: This uses random row projections to approximate the column space. Surprisingly, the authors show that if you only care about preserving anomaly scores on average (identifying most outliers rather than guaranteeing every single one), you can reduce the space requirement to $O(\text{poly}(k) \log d)$. This is a massive win for extremely high-dimensional data.

The theoretical heavy lifting of the paper involves proving new matrix perturbation inequalities. These proofs show that even if the sketch is a "noisy" version of the original matrix, the specific mathematical operators used to calculate leverage scores and projection distances remain remarkably stable.

Key Insights

  • The Pointwise vs. Average-Case Trade-off: The paper proves a lower bound showing that if you want a guarantee for every single point, you must use at least $\Omega(d)$ space. However, by relaxing this to an "average-case" guarantee, you can drop the space requirement to logarithmic levels.
  • Theory vs. Practice: While mathematical proofs suggest that the sketch size ($\ell$) needs to be quite large, experiments revealed that in practice, a sketch size just a few times larger than $k$ (e.g., $\ell = 10k$) is often sufficient for high accuracy.
  • Stability of Subspaces: The core insight is that anomaly scores depend on the top-$k$ subspace. As long as the sketch preserves the "gap" between the $k$-th and $(k+1)$-th singular values, the resulting anomaly scores are robust to the noise introduced by sketching.

Experimental Results

The researchers validated their algorithms on three high-dimensional datasets from the UCI Machine Learning Repository: p53 mutants (biomedical), Dorothea (drug discovery), and RCV1 (text categorization).

Accuracy: On the p53 dataset, the algorithms achieved $F_1$ scores (a measure of precision and recall) above 0.8 while using 10x less space than traditional methods. Row Projection generally outperformed Column Projection in accuracy for a given sketch size, aligning with its stronger theoretical guarantees.

F1 scores for Column and Row Projection on the P53 dataset

Speed: The sketching approach provided consistent speedups of 2x to 6x compared to optimized randomized SVD baselines across the tested datasets.

Execution times comparing SVD to Column and Row Projection

While Row Projection is more accurate, Column Projection's memory footprint is essentially independent of the input dimension $d$, making it the only viable choice for "ultra-high" dimensions.

Limitations and Future Work

The algorithms perform best when the data has a pronounced low-rank structure (i.e., most variance is captured by a few components). On datasets where the low-rank structure is less clear, the approximation quality drops. Additionally, the theoretical guarantees rely on a "separation assumption"—there must be a noticeable gap between the $k$-th and $(k+1)$-th singular values. If the spectrum is very flat, the principal subspace becomes unstable.

Future directions include applying these sketching techniques to other types of subspace-based anomaly detection and exploring their use in more complex, non-linear anomaly detection 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{sharan2018efficient,
  author = {Vatsal Sharan and Parikshit Gopalan and Udi Wieder},
  title = {{Efficient Anomaly Detection via Matrix Sketching}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=H1Wm-Db_br},
}
Figure