Robust Projective Clustering Under $L_{2}$ Norm
Abstract
Projective clustering is a fundamental problem in data science, aiming to find $k$ lower-dimensional $j$-flats that minimize the average distance from a point set $P \subset \mathbb{R}^d$. Traditional methods using adaptive sampling or core-sets often suffer from super-linear complexities. This paper presents the first linear-time algorithm ($O(nd)$) based on uniform random sampling. By introducing techniques such as symmetric sampling, recursive projection, and slab partition, we provide robust approximation schemes for general, regular, and $L_\tau$ sense projective clustering.
Introduction
Projective clustering generalizes the classic $k$-means problem. Instead of 0-dimensional centers, it seeks $j$-dimensional subspaces (flats) to represent data clusters. This requires simultaneously solving the clustering (partitioning) and the subspace fitting problems. The difficulty increases with the dimensionality $d$ and the number of points $n$. This work overcomes previous limitations by achieving a linear-time solution that is robust to outliers, breaking the super-linear barriers of previous core-set based approaches.
Methodology
The proposed framework departs from complex adaptive sampling in favor of uniform random sampling. The core of the approach lies in four novel geometric techniques:
- Symmetric Sampling: To accurately estimate a cluster's orientation, the algorithm utilizes a sample $S$ and its reflection $-S$ across the cluster mean. This helps identify points that define the "tilt" or rotation of the optimal flat.
- Recursive Projection: A $j$-dimensional flat is constructed iteratively by finding one principal direction at a time and projecting the dataset onto the orthogonal complement, reducing a complex $j$-dimensional problem into simpler 1-dimensional tasks.
- $\Delta$-Rotation: This framework bounds the error when a flat is estimated from a finite sample, ensuring the result is "close enough" to the optimal subspace.
- Slab Partition: This ensures the random sample captures the full extent of the data points, preventing the algorithm from getting stuck in a local, narrow view of the data.
Theoretical Results and Performance
The algorithm is analyzed under three distinct settings:
- General Projective Clustering: For any $\gamma, \epsilon \in (0, 1)$, the algorithm removes $\gamma|P|$ outliers and finds $k$ flats for the remaining points with a $(1+\epsilon)$ approximation factor relative to the optimal for the entire set.
- Regular Projective Clustering: For data following distributions with bounded coefficients of variation (e.g., Gaussian or Erlang), the approach yields a Polynomial Time Approximation Scheme (PTAS).
- $L_\tau$ Sense Clustering: The techniques naturally extend to $L_\tau$ norms ($1 \le \tau < \infty$), providing versatility for various statistical objectives beyond standard Euclidean squared distance.
The overall time complexity is $O(2^{poly(kj/\gamma)} nd)$. While the constant factor is exponential in the number of clusters $k$ and flat dimension $j$, the complexity remains strictly linear with respect to the data size $n$ and ambient dimension $d$. This makes it highly efficient for high-dimensional datasets where $k$ and $j$ are relatively small.
Conclusion
This paper establishes that uniform random sampling is sufficient for robust projective clustering. By reducing a $j$-dimensional fitting problem into a series of 1-dimensional projections, the authors achieve a significant breakthrough in algorithmic efficiency. While the paper is primarily a theoretical contribution, the authors note that these techniques are easily implementable. Future research will focus on empirical testing to evaluate the practical impact of the exponential constant factors in real-world, high-cluster-count scenarios.
Summary updated