Subset selection for matrices by volume sampling

DOI10.48550/arXiv.2610.08576MaRDI QIDQ7367898arXivFDO

Authors Ivan Kozyrev, Alexander Osinsky

Publication date 6 October 2026

Published in arXiv

Tldr We propose a deterministic algorithm called Forward derandomized volume sampling (FDVS) to select a subset of columns from a matrix, such that the sampled submatrix has minimal Frobenius norm under its pseudoinverse. Our method provably attains the tightest known bound on this objective in expectation and has asymptotic complexity O(nkm).

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

arXiv classification

math.NA

Cites work

• A collocation method for nonlinear tensor differential equations on low-rank manifolds
• A new selection operator for the discrete empirical interpolation method -- improved a priori error bound and extensions
• A note on sparse least-squares regression
• A note on subset selection for matrices
• A projector-splitting integrator for dynamical low-rank approximation
• A Stable and Efficient Algorithm for the Rank-One Modification of the Symmetric Eigenproblem
• Adaptive randomized pivoting for column subset selection, DEIM, and low-rank approximation
• Algorithm 853
• An accelerated divide-and-conquer algorithm for the bidiagonal SVD problem
• An unconventional robust integrator for dynamical low-rank approximation
• Close to optimal column approximation using a single SVD
• Data-Driven Sparse Sensor Placement for Reconstruction: Demonstrating the Benefits of Exploiting Known Patterns
• Discrete Signal Processing on Graphs: Sampling Theory
• Downdating the Singular Value Decomposition
• Dynamical Low‐Rank Approximation
• Efficient volume sampling for row/column subset selection
• Faster subset selection for matrices and applications
• How to find a good submatrix
• Interpolatory Dynamical Low-Rank Approximation: Theoretical Foundations and Algorithms
• Low-rank approximation in the Frobenius norm by column and row subset selection
• Lower bounds for column matrix approximations
• Near-optimal discrete optimization for experimental design: a regret minimization approach
• Nonlinear model reduction via discrete empirical interpolation
• Optimal CUR matrix decompositions
• Preconditioning linear least-squares problems by identifying a basis matrix
• Proportional volume sampling and approximation algorithms for \(A\)-optimal design
• Rank-deficient nonlinear least squares problems and subset selection
• Rectangular maximum volume and projective volume search algorithms
• Rectangular submatrices of maximum volume and their computation
• Reverse iterative volume sampling for linear regression
• Sampling algorithms for l₂ regression and applications
• Signals on Graphs: Uncertainty Principle and Sampling
• Some Applications of the Pseudoinverse of a Matrix
• Stability of discrete empirical interpolation and gappy proper orthogonal decomposition with randomized and deterministic sampling points
• Subset selection for matrices
• Subset selection for matrices by column exchange
• Subset selection for matrices in spectral norm
• Subset selection for matrices with fixed blocks
• Volume‐based subset selection

This page was built for publication: Subset selection for matrices by volume sampling

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