Clustering high-dimensional data is notoriously computationally expensive because distance calculations scale linearly with the number of dimensions. While the Johnson-Lindenstrauss (JL) Lemma offers a standard workaround—projecting $n$ points into $O(\log n)$ dimensions while preserving pairwise distances—researchers have often wondered if we can compress data even further.
For problems with a fixed number of clusters ($k$), like $k$-means, it is possible to project into $O(\log k)$ dimensions. However, many real-world problems do not have a predetermined $k$. This paper investigates two such variable-cluster problems:
- Facility Location (FL): Balancing the cost of opening "facilities" (cluster centers) against the distance points must travel to reach them.
- Single-Linkage Clustering (MST): Building a hierarchy of clusters by connecting the closest points, mathematically equivalent to finding a Minimum Spanning Tree.
The authors demonstrate that for these problems, randomly projecting data into a lower dimension proportional to its intrinsic doubling dimension ($d_X$) is sufficient to preserve solution quality. This approach yields massive speedups on high-dimensional datasets with minimal loss in accuracy.
Leveraging Intrinsic Geometry
The core theoretical contribution of the paper links the target projection dimension not to the raw number of points ($n$), but to the dataset's doubling dimension ($d_X$).
The doubling dimension measures a dataset's "intrinsic" dimensionality. If a set of points covered by a ball of radius $r$ can always be covered by a small number of balls of radius $r/2$, the dataset has a low doubling dimension. By proving that the "true" complexity of clustering depends on this intrinsic shape rather than the raw point count, the authors justify much more aggressive compression than the JL lemma suggests.
To prove this works, the authors rely on two main technical arguments:
- Local Optimality for FL: They prove that a solution that is "locally optimal" in the projected space is still a good approximation when evaluated in the original high-dimensional space.
- Chaining Arguments for MST: They utilize sophisticated "chaining" techniques to ensure that edges in the Minimum Spanning Tree don't shrink or expand excessively after projection.
Key Findings and Experimental Results
The authors validated their theory using both real-world datasets (Faces, MNIST) and synthetic datasets designed to test sensitivity to intrinsic dimensionality.
Massive Speedups: By projecting data to just $d=20$ dimensions, the authors achieved an 80x speedup for MST computation on the Faces dataset (4096 original dimensions) and a 30x speedup on the MNIST dataset (784 original dimensions).
High Accuracy: Despite the aggressive dimensionality reduction, the "Pullback" cost—the cost of the low-dimensional solution when measured back in the high-dimensional space—quickly approaches the optimal cost as the projected dimension increases.
Sensitivity to Doubling Dimension: The experiments perfectly confirmed the paper's central theory regarding intrinsic geometry. When comparing synthetic datasets, the dataset with a low doubling dimension reached a high-quality MST approximation much faster (at lower projected dimensions) than the dataset with a high doubling dimension.
Limitations and Future Directions
While the results are highly promising, the paper notes a few limitations:
- Uniform Costs: The primary theoretical results for Facility Location assume uniform opening costs for all facilities. While generalizations are possible, the core proofs focus on this simpler case.
- Worst-case Scenarios: If a dataset is truly high-dimensional with no underlying structure (e.g., random points uniformly distributed on a sphere), the doubling dimension $d_X$ becomes $O(\log n)$, and the benefits over standard JL reduction disappear.
Ultimately, this paper proves that standard clustering algorithms work exceptionally well on aggressively projected data. Rather than proposing a new end-to-end algorithm, it provides a rigorous theoretical justification for using random projections as a highly effective pre-processing step for variable-cluster problems.
Summary updated