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

Farhad Pourkamali-Anaraki, Stephen Becker
10/31/2015
stat.MLcs.LG

Official code: stephenbeckr/SparsifiedKMeans (62 stars, MIT, last commit 2020-04-13).

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.

View on arXivView PDF

Code Implementations(1)

stephenbeckr/SparsifiedKMeansOfficial100%
MIT

KMeans for big data using preconditioning and sparsification, Matlab implementation. Aka k-means

6246C, MATLABAug 4, 20156 years agoMIT
k-meanskmeansout-of-core

Similar Papers

Compressed and distributed least-squares regression: convergence rates with applications to Federated Learning

79% match2023

Compressed Sensing using Generative Models

79% match1 repo2262017

Compressing Model with Few Class-Imbalance Samples: An Out-of-Distribution Expedition

79% match2025

Collaborative Compressors in Distributed Mean Estimation with Limited Communication Budget

79% match2026

Gradient Coding with Iterative Block Leverage Score Sampling

78% match2023

SLiM: One-shot Quantization and Sparsity with Low-rank Approximation for LLM Weight Compression

78% match1 repo372024

Cite this paper

@article{pourkamalianaraki2015preconditioned,
  title  = {Preconditioned Data Sparsification for Big Data with Applications to PCA and K-means},
  author = {Farhad Pourkamali-Anaraki and Stephen Becker},
  year   = {2015},
  eprint = {1511.00152},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/1511.00152}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/1511.00152.svg)](https://codeofpaper.com/paper/1511.00152)

Discussion