Approximation and Streaming Algorithms for Projective Clustering via Random Projections

Michael Kerber, Sharath Raghvendra

Abstract

Let $P$ be a set of $n$ points in $\mathbb{R}^d$. In the projective clustering problem, given $k, q$ and norm $\rho \in [1,\infty]$, we seek a set $\mathcal{F}$ of $k$ $q$-dimensional flats that minimizes the distance objective $(\sum_{p\in P}d(p, \mathcal{F})^\rho)^{1/\rho}$. This paper demonstrates that the orthogonal projection of $P$ onto a randomly chosen flat of dimension $O(((q+1)^2\log(1/\epsilon)/\epsilon^3) \log n)$ provides an $\epsilon$-approximation for the projective clustering objective. This result, which combines geometric coresets with subspace embeddings based on the Johnson-Lindenstrauss Lemma, allows for dimensionality reduction that is independent of the number of clusters $k$. These findings lead to new streaming algorithms that significantly reduce space requirements compared to traditional methods.

Introduction

Clustering is a fundamental task in data analysis, typically involving the partitioning of data points into groups represented by central points (0-dimensional flats). Projective clustering generalizes this by seeking $k$ $q$-dimensional flats (lines, planes, etc.) that best approximate a dataset $P \subset \mathbb{R}^d$. This framework encompasses well-known problems such as $k$-means, $k$-median, and $k$-center as special cases where $q=0$.

As datasets grow in both size ($n$) and dimensionality ($d$), the computational cost of these problems increases exponentially—a phenomenon often called the "curse of dimensionality." In streaming environments where memory is a scarce resource, existing algorithms often require space proportional to $O(kd)$. When both $k$ and $d$ are large, this becomes a significant bottleneck. This paper addresses whether we can project high-dimensional data into a lower-dimensional space while preserving the clustering structure, specifically in a way that is independent of the number of clusters $k$.

The Projective Clustering Framework

The objective of projective clustering is to find a set $\mathcal{F}$ of $k$ $q$-dimensional flats to minimize the distance function $f_k^q(P,\rho)$. The challenge lies in the fact that as $d$ increases, the search space for these flats expands. Traditional dimensionality reduction, such as Principal Component Analysis (PCA), often results in a target dimension that depends heavily on $k$.

Kerber and Raghvendra propose a different approach using random projections. They prove that a random projection can reduce the dimension to a level logarithmic in $n$ and polynomial in $q$ and $1/\epsilon$, effectively decoupling the target dimension from the number of clusters $k$.

Bridging Coresets and Random Projections

The core theoretical innovation of this work is the synthesis of Geometric Coresets and the Johnson-Lindenstrauss (JL) Lemma.

  1. The JL Lemma: Traditionally, the JL Lemma states that a random projection into $O(\log n / \epsilon^2)$ dimensions preserves pairwise distances between points. The authors extend this to show that random projections also preserve distances between points and affine subspaces (flats).
  2. The Coreset Connection: A coreset is a small subset of data that approximates the shape or clustering objective of the entire set. The authors employ an "existence trick": they demonstrate that if a problem admits a small coreset of size $C$, then a random projection to a space of dimension roughly $O(C \log n)$ will preserve the clustering objective for the entire dataset.

Crucially, the algorithm does not need to explicitly compute the coreset. The mathematical guarantee that a small coreset exists is sufficient to ensure that a simple random projection will preserve the distances to the optimal flats for the whole set.

Key Results and Algorithmic Impact

Dimensionality Reduction

The paper proves that for any $0 < \epsilon < 1$, an orthogonal projection of $P$ to a subspace of dimension $O(\frac{(q+1)^2}{\epsilon^3} \log n \log \frac{q+1}{\epsilon})$ $\epsilon$-approximates the projective clustering objective for every $k$ and $\rho$ simultaneously. This means a single projection works regardless of whether one is performing $k$-means, $k$-median, or $k$-center clustering, and regardless of how many clusters are eventually sought.

Streaming Efficiency

By applying this dimensionality reduction to streaming data, the authors achieve a space complexity of: $$O\left((n+d) \frac{(q+1)^2 \log ((q+1)/\epsilon)}{\epsilon^3} \log n\right)$$ In scenarios where $n$ and $d$ are of similar magnitude and $k$ is large, this is a substantial improvement over the standard $\Omega(kd)$ space requirement. The projection can be applied to points as they arrive, allowing the system to maintain a low-dimensional representation of the stream.

Topological Preservation

Beyond clustering, the authors show that these random projections preserve the radius of Minimum Enclosing Balls (MEB). This has implications for computational topology, as it suggests that the topological features of high-dimensional data, such as those found in Cech complexes, are preserved during the reduction process.

Conclusion and Future Directions

This research provides a powerful tool for handling high-dimensional projective clustering by proving that the required dimension for an accurate approximation is independent of the number of clusters. By leveraging the existence of coresets to validate random projections, the authors bridge two previously distinct areas of computational geometry.

Future work may focus on refining the dependence on $\epsilon$. Currently, the $1/\epsilon^3$ dependence may lead to high dimensions for very high-precision requirements. Additionally, while the theoretical bounds are promising, empirical studies are needed to evaluate the performance of the "lifting" step—mapping the low-dimensional solution back to the original space—on real-world, noisy datasets.

Summary updated

Abstract

Let $P$ be a set of $n$ points in $\mathbb{R}^d$. In the projective clustering problem, given $k, q$ and norm $\rho \in [1,\infty]$, we have to compute a set $\mathcal{F}$ of $k$ $q$-dimensional flats such that $(\sum_{p\in P}d(p, \mathcal{F})^\rho)^{1/\rho}$ is minimized; here $d(p, \mathcal{F})$ represents the (Euclidean) distance of $p$ to the closest flat in $\mathcal{F}$. We let $f_k^q(P,\rho)$ denote the minimal value and interpret $f_k^q(P,\infty)$ to be $\max_{r\in P}d(r, \mathcal{F})$. When $\rho=1,2$ and $\infty$ and $q=0$, the problem corresponds to the $k$-median, $k$-mean and the $k$-center clustering problems respectively. For every $0 < \epsilon < 1$, $S\subset P$ and $\rho \ge 1$, we show that the orthogonal projection of $P$ onto a randomly chosen flat of dimension $O(((q+1)^2\log(1/\epsilon)/\epsilon^3) \log n)$ will $\epsilon$-approximate $f_1^q(S,\rho)$. This result combines the concepts of geometric coresets and subspace embeddings based on the Johnson-Lindenstrauss Lemma. As a consequence, an orthogonal projection of $P$ to an $O(((q+1)^2 \log ((q+1)/\epsilon)/\epsilon^3) \log n)$ dimensional randomly chosen subspace $\epsilon$-approximates projective clusterings for every $k$ and $\rho$ simultaneously. Note that the dimension of this subspace is independent of the number of clusters~$k$. Using this dimension reduction result, we obtain new approximation and streaming algorithms for projective clustering problems. For example, given a stream of $n$ points, we show how to compute an $\epsilon$-approximate projective clustering for every $k$ and $\rho$ simultaneously using only $O((n+d)((q+1)^2\log ((q+1)/\epsilon))/\epsilon^3 \log n)$ space. Compared to standard streaming algorithms with $\Omega(kd)$ space requirement, our approach is a significant improvement when the number of input points and their dimensions are of the same order of magnitude.
BibTeX
@inproceedings{kerber2015approximation,
  author = {Michael Kerber and Sharath Raghvendra},
  title = {{Approximation and Streaming Algorithms for Projective Clustering via Random Projections}},
  booktitle = {CCCG},
  year = {2015},
  url = {https://openreview.net/forum?id=HOJIf5fbG5i},
}
Figure