Subset selection for matrices by volume sampling
Abstract
We address the Subset selection problem for matrices, where the goal is to select a subset 𝒮 of k column indices from a \enquote{short-and-fat} matrix X ∈ ℝm × n, such that the sampled submatrix X𝒮 has |X𝒮†X|F as small as possible. Our approach is centered on volume sampling, which attains the tightest known bound on this objective in expectation. As our primary contribution, we propose a new deterministic algorithm, Forward derandomized volume sampling (FDVS), which provably attains this bound and has asymptotic complexity O(nkm). In contrast, the complexity of all previously known algorithms with this guarantee scales at least quadratically in n when k ≪ n, making FDVS particularly attractive for very wide matrices. In addition, we systematically structure the landscape of volume sampling methods: we propose a simple O(nm2) algorithm for exact forward volume sampling, show that a known deterministic method is in fact a derandomization of Reverse iterative volume sampling, and derive a modification of the latter that avoids repeated SVD downdating, along with a fast greedy forward variant. The algorithms are verified and compared in numerical experiments involving optimal experimental design, sensor placement, and DLRA-DEIM.
Related
- Incremental Column Subset Selection via Conditional Determinantal Point Processes
- Sequential Optimization of Multiple Stopping Times with Spatial Subset Selection
- Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids
- Smallest Singular Value Estimates for Nonuniform Fourier Matrices via Periodic Nonuniform Sampling
- Frequency sorting in graded dispersive resonator arrays via volume-interaction matrices
BibTeX
@misc{kozyrev2026subset,
title = {{Subset selection for matrices by volume sampling}},
author = {Ivan Kozyrev and Alexander Osinsky},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08576},
eprint = {2610.08576},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08576},
}
RIS
TY - UNPB
TI - Subset selection for matrices by volume sampling
AU - Ivan Kozyrev
AU - Alexander Osinsky
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.08576
UR - https://arxiv.org/abs/2610.08576
AB - We address the Subset selection problem for matrices, where the goal is to select a subset 𝒮 of k column indices from a \enquote{short-and-fat} matrix X ∈ ℝ^m × n, such that the sampled submatrix X_𝒮 has |X_𝒮^†X|_F as small as possible. Our approach is centered on volume sampling, which attains the tightest known bound on this objective in expectation. As our primary contribution, we propose a new deterministic algorithm, Forward derandomized volume sampling (FDVS), which provably attains this bound and has asymptotic complexity O(nkm). In contrast, the complexity of all previously known algorithms with this guarantee scales at least quadratically in n when k ≪ n, making FDVS particularly attractive for very wide matrices. In addition, we systematically structure the landscape of volume sampling methods: we propose a simple O(nm^2) algorithm for exact forward volume sampling, show that a known deterministic method is in fact a derandomization of Reverse iterative volume sampling, and derive a modification of the latter that avoids repeated SVD downdating, along with a fast greedy forward variant. The algorithms are verified and compared in numerical experiments involving optimal experimental design, sensor placement, and DLRA-DEIM.
ER -