Incremental Column Subset Selection via Conditional Determinantal Point Processes

DOI10.48550/arXiv.2609.20556MaRDI QIDQ7353393zbMATH OpenarXivFDO

Publication date 17 September 2026

Tldr We introduce conditional DPPs for incremental column subset selection from existing algorithms, combine with adaptive randomized pivoting (ARP) to develop a multi-stage ARP algorithm (MSARP), and establish theoretical guarantees on the expected Frobenius-norm approximation errors, achieving accuracy comparable to standard ARP while enabling incremental selection.

Full work available at URL https://doi.org/10.48550/arXiv.2609.20556

arXiv classification

math.NA

Cites work

Adaptive randomized pivoting for column subset selection, DEIM, and low-rank approximation
Close to optimal column approximation using a single SVD
Column and row subset selection using nuclear scores: algorithms and theory for Nyström approximation, CUR decomposition, and graph Laplacian reduction
Computing Strong Rank-Revealing Factorizations for Matrices with Orthonormal Rows
Determinantal point processes for machine learning
Determinantal processes and independence
Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
Matrix approximation and projective clustering via volume sampling
Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
Optimal Design of Experiments
Randomized algorithms for low-rank matrix factorizations: sharp performance bounds
Randomly pivoted Cholesky: practical approximation of a kernel matrix with few entry evaluations

This page was built for publication: Incremental Column Subset Selection via Conditional Determinantal Point Processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7353393)