A new upper bound for sampling numbers

DOI10.1007/S10208-021-09504-0MaRDI QIDQ6350306arXivFDO

Publication date 30 September 2020

Full work available at URL https://doi.org/10.1007/S10208-021-09504-0

Rate of convergence, degree of approximation (41A25) Multidimensional problems (41A63) Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25)

arXiv classification

cs.NA math.NA

Abstract: We provide a new upper bound for sampling numbers

(g_{n})_{n i n m a t h b b 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{Clog(n)}{n}sumlimits_{kgeq lfloor cn floor} sigma_k^2quad,quad ngeq 2,,

where

(s i g m a_{k})_{k i n m a t h b b N}

is the sequence of singular numbers (approximation numbers) of the Hilbert-Schmidt embedding

e x t I d : H (K) o L_{2} (D, v a r r h o_{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_{e x t m i x}^{s} (m a t h b b T^{d})

in

L_{2} (m a t h b b 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

s q r t l o g (n)

.

Cited in

(2)

This page was built for publication: A new upper bound for sampling numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6350306)