# Adaptive randomized pivoting and volume sampling

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 40 references that are in the map.
- First posted on arXiv 2 Oct 2025.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Determinantal Point Processes in Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2005.03185/) (2020)
- [Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations](https://mlsanity.com/paper/2207.06503/) (2022)
- [Unbiased estimates for linear regression via volume sampling](https://mlsanity.com/paper/1705.06908/) (2017)
- [Reverse iterative volume sampling for linear regression](https://mlsanity.com/paper/1806.01969/) (2018)
- [Minimax experimental design: Bridging the gap between statistical and worst-case approaches to least squares regression](https://mlsanity.com/paper/1902.00995/) (2019)
- [A Faster Sampler for Discrete Determinantal Point Processes](https://mlsanity.com/paper/2210.17358/) (2022)
- [Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Cholesky](https://mlsanity.com/paper/2410.03969/) (2024)
- [Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors](https://mlsanity.com/paper/2508.14234/) (2025)
- [Faster Linear Algebra Algorithms with Structured Random Matrices](https://mlsanity.com/paper/2508.21189/) (2025)

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

- [Contact Geometry and Covariance Deficits in Volume-Sampled Least Squares](https://mlsanity.com/paper/2608.26877/) (2026)

## Abstract (arXiv)

Adaptive randomized pivoting (ARP) is a recently proposed and highly effective algorithm for column subset selection. This paper reinterprets the ARP algorithm by drawing connections to the volume sampling distribution and active learning algorithms for linear regression. As consequences, this paper presents new analysis for the ARP algorithm and faster implementations using rejection sampling.