Greedy sampling designs via reduced basis methods: optimal recovery in the uniform norm
Abstract
We study optimal sampling recovery in reproducing kernel Hilbert spaces (RKHS) in the uniform norm. For every RKHS with bounded kernel, we establish new comparisons between linear sampling widths and Gelfand widths that overcome the known square-root gap, without requiring a measure or a Christoffel-type condition. Our bounds rely on nested sampling designs obtained by kernel interpolation at (weak) P-greedy points. Under additional (polynomial) decay assumptions the decay rate of the Gelfand widths directly transfers to the sampling widths. With either a logarithmic oversampling or passing to the square root of the Gelfand widths we obtain a direct comparison (requiring no decay assumption) between them. This is particularly effective for super-polynomial decay, such as in Paley-Wiener spaces. Our results follow from representations of both widths in terms of kernel translates and yield, in the opposite direction, a new existence result for a sharp reduced basis selection. Numerical experiments for Legendre, mixed-Sobolev, and Paley-Wiener kernels illustrate our findings.
Related
- Optimal Two‐Phase Sampling Designs for Generalized Raking Estimators With Multiple Parameters of Interest
- A sharp bound for sampling widths in the uniform norm: kernel D-optimal designs and oversampling
- Quasi-uniform designs from random candidates: optimal candidate complexity and farthest-point sampling
- On Optimal Quantum LRCs From the Hermitian Construction and t -Designs
- A Tutorial on Safe Anytime-Valid Inference: Practical Maximally Flexible Sampling Designs for Experiments Based on e-Values
BibTeX
@misc{neumayer2026greedy,
title = {{Greedy sampling designs via reduced basis methods: optimal recovery in the uniform norm}},
author = {Sebastian Neumayer and Kateryna Pozharska and Tino Ullrich},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.01578},
eprint = {2609.01578},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.01578},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Greedy sampling designs via reduced basis methods: optimal recovery in the uniform norm
AU - Sebastian Neumayer
AU - Kateryna Pozharska
AU - Tino Ullrich
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.01578
UR - https://arxiv.org/abs/2609.01578
AB - We study optimal sampling recovery in reproducing kernel Hilbert spaces (RKHS) in the uniform norm. For every RKHS with bounded kernel, we establish new comparisons between linear sampling widths and Gelfand widths that overcome the known square-root gap, without requiring a measure or a Christoffel-type condition. Our bounds rely on nested sampling designs obtained by kernel interpolation at (weak) P-greedy points. Under additional (polynomial) decay assumptions the decay rate of the Gelfand widths directly transfers to the sampling widths. With either a logarithmic oversampling or passing to the square root of the Gelfand widths we obtain a direct comparison (requiring no decay assumption) between them. This is particularly effective for super-polynomial decay, such as in Paley-Wiener spaces. Our results follow from representations of both widths in terms of kernel translates and yield, in the opposite direction, a new existence result for a sharp reduced basis selection. Numerical experiments for Legendre, mixed-Sobolev, and Paley-Wiener kernels illustrate our findings.
ER -