Robust Projective Clustering Under $L_{2}$ Norm

Hu Ding, Jinhui XuarXiv 2012 · arXiv · OpenReview

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.
Illustration of geometric bounds and rotation techniques used to estimate optimal flats.

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.
Geometric representation of slab partitioning to capture data extent.

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

Abstract

Projective clustering is a problem with both theoretical and practical importance and has received a great deal of attentions in recent years. Given a set of points $P$ in $\mathbb{R}^{d}$ space, projective clustering is to find a set $\mathbb{F}$ of $k$ lower dimensional $j$-flats so that the average distance (or squared distance) from points in $P$ to their closest flats is minimized. Existing approaches for this problem are mainly based on adaptive/volume sampling or core-sets techniques which suffer from several limitations. In this paper, we present the first uniform random sampling based approach for this challenging problem and achieve linear time solutions for three cases, general projective clustering, regular projective clustering, and $L_{\tau}$ sense projective clustering. For the general projective clustering problem, we show that for any given small numbers $0<\gamma, \epsilon <1$, our approach first removes $\gamma|P|$ points as outliers and then determines $k$ $j$-flats to cluster the remaining points into $k$ clusters with an objective value no more than $(1+\epsilon)$ times of the optimal for all points. For regular projective clustering, we demonstrate that when the input points satisfy some reasonable assumption on its input, our approach for the general case can be extended to yield a PTAS for all points. For $L_{\tau}$ sense projective clustering, we show that our techniques for both the general and regular cases can be naturally extended to the $L_{\tau}$ sense projective clustering problem for any $1 \le \tau < \infty$. Our results are based on several novel techniques, such as slab partition, $\Delta$-rotation, symmetric sampling, and recursive projection, and can be easily implemented for applications.
BibTeX
@misc{ding2012robust,
  author = {Hu Ding and Jinhui Xu},
  title = {{Robust Projective Clustering Under $L\_\{2\}$ Norm}},
  year = {2012},
  eprint = {1204.6717},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1204.6717},
}
Figure