.png){kind=icon}
.png){kind=icon}
Return
ADAPTIVE RANDOMIZED PIVOTING FOR COLUMN SUBSET SELECTION, DEIM, AND LOW-RANK APPROXIMATION
.png){kind=icon}
PRE
AI
DOI：10.1137/24M1719189.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We derive a new adaptive leverage score sampling strategy for solving the column subset selection problem (CSSP). The resulting algorithm, called adaptive randomized pivoting, can be viewed as a randomization of Osinsky's recently proposed deterministic algorithm for CSSP. It guarantees, in expectation, an approximation error that matches the optimal existence result in the Frobenius norm. Although the same guarantee can be achieved with volume sampling, our sampling strategy is much simpler and less expensive. To show the versatility of adaptive randomized pivoting, we apply it to select indices in the discrete empirical interpolation method, in cross/skeleton approximation of general matrices, and in the Nystro\m approximation of symmetric positive semidefinite matrices. In all these cases, the resulting randomized algorithms are new and they enjoy bounds on the expected error that match---or improve---the best known deterministic results. A derandomization of the algorithm for the Nystro\m approximation results in a new deterministic algorithm with a rather favorable error bound.
Keywords:
randomized algorithms
column subset selection
DEIM
cross approximation
Nystro
m approximation
Journal
S
IF:
1.7
Papers:
19
Citations:
0