A New Upper Bound for Sampling Numbers
Authors:
Top Cited Papers
Open Access
- 26 April 2021
- journal article
- research article
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 22 (2) , 445-468
Abstract
We provide a new upper bound for sampling numbers $$(g_n)_{n\in \mathbb {N}}$$ associated with 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 $$\begin{aligned} g^2_n \le \frac{C\log (n)}{n}\sum \limits _{k\ge \lfloor cn \rfloor } \sigma _k^2,\quad n\ge 2, \end{aligned}$$ where $$(\sigma _k)_{k\in \mathbb {N}}$$ is the sequence of singular numbers (approximation numbers) of the Hilbert–Schmidt embedding $$\mathrm {Id}:H(K) \rightarrow L_2(D,\varrho _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^s_{\text {mix}}(\mathbb {T}^d)$$ in $$L_2(\mathbb {T}^d)$$ with $$s>1/2$$ . We obtain the asymptotic bound $$\begin{aligned} g_n \le C_{s,d}n^{-s}\log (n)^{(d-1)s+1/2}, \end{aligned}$$ which improves on very recent results by shortening the gap between upper and lower bound to $$\sqrt{\log (n)}$$ . The result implies that for dimensions $$d>2$$ any sparse grid sampling recovery method does not perform asymptotically optimal.
Keywords
All Related Versions
Funding Information
- Technische Universität Chemnitz
This publication has 27 references indexed in Scilit:
- Lower bounds for the integration error for multivariate functions with mixed smoothness and optimal Fibonacci cubature for functions on the squareMathematische Nachrichten, 2014
- Mercer’s Theorem on General Domains: On the Interaction between Measures, Kernels, and RKHSsConstructive Approximation, 2012
- B-spline quasi-interpolant representations and sampling recovery of functions with mixed smoothnessJournal of Complexity, 2011
- User-Friendly Tail Bounds for Sums of Random MatricesFoundations of Computational Mathematics, 2011
- On the power of standard information for multivariate approximation in the worst case settingJournal of Approximation Theory, 2009
- Linear information versus function evaluations for -approximationJournal of Approximation Theory, 2008
- On singular values of matrices with independent rowsBernoulli, 2006
- Sparse gridsActa Numerica, 2004
- The Kadison–Singer problem in discrepancy theoryDiscrete Mathematics, 2004
- Extensions of Pure StatesAmerican Journal of Mathematics, 1959