# Provable Deterministic Leverage Score Sampling

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Apr 2014.

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

- [CHEX: CHannel EXploration for CNN Model Compression](https://mlsanity.com/paper/2203.15794/) (2022)
- [Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions](https://mlsanity.com/paper/2104.01101/) (2021)
- [Deep Unsupervised Active Learning on Learnable Graphs](https://mlsanity.com/paper/2111.04286/) (2021)
- [Fair Column Subset Selection](https://mlsanity.com/paper/2306.04489/) (2023)
- [Generalized Leverage Scores: Geometric Interpretation and Applications](https://mlsanity.com/paper/2206.08054/) (2022)
- [Randomized Algorithms for Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/2402.08134/) (2024)
- [Estimating leverage scores via rank revealing methods and randomization](https://mlsanity.com/paper/2105.11004/) (2021)
- [Reconstructing Kernel-based Machine Learning Force Fields with Super-linear Convergence](https://mlsanity.com/paper/2212.12737/) (2022)
- [Gradient Coding with Iterative Block Leverage Score Sampling](https://mlsanity.com/paper/2308.03096/) (2023)
- [Linear Discriminant Analysis with the Randomized Kaczmarz Method](https://mlsanity.com/paper/2211.05749/) (2022)
- [On the Error-Propagation of Inexact Hotelling's Deflation for Principal Component Analysis](https://mlsanity.com/paper/2310.04283/) (2023)
- [Towards Deterministic Diverse Subset Sampling](https://mlsanity.com/paper/2105.13942/) (2021)
- [Unsupervised Active Learning via Natural Feature Progressive Framework](https://mlsanity.com/paper/2510.04939/) (2025)

## Abstract (arXiv)

We explain theoretically a curious empirical phenomenon: "Approximating a matrix by deterministically selecting a subset of its columns with the corresponding largest leverage scores results in a good low-rank matrix surrogate". To obtain provable guarantees, previous work requires randomized sampling of the columns with probabilities proportional to their leverage scores. In this work, we provide a novel theoretical analysis of deterministic leverage score sampling. We show that such deterministic sampling can be provably as accurate as its randomized counterparts, if the leverage scores follow a moderately steep power-law decay. We support this power-law assumption by providing empirical evidence that such decay laws are abundant in real-world data sets. We then demonstrate empirically the performance of deterministic leverage score sampling, which many times matches or outperforms the state-of-the-art techniques.