Incremental Column Subset Selection via Conditional Determinantal Point Processes
Abstract
Column subset selection aims to seek a small set of representative columns that accurately approximates a given matrix. We study this problem from the perspective of determinantal point processes (DPPs) and their relation to several existing algorithms. To support incremental column selection, we introduce conditional DPPs, which can be applied to any column selection strategy. In particular, we combine it with adaptive randomized pivoting(ARP), and develop a multi-stage ARP (MSARP) algorithm. We establish theoretical guarantees on the expected Frobenius-norm approximation errors for these methods. In addition, we propose a fixed-precision variant of ARP that adaptively determines the number of selected columns. Numerical experiments on column subset selection and Nyström approximation show that MSARP achieves accuracy comparable to standard ARP while enabling incremental selection.
Related
- Decay of Correlations for Multiplicative Functionals of Determinantal Point Processes
- Large deviation principle for determinantal point processes on Stein manifolds
- Reducing the domain of discrete multi-time determinantal point processes
- Scalable Learning of Determinantal Point Processes with Kernel-Structured Interactions
- Product approximations for uniform spanning trees and determinantal processes
BibTeX
@misc{grigori2026incremental,
title = {{Incremental Column Subset Selection via Conditional Determinantal Point Processes}},
author = {Laura Grigori and Zhipeng Xue},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20556},
eprint = {2609.20556},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20556},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Incremental Column Subset Selection via Conditional Determinantal Point Processes
AU - Laura Grigori
AU - Zhipeng Xue
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.20556
UR - https://arxiv.org/abs/2609.20556
AB - Column subset selection aims to seek a small set of representative columns that accurately approximates a given matrix. We study this problem from the perspective of determinantal point processes (DPPs) and their relation to several existing algorithms. To support incremental column selection, we introduce conditional DPPs, which can be applied to any column selection strategy. In particular, we combine it with adaptive randomized pivoting(ARP), and develop a multi-stage ARP (MSARP) algorithm. We establish theoretical guarantees on the expected Frobenius-norm approximation errors for these methods. In addition, we propose a fixed-precision variant of ARP that adaptively determines the number of selected columns. Numerical experiments on column subset selection and Nyström approximation show that MSARP achieves accuracy comparable to standard ARP while enabling incremental selection.
ER -