A new upper bound for sampling numbers
share
We provide a new upper bound for sampling numbers (g_n)_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 ≤Clog(n)/n∑_k≥⌊ cn ⌋σ_k^2 , n≥ 2 , where (σ_k)_k∈ℕ is the sequence of singular numbers (approximation numbers) of the Hilbert-Schmidt embedding Id:H(K) → L_2(D,ϱ_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_mix(𝕋^d) in L_2(𝕋^d) with s>1/2. We obtain the asymptotic bound g_n ≤ C_s,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)).
READ FULL TEXT