Linear Time Algorithm for Projective Clustering

Hu Ding, Jinhui XuarXiv 2012 · DOI · arXiv

Abstract

Projective clustering is a problem with both theoretical and practical importance and has received a great deal of attention 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 < \epsilon, \gamma < 1$, a $(1+\epsilon)$ approximation for $(1-\gamma)n$ points can be found in $O(2^{poly(kj/\gamma)}nd)$ time.

Introduction

In data science and computational geometry, projective clustering involves finding a set of $k$ lower-dimensional "flats" (such as lines or planes) that best fit a cloud of $n$ points in $d$-dimensional space. The objective is to minimize the average distance from each point to its nearest flat. This problem is notoriously difficult; while fitting a single line ($k=1, j=1$) is straightforward, the computational cost typically explodes as the number of clusters ($k$) and the dimensions of the flats ($j$) increase.

Existing solutions often suffer from super-linear time complexity or require specific data constraints, such as integer coordinates. This research introduces a truly linear-time algorithm—one where processing time scales directly with the number of points $n$, independent of the dimensionality $d$ in the sampling phase.

Methodology

The core innovation of this work is the shift from complex "adaptive sampling" (where points are selected based on previous choices) to uniform random sampling. To bridge the gap between simple sampling and high-accuracy clustering, the authors introduce several novel geometric tools:

Symmetric Sampling and Recursive Projection

Standard sampling often fails to capture the orientation of a flat. The authors utilize Symmetric Sampling, taking a random sample $S$ and creating a reflected set $-S$ across the mean. By examining subsets of $S \cup -S$, the algorithm identifies "steering points" that define the orientation of the optimal flat.

To find a $j$-dimensional flat, the algorithm employs Recursive Projection: it identifies one direction, projects all points onto a subspace perpendicular to that direction, and repeats the process. This builds a hierarchical tree of candidate flats.

Geometric Approximation Tools

Two critical frameworks ensure the accuracy of these samples:

  1. $\Delta$-Rotation: A mathematical framework that bounds the increase in clustering error when a flat is slightly rotated. This allows the algorithm to accept a "good-enough" flat found via sampling without exhaustive searching.
  2. Slab Partition: This method divides the space into "slabs" to ensure that the random sample effectively represents the spread of the data, preventing the algorithm from being misled by localized point densities.
Figure 3: Geometric illustration of the approximation bounds and rotation framework used to settle on candidate flats.
Figure 6: Illustration of the slab partition method, showing the boundaries used to ensure representative sampling across the data spread.

Key Insights

  • Uniformity is Sufficient: The research demonstrates that uniform random sampling is sufficient to solve projective clustering when combined with the right projection techniques, challenging the previous assumption that complex "volume sampling" was necessary.
  • Bicriteria Approximation for Outliers: For general datasets, the algorithm provides a bicriteria approximation: it fits $(1-\gamma)n$ points to achieve a tight $(1+\epsilon)$ error bound, effectively handling potential outliers.
  • Regularity Advantages: If the data follows a "regular" distribution (e.g., Gaussian), the algorithm provides a full Polynomial Time Approximation Scheme (PTAS) without needing to exclude any points.

Results and Complexity

The algorithm achieves a linear time complexity of $O(nd)$, specifically $O(2^{poly(kj/\gamma)}nd)$. This makes it highly scalable for "Big Data" applications where $n$ is extremely large, provided that the number of clusters $k$ and the flat dimension $j$ remain small constants.

The paper successfully provides linear-time solutions for:

  1. General Projective Clustering: $(1+\epsilon)$ approximation for the majority of points.
  2. Regular Projective Clustering: A PTAS for all points in well-behaved distributions.
  3. $L_\tau$ Sense Clustering: Extensions to various distance measures beyond squared distance.

Conclusion and Future Work

While the algorithm is theoretically linear in $n$, the constant factor is exponential in $k$ and $j$. This suggests the algorithm is most effective for high-volume datasets with a small number of target clusters. Future research may focus on empirical testing against heuristic methods like $k$-means variations and applying these symmetric sampling and slab partition techniques to other high-dimensional geometric problems.

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_τ$ sense projective clustering. For the general projective clustering problem, we show that for any given small numbers $0
BibTeX
@misc{ding2012linear,
  author = {Hu Ding and Jinhui Xu},
  title = {{Linear Time Algorithm for Projective Clustering}},
  year = {2012},
  eprint = {1204.6717},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1204.6717},
}
Figure