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

arXiv: https://arxiv.org/abs/1511.00152 · HTML: https://mlsanity.com/paper/1511.00152/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Oct 2015.

## Built on by (most cited first, 3 of 3)

- [An Empirical Evaluation of the t-SNE Algorithm for Data Visualization in Structural Engineering](https://mlsanity.com/paper/2109.08795/) (2021)
- [An Improved Frequent Directions Algorithm for Low-Rank Approximation via Block Krylov Iteration](https://mlsanity.com/paper/2109.11703/) (2021)
- [D-CBRS: Accounting For Intra-Class Diversity in Continual Learning](https://mlsanity.com/paper/2207.05897/) (2022)

## Abstract (arXiv)

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.