PreprintCC BY 4.0arXiv
A sharp bound for sampling widths in the uniform norm: kernel D-optimal designs and oversampling
Abstract
For every reproducing kernel Hilbert space ℋK with bounded kernel K, we prove that the linear sampling widths gmlin and Gelfand widths cn in the uniform norm satisfy gmlin(BℋK)∞ ≤ (m+1)/(m−n+1) cn(BℋK)∞ , m≥ n. In a certain sense, the leading factor (m+1)/(m−n+1) on the right-hand side is sharp. We transfer the problem into the selection of a maximal volume subset of kernel translates (kernel D-optimal design). Apart from basic linear algebra, our proof employs low rank approximation techniques and a version of the Eckart-Young-Mirsky theorem. The same argument gives corresponding bounds for the selection of a reduced basis in Hilbert spaces.
Related
- Greedy sampling designs via reduced basis methods: optimal recovery in the uniform norm
- Quasi-uniform designs from random candidates: optimal candidate complexity and farthest-point sampling
- Optimal Two‐Phase Sampling Designs for Generalized Raking Estimators With Multiple Parameters of Interest
- Nearly optimal Kolmogorov widths under holomorphic mappings
- Exact construction of quasi-uniform designs over polytopal domains
BibTeX
@misc{neumayer2026sharp,
title = {{A sharp bound for sampling widths in the uniform norm: kernel $D$-optimal designs and oversampling}},
author = {Sebastian Neumayer and Tino Ullrich},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15556},
eprint = {2609.15556},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15556},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A sharp bound for sampling widths in the uniform norm: kernel D-optimal designs and oversampling
AU - Sebastian Neumayer
AU - Tino Ullrich
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.15556
UR - https://arxiv.org/abs/2609.15556
AB - For every reproducing kernel Hilbert space ℋ_K with bounded kernel K, we prove that the linear sampling widths g_m^lin and Gelfand widths c_n in the uniform norm satisfy g_m^lin(B_ℋ_K)_∞ ≤ (m+1)/(m−n+1) c_n(B_ℋ_K)_∞ , m≥ n. In a certain sense, the leading factor (m+1)/(m−n+1) on the right-hand side is sharp. We transfer the problem into the selection of a maximal volume subset of kernel translates (kernel D-optimal design). Apart from basic linear algebra, our proof employs low rank approximation techniques and a version of the Eckart-Young-Mirsky theorem. The same argument gives corresponding bounds for the selection of a reduced basis in Hilbert spaces.
ER -