A sharp upper bound for sampling numbers in $L_2$

Abstract

For a class $F$ of complex-valued functions on a set $D$, we denote by $g_n(F)$ its sampling numbers, i.e., the minimal worst-case error on $F$, measured in $L_2$, that can be achieved with a recovery algorithm based on $n$ function evaluations. We prove that there is a universal constant $c\in \mathbb{N}$ such that, if $F$ is the unit ball of a separable reproducing kernel Hilbert space, then \[ g_{cn}(F)^2 \,\le\, \frac{1}{n}\sum_{k\geq n} d_k(F)^2, \] where $d_k(F)$ are the Kolmogorov widths (or approximation numbers) of $F$ in $L_2$. We also obtain similar upper bounds for more general classes $F$, including all compact subsets of the space of continuous functions on a bounded domain $D\subset {\mathbb{R}}^d$, and show that these bounds are sharp by providing examples where the converse inequality holds up to a constant. The results rely on the solution to the Kadison-Singer problem, which we extend to the subsampling of a sum of infinite rank-one matrices.

References in corpus (5)

• Random sections of ellipsoids and the power of random information
• On the worst-case error of least squares algorithms for $L_2$-approximation with high probability
• Function values are enough for $L_2$-approximation: Part II
• Bounds on Kolmogorov widths and sampling recovery for classes with small mixed smoothness
• On the power of standard information for tractability for $L_2$-approximation in the randomized setting

Cited by in corpus (2)

• Exponential tractability of $L_2$-approximation with function values
• Random sampling of signals concentrated on compact set in localized reproducing kernel subspace of $L^p({\mathbb{R}}^n)$