Abstract
Principal Component Analysis (PCA) is a fundamental tool for dimensionality reduction, yet its sensitivity to outliers remains a significant challenge. Robust subspace recovery—finding the optimal subset of inliers—is a combinatorial problem that typically forces a choice between fast heuristics and slow, exact methods. This paper presents Chunk-A, an algorithm that bridges this gap by framing outlier detection as a graph search. By integrating "chunk recursive elimination" with A search heuristics, Chunk-A* provides a scalable solution with provable mathematical bounds on sub-optimality.
Introduction
The core challenge in robust subspace recovery is identifying $k$ outliers in a dataset of $n$ points such that their removal minimizes the PCA reconstruction error for the remaining inliers. Standard PCA is notoriously fragile; a single distant outlier can drastically rotate the principal components, leading to misleading results.
While combinatorial search methods like A can find optimal solutions, they suffer from exponential complexity, making them impractical for large datasets. Conversely, ranking heuristics are fast but often fail to find the global optimum in complex data distributions. Chunk-A addresses these limitations by optimizing the search process through data "chunking."
Methodology: The Chunk-A* Algorithm
Chunk-A innovates on traditional A search through three primary mechanisms:
1. Chunking and Super-Children
In a standard A search for outliers, each level of the search tree adds a single point to the outlier set. Chunk-A introduces "chunking," where the algorithm identifies a group (or "chunk") of $c$ potential outliers and processes them as a single "super child" node. This allows the search to skip multiple levels of the tree, drastically reducing the number of nodes explored.
2. Filter Functions for Pruning
To efficiently navigate the search space, the algorithm employs filter functions that calculate lower ($l$) and upper ($u$) bounds on the PCA error based on data eigenvalues. These bounds "sandwich" the true error, allowing the algorithm to prune branches that are mathematically guaranteed not to contain the optimal solution.
3. Iterative Refinement
Following the search, an iterative refinement step is applied. Similar to k-means, it alternates between calculating the PCA subspace and updating the outlier set based on reconstruction errors. This step ensures that even if the initial search was slightly sub-optimal, the final result is highly accurate.
Experimental Evaluation
The researchers tested Chunk-A* across synthetic models (Haystack, Blurryface) and large-scale real-world datasets (Sift, YPMSD, Covtype).
- Scalability: On the
Siftdataset containing 1 million points, Chunk-A* identified outliers in just 65 seconds. In comparison, existing methods like R-graph and iSearch often exceeded memory limits or required significantly more time. - Accuracy: In image-based experiments using the Yale Face Database B, Chunk-A* consistently achieved lower reconstruction errors than established robust methods such as FMS, GGD, and R1PCA.
- Provable Bounds: Unlike purely heuristic methods, Chunk-A* provides a fractional bound, offering a theoretical guarantee on how close the found solution is to the global optimum.
Conclusion
Chunk-A represents a significant advancement in robust outlier detection. By combining the rigor of combinatorial search with the efficiency of chunk-based elimination, it enables high-accuracy subspace recovery on datasets with millions of points. While future work may focus on optimizing performance for sparse data and automated parameter selection, Chunk-A currently stands as a powerful tool for reliable data cleaning and dimensionality reduction.
Full Citation: Wan, G., & Schweitzer, H. (2021). Accelerated Combinatorial Search for Outlier Detection with Provable Bounds on Sub-Optimality. Proceedings of the AAAI Conference on Artificial Intelligence, 35(14), 12436-12444.
Summary updated