{"id":"arxiv/2610.08576","url":"https://arxiv.org/abs/2610.08576","tags":["math.NA"],"score":0,"title":"Subset selection for matrices by volume sampling","domain":"math.NA","source":"arxiv","authors":["Ivan Kozyrev","Alexander Osinsky"],"reviews":0,"subject":"math.NA","summary":"We address the Subset selection problem for matrices, where the goal is to select a subset $\\mathcal{S}$ of $k$ column indices from a \\enquote{short-and-fat} matrix $X \\in \\mathbb{R}^{m \\times n}$, such that the sampled submatrix $X_{\\mathcal{S}}$ has $\\|X_{\\mathcal{S}}^†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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-06","reactions":{}}