# Estimating leverage scores via rank revealing methods and randomization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 85 references that are in the map.
- First posted on arXiv 23 May 2021.

## Builds on (most cited first, 17 of 17)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [Faster Kernel Ridge Regression Using Sketching and Preconditioning](https://mlsanity.com/paper/1611.03220/) (2016)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [Toward a unified theory of sparse dimensionality reduction in Euclidean space](https://mlsanity.com/paper/1311.2542/) (2013)
- [Provable Deterministic Leverage Score Sampling](https://mlsanity.com/paper/1404.1530/) (2014)
- [Column subset selection is NP-complete](https://mlsanity.com/paper/1701.02764/) (2017)
- [Matrix Coherence and the Nystrom Method](https://mlsanity.com/paper/1408.2044/) (2014)
- [Single Pass Spectral Sparsification in Dynamic Streams](https://mlsanity.com/paper/1407.1289/) (2014)
- [Error Estimation for Randomized Least-Squares Algorithms via the Bootstrap](https://mlsanity.com/paper/1803.08021/) (2018)
- [Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness](https://mlsanity.com/paper/1704.04163/) (2017)
- [Tighter Low-rank Approximation via Sampling the Leveraged Element](https://mlsanity.com/paper/1410.3886/) (2014)
- [Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees](https://mlsanity.com/paper/1705.00985/) (2017)
- [How to Fake Multiply by a Gaussian Matrix](https://mlsanity.com/paper/1606.05732/) (2016)
- [Density Independent Algorithms for Sparsifying k-Step Random Walks](https://mlsanity.com/paper/1702.06110/) (2017)
- [An Empirical Evaluation of Sketched SVD and its Application to Leverage Score Ordering](https://mlsanity.com/paper/1812.07903/) (2018)

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

- [SALSA: Sequential Approximate Leverage-Score Algorithm with Application in Analyzing Big Time Series Data](https://mlsanity.com/paper/2401.00122/) (2023)
- [Stochastic diagonal estimation with adaptive parameter selection](https://mlsanity.com/paper/2410.11613/) (2024)

## Abstract (arXiv)

We study algorithms for estimating the statistical leverage scores of rectangular dense or sparse matrices of arbitrary rank. Our approach is based on combining rank revealing methods with compositions of dense and sparse randomized dimensionality reduction transforms. We first develop a set of fast novel algorithms for rank estimation, column subset selection and least squares preconditioning. We then describe the design and implementation of leverage score estimators based on these primitives. These estimators are also effective for rank deficient input, which is frequently the case in data analytics applications. We provide detailed complexity analyses for all algorithms as well as meaningful approximation bounds and comparisons with the state-of-the-art. We conduct extensive numerical experiments to evaluate our algorithms and to illustrate their properties and performance using synthetic and real world data sets.