# Near-Optimal Entrywise Sampling for Data Matrices

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Nov 2013.

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

- [Even Sparser Graph Transformers](https://mlsanity.com/paper/2411.16278/) (2024)
- [Importance Sparsification for Sinkhorn Algorithm](https://mlsanity.com/paper/2306.06581/) (2023)
- [On Recovering the Best Rank-r Approximation from Few Entries](https://mlsanity.com/paper/2111.06302/) (2021)
- [Graph Enabled Cross-Domain Knowledge Transfer](https://mlsanity.com/paper/2304.03452/) (2023)
- [Neural Network Pruning as Spectrum Preserving Process](https://mlsanity.com/paper/2307.08982/) (2023)

## Abstract (arXiv)

We consider the problem of selecting non-zero entries of a matrix A in order to produce a sparse sketch of it, B, that minimizes |A-B|2. For large m × n matrices, such that n gg m (for example, representing n observations over m attributes) we give sampling distributions that exhibit four important properties. First, they have closed forms computable from minimal information regarding A. Second, they allow sketching of matrices whose non-zeros are presented to the algorithm in arbitrary order as a stream, with O(1) computation per non-zero. Third, the resulting sketch matrices are not only sparse, but their non-zero entries are highly compressible. Lastly, and most importantly, under mild assumptions, our distributions are provably competitive with the optimal offline distribution. Note that the probabilities in the optimal offline distribution may be complex functions of all the entries in the matrix. Therefore, regardless of computational complexity, the optimal distribution might be impossible to compute in the streaming model.