A sharp upper bound for sampling numbers in L2

For a class F of complex-valued functions on a set D, we denote by gn(F) its sampling numbers, i.e., the minimal worst-case error on F, measured in L2, that can be achieved with a recovery algorithm based on n function evaluations. We prove that there is a universal constant c is an element of N such that, if F is the unit ball of a separable reproducing kernel Hilbert space, then gcn(F)2 <= 1 E n k >= n dk(F )2, where dk(F) are the Kolmogorov widths (or approximation numbers) of F in L2. 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 of Rd, 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. (c) 2022 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

Automated summary

This article discusses the sampling numbers of a class of complex-valued functions, which represent the minimal worst-case error that can be achieved with a recovery algorithm based on n function evaluations in the L2 norm. It is proven that for the unit ball of a separable reproducing kernel Hilbert space, there exists a constant c such that gcn(F)2 ≤ 1 E n k >= n dk(F)2, where dk(F) represents the Kolmogorov widths of F in L2. Similar upper bounds are also obtained for more general function classes, including compact subsets of the space of continuous functions on a bounded domain. Examples are provided to show the sharpness of these bounds by establishing the converse inequality. The results are built upon the solution to the Kadison-Singer problem, which is extended to the subsampling of a sum of infinite rank-one matrices.