A new upper bound for sampling numbers

DOI10.1007/S10208-021-09504-0arXiv2010.00327MaRDI QIDQ6350306FDOQ6350306

Authors: Martin Schäfer, Tino Ullrich 

Publication date: 30 September 2020

Abstract: We provide a new upper bound for sampling numbers $(g_n{)}_{ninmathbbN}$ 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 ${\displaystyle }$ g^2_n leq frac{Clog(n)}{n}sumlimits_{kgeq lfloor cn floor} sigma_k^2quad,quad ngeq 2,, ${\displaystyle }$ where $(sigm{a}_k{)}_{kinmathbbN}$ is the sequence of singular numbers (approximation numbers) of the Hilbert-Schmidt embedding $extId:H(K)o{L}_2(D,varrh{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_{extmix}^s(mathbb{T}^d)$ in $L_2(mathbb{T}^d)$ with $s>1/2$. We obtain the asymptotic bound ${\displaystyle }$ g_n leq C_{s,d}n^{-s}log(n)^{(d-1)s+1/2},, ${\displaystyle }$ which improves on very recent results by shortening the gap between upper and lower bound to $sqrtlog(n)$.

Mathematics Subject Classification ID

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

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)