A new upper bound for sampling numbers
Authors:
Preprint
Abstract
We provide a new upper bound for sampling numbers $(g_n)_{n\in \mathbb{N}}$ associated to the compact embedding of a separable reproducing kernel Hilbert space into the space of square integrable functions. There are universal constants $C,c>0$ (which are specified in the paper) such that $$ g^2_n \leq \frac{C\log(n)}{n}\sum\limits_{k\geq \lfloor cn \rfloor} \sigma_k^2\quad,\quad n\geq 2\,, $$ where $(\sigma_k)_{k\in \mathbb{N}}$ is the sequence of singular numbers (approximation numbers) of the Hilbert-Schmidt embedding $\text{Id}:H(K) \to L_2(D,\varrho_D)$. The algorithm which realizes the bound is a least squares algorithm based on a specific set of sampling nodes. These are constructed out of a random draw in combination with a down-sampling procedure coming from the celebrated proof of Weaver's conjecture, which was shown to be equivalent to the Kadison-Singer problem. Our result is non-constructive since we only show the existence of a linear sampling operator realizing the above bound. The general result can for instance be applied to the well-known situation of $H^s_{\text{mix}}(\mathbb{T}^d)$ in $L_2(\mathbb{T}^d)$ with $s>1/2$. We obtain the asymptotic bound $$ g_n \leq C_{s,d}n^{-s}\log(n)^{(d-1)s+1/2}\,, $$ which improves on very recent results by shortening the gap between upper and lower bound to $\sqrt{\log(n)}$.
Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- Worst-case Recovery Guarantees for Least Squares Approximation Using Random SamplesConstructive Approximation, 2021
- $L_2$-norm sampling discretization and recovery of functions from RKHS with finite traceSampling Theory, Signal Processing, and Data Analysis, 2021
- Function Values Are Enough for $L_2$-ApproximationFoundations of Computational Mathematics, 2020
- New Preasymptotic Estimates for Approximation of Periodic Sobolev Functions2020
- The Marcinkiewicz-Type Discretization TheoremsConstructive Approximation, 2018
- Approximation of Mixed Order Sobolev Functions on the d-Torus: Asymptotics, Preasymptotics, and d-DependenceConstructive Approximation, 2015
- Lower bounds for the integration error for multivariate functions with mixed smoothness and optimal Fibonacci cubature for functions on the squareMathematische Nachrichten, 2014
- User-Friendly Tail Bounds for Sums of Random MatricesFoundations of Computational Mathematics, 2011
- Reproducing Kernel Hilbert Spaces in Probability and Statistics2004
- On the Power of Standard Information for Weighted ApproximationFoundations of Computational Mathematics, 2001