A sharp upper bound for sampling numbers in L_2 - CNRS - Centre national de la recherche scientifique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2022

A sharp upper bound for sampling numbers in L_2

Résumé

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 ∈ N such that, if F is the unit ball of a separable reproducing kernel Hilbert space, then g_{cn}(F)^2 ≤ 1/n \sum_{k≥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 ⊂ 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
DKU22.pdf (397.91 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

  • HAL Id : hal-03881514 , version 1

Citer

Matthieu Dolbeault, David Krieg, Mario Ullrich. A sharp upper bound for sampling numbers in L_2. 2022. ⟨hal-03881514v1⟩
40 Consultations
57 Téléchargements

Partager

Gmail Facebook X LinkedIn More