Adaptive randomized pivoting and volume sampling
This work provides incremental improvements to column subset selection methods, primarily benefiting researchers in numerical linear algebra and machine learning.
The paper reinterprets the Adaptive Randomized Pivoting (ARP) algorithm by linking it to volume sampling and active learning for linear regression, resulting in new analysis and faster implementations using rejection sampling.
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.