Adaptive randomized pivoting and volume sampling
Not on the map. Why?
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.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 10 of its 40 references that are in the map. First posted on arXiv 2 Oct 2025.
Builds on
10 of 40 references.
References · 10
- 2014Sketching as a Tool for Numerical Linear Algebracited by 285
- 2020Determinantal Point Processes in Randomized Numerical Linear Algebracited by 41
- 2022Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluationscited by 31
- 2017Unbiased estimates for linear regression via volume samplingcited by 13
- 2018Reverse iterative volume sampling for linear regressioncited by 9
- 2019Minimax experimental design: Bridging the gap between statistical and worst-case approaches to least squares regressioncited by 8
- 2022A Faster Sampler for Discrete Determinantal Point Processescited by 6
- 2024Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Choleskycited by 5
- 2025Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factorscited by 2
- 2025Faster Linear Algebra Algorithms with Structured Random Matricescited by 2
Built on by
Not cited yet.