Speaker
Description
We consider the column subset selection problem (CSSP), that is, the problem of selecting a submatrix $C$ made of $k$ columns of a matrix $A \in \mathbb{R}^{n \times n}$ such that $\|A - CC^\dagger A\|$ is small, where $\dagger$ denotes the pseudoinverse.
We present a randomized algorithm for CSSP, based on an adaptive leverage score sampling strategy, which guarantees, in expectation, an approximation error that matches the optimal existence result in the Frobenius norm. Our method, called Adaptive Randomized Pivoting (ARP), can be seen as a randomized counterpart to a recent deterministic approach proposed by Osinsky. Although the same theoretical guarantee can be achieved with other methods, such as volume sampling, ARP is simpler and less expensive.
We will highlight how this simple yet powerful strategy can be adapted to a range of other tasks related to low-rank approximation, including the Discrete Empirical Interpolation Method, cross/skeleton approximation, and the Nyström approximation of positive semidefinite matrices. We will also briefly describe a new deterministic variant for Nyström approximation that inherits strong error guarantees.
