A sharp upper bound for sampling numbers in $L_2$ - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

A sharp upper bound for sampling numbers in $L_2$

(1) , (2) , (2)
Matthieu Dolbeault
  • Function : Author
  • PersonId : 1098233
David Krieg
  • Function : Author
  • PersonId : 1197487
Mario Ullrich
  • Function : Author
  • PersonId : 1197488


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 \leq \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.
Fichier principal
Vignette du fichier
optimal_sampling_final.pdf (497.44 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03881514 , version 1 (01-12-2022)
hal-03881514 , version 2 (08-12-2022)


  • HAL Id : hal-03881514 , version 2


Matthieu Dolbeault, David Krieg, Mario Ullrich. A sharp upper bound for sampling numbers in $L_2$. 2022. ⟨hal-03881514v2⟩
0 View
0 Download


Gmail Facebook Twitter LinkedIn More