A Single-Pass Algorithm for Efficiently Recovering Sparse Cluster Centers of High-dimensional Data

Jinfeng Yi, Lijun Zhang, Jun Wang, Rong Jin, Anil K. JainICML 2014 · OpenReview

This paper tackles a fundamental challenge in modern machine learning: how do we make sense of data when the number of features (dimensions) vastly outweighs the number of available examples?

TL;DR

The authors introduce HDSC (High-dimensional Clustering with Sparse Centers), a single-pass algorithm that can accurately cluster data even when the number of samples is much smaller than the data's dimensionality. By assuming cluster centers are "sparse" (mostly zeros) and using an iterative refinement strategy, they achieve a theoretical sample complexity of just $O(s \log d)$, making it both mathematically optimal and orders of magnitude faster than traditional k-means.

What Problem Does This Paper Address?

In fields like genomics or document analysis, we often deal with "high-dimensional, low-sample size" data. For instance, a dataset might have 100,000 features (word counts or gene expressions) but only 1,000 samples.

Standard statistical theory suggests that to recover the underlying structure of such data, you need a number of samples that grows linearly with the dimensionality ($d$). This is the "curse of dimensionality." However, in many real-world scenarios, the "true" signals are sparse—only a small subset of features ($s$) actually defines a cluster. The authors ask: Can we reliably cluster high-dimensional data when the number of samples is smaller than the dimensionality?

Methods

The authors propose an algorithm called HDSC. Its novelty lies in two main areas:

  1. Iterative Refinement with Exponential Growth: Instead of looking at all data at once or using standard mini-batches, HDSC divides the dataset into disjoint subsets that grow exponentially in size ($1, 2, 4, 8 \dots$). It uses the first small subset to get a rough estimate of the centers, then refines that estimate using the next (larger) subset, and so on. This ensures the algorithm stays "close" to the true centers as it processes more data.
  2. $\ell_1$ Regularization (Sparsity): During the center update step, the algorithm doesn't just take a simple average. It solves an optimization problem using an $\ell_1$ penalty (similar to the Lasso in regression). This forces the estimated cluster centers to be sparse, effectively filtering out the noise inherent in high-dimensional spaces.
  3. Single-Pass Efficiency: Unlike standard k-means, which iterates over the entire dataset multiple times until convergence, HDSC touches each data point exactly once.

Datasets

The researchers evaluated HDSC on four well-known high-dimensional benchmarks:

  • Yale Face Database: Grayscale images of faces.
  • Reuters-21578: A classic text categorization dataset.
  • TDT2: A large corpus of news articles.
  • TREC 05: A massive spam email dataset.
Dataset statistics showing instances, features, and clusters

Key Insights and Ideas

  • Optimal Sample Complexity: The most striking theoretical finding is that HDSC only requires $O(s \log d)$ samples to recover cluster centers. This mirrors the efficiency of supervised learning (like Compressed Sensing), proving that unsupervised clustering can be just as sample-efficient if the underlying structure is sparse.
  • The Power of the Single Pass: By increasing the subset size and decreasing the regularization strength ($\lambda$) over time, the algorithm "warms up." Early iterations focus on the most prominent features, while later iterations refine the details as confidence grows.
  • Initialization Matters: The theory requires the starting point to be "not too far" from the truth. The authors show that running a simple hierarchical clustering on a tiny, logarithmically-sized subset of the data provides a sufficiently good starting point.

Key Results

HDSC was compared against several baselines, including standard K-Means (KM), PCA-based K-Means (PCAKM), Latent Dirichlet Allocation (LDA), Localized Spectral Clustering (LSC), and Regularized K-Means (RegKM).

Clustering performance comparing NMI and CPU time across datasets
  • Speed: HDSC is incredibly fast. On the TDT2 dataset, HDSC finished in 0.9 seconds, while standard k-means took 52 seconds and PCA-based k-means took 221 seconds. On the massive TREC 05 dataset, HDSC took 7.8 seconds compared to 412 seconds for k-means.
  • Accuracy: Despite being faster and seeing the data only once, HDSC achieved higher Normalized Mutual Information (NMI)—a measure of clustering quality—than k-means, LDA, and spectral clustering on almost all tested datasets.
  • Robustness: The algorithm performed well even when the strict mathematical assumption of "Gaussian noise" was likely violated (as in the text datasets).

Limitations and Future Work

  • GMM Assumption: The core theoretical proofs rely on the data being generated from a Gaussian Mixture Model (GMM). While experiments show it works on other data types, the theoretical guarantees for non-Gaussian distributions remain an open question.
  • Sparsity Dependence: The algorithm's success depends on the cluster centers actually being sparse. If the "signal" is spread thinly across all dimensions, the $\ell_1$ regularization might discard useful information.
  • Streaming Data: While the algorithm is single-pass, the current version assumes you can store the subsets in memory during each iteration. The authors suggest that future work could adapt this into a true "streaming" framework where data is processed and discarded immediately.

Summary updated

Abstract

Learning a statistical model for high-dimensional data is an important topic in machine learning. Although this problem has been well studied in the supervised setting, little is known about its un...
BibTeX
@inproceedings{yi2014single,
  author = {Jinfeng Yi and Lijun Zhang and Jun Wang and Rong Jin and Anil K. Jain},
  title = {{A Single-Pass Algorithm for Efficiently Recovering Sparse Cluster Centers of High-dimensional Data}},
  booktitle = {International Conference on Machine Learning},
  year = {2014},
  url = {https://openreview.net/forum?id=HJ4Wgob_ZS},
}
Figure