Preconditioned Data Sparsification for Big Data with Applications to PCA and K-means

Farhad Pourkamali-Anaraki, Stephen BeckerIEEE Trans. Information Theory 2015 · DOI · OpenReview

TL;DR

This paper introduces a novel, single-pass data sparsification technique that significantly speeds up computations for Principal Component Analysis (PCA) and K-means clustering on large datasets. By combining a randomized preconditioning step with element-wise random sampling, the method achieves substantial memory and computational savings while maintaining high accuracy, making it suitable for streaming and distributed environments.

What Problem Does This Paper Address?

Processing massive datasets for unsupervised learning tasks like PCA and K-means is computationally expensive and memory-intensive. Traditional algorithms often require multiple passes over the data or significant storage, making them impractical for streaming scenarios or distributed systems. Existing compression techniques can lose crucial information or require computationally demanding pre-processing steps, limiting their applicability. This paper aims to bridge this gap by developing an efficient, single-pass sparsification method that preserves essential data structure for accurate analysis.

Methods

The core of the proposed method involves two key steps:

  1. Randomized Preconditioning: The data is first transformed using a Randomized Orthonormal System (ROS). This step, based on the fast Johnson-Lindenstrauss transform, effectively smooths out large entries in the data, reducing the variance of subsequent estimators and improving the robustness of the sampling process. This preconditioning is achieved efficiently using Hadamard or DCT matrices and random sign flips, allowing for fast matrix-vector multiplications.
  2. Element-wise Random Sampling: After preconditioning, a small, fixed percentage of the data entries (m out of p) are randomly selected from each data sample. This results in a sparse representation of the data. The sampling is done without replacement and is applied independently to each preconditioned data sample.

These two steps are combined into a single pass, allowing for efficient processing of streaming data. The authors then provide theoretical guarantees for the accuracy of PCA (covariance matrix estimation) and K-means (cluster center estimation) using this sparsified data.

Datasets

The paper uses synthetic datasets for theoretical validation and numerical experiments. For real-world evaluation, it utilizes the MNIST dataset, a standard benchmark for image recognition and clustering tasks. The MNIST dataset is used in various sizes, including an "out-of-core" version with over 9.6 million samples, to demonstrate the scalability of the proposed method.

Key Insights and Ideas

  • Preconditioning is Crucial for Robustness: The randomized preconditioning step is not just for smoothing; it's essential for making the subsequent random sampling robust. Without it, simple random sampling can lead to high variance in estimators, especially when data has a few large outliers.
  • Single-Pass Efficiency: The combination of preconditioning and sampling in a single pass is a significant advantage for streaming and distributed data processing, eliminating the need to revisit data.
  • Theoretical Guarantees: The paper provides strong theoretical guarantees for both PCA and K-means, showing that the sparsified estimators are accurate with high probability, even with substantial compression.
  • K-means ML Interpretation: The sparsified K-means objective function retains a Maximum-Likelihood (ML) interpretation, providing a principled way to derive the algorithm.
  • Improved K-means Center Estimation: The sparsified K-means algorithm can provide accurate cluster center estimates in a single pass, unlike other feature-based methods that typically require multiple passes.

Key Results

  • PCA: The proposed method provides unbiased estimators for the sample mean and covariance matrix. Theoretical bounds show that the estimation error decreases exponentially with the number of samples and can be controlled by the compression factor. Numerical experiments demonstrate that the theoretical bounds are tight.
  • K-means: The sparsified K-means algorithm achieves high accuracy, comparable to standard K-means, with significant speedups. For example, on a synthetic dataset with 10⁵ samples, the sparsified version was approximately 67 times faster than an optimized standard K-means implementation. On the MNIST dataset, the 2-pass sparsified K-means achieved accuracy close to standard K-means even with a compression factor of 0.05.
  • Speedup: The method offers substantial computational speedups, particularly for large datasets. For instance, on a large MNIST dataset (n=6.10⁵), the sparsified K-means achieved a speedup of about 40x compared to a single iteration of standard K-means.
  • Variance Reduction: Preconditioning significantly reduces the variance of the estimators, leading to more reliable results, especially for PCA.

Limitations and Future Work

  • Parameter Tuning: While the method offers theoretical guarantees, the optimal choice of compression factor (m/p) might still require empirical tuning for specific applications.
  • Computational Cost of Preconditioning: Although efficient, the preconditioning step still adds a computational cost. The paper mentions that this can be further accelerated using GPUs.
  • Future Work: The authors suggest that the preconditioning and sampling technique can be broadly applied to other machine learning and signal processing algorithms, such as K-nearest neighbors, soft K-means, and expectation-maximization algorithms, to improve their efficiency and enable one-pass variants. They also highlight the potential for further optimization of the DCT implementation.

Summary updated

Abstract

We analyze a compression scheme for large data sets that randomly keeps a small percentage of the components of each data sample. The benefit is that the output is a sparse matrix and therefore subsequent processing, such as PCA or K-means, is significantly faster, especially in a distributed-data setting. Furthermore, the sampling is single-pass and applicable to streaming data. The sampling mechanism is a variant of previous methods proposed in the literature combined with a randomized preconditioning to smooth the data. We provide guarantees for PCA in terms of the covariance matrix, and guarantees for K-means in terms of the error in the center estimators at a given step. We present numerical evidence to show both that our bounds are nearly tight and that our algorithms provide a real benefit when applied to standard test data sets, as well as providing certain benefits over related sampling approaches.
BibTeX
@article{pourkamalianaraki2015preconditioned,
  author = {Farhad Pourkamali-Anaraki and Stephen Becker},
  title = {{Preconditioned Data Sparsification for Big Data with Applications to PCA and K-means}},
  journal = {IEEE Trans. Information Theory},
  year = {2015},
  doi = {10.1109/tit.2017.2672725},
}
Figure