2020/09/30 by Nagel, Nicolas, Schäfer, Martin, Ullrich, Tino · 1 citation
#FOS: Mathematics #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.2010.00327
We provide a new upper bound for sampling numbers (gn)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 g2n ≤ (Clog(n))/(n)∑k≥ \lfloor cn \rfloor σk2 , n≥ 2 , where (σk)k∈ ℕ is the sequence of singular numbers (approximation numbers) of the Hilbert-Schmidt embedding Id:H(K) → L2(D,\varrhoD). 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 Hsmix(\mathbbTd) in L2(\mathbbTd) with s>1/2. We obtain the asymptotic bound gn ≤ Cs,dn-slog(n)(d-1)s+1/2 , which improves on very recent results by shortening the gap between upper and lower bound to √(log(n)).