论文标题
$ l_ {2} $中的采样数字的尖锐上限
A sharp upper bound for sampling numbers in $L_{2}$
论文作者
论文摘要
对于集合$ d $的复杂价值功能的类$ f $，我们用$ g_n（f）$表示其采样数字，即以$ l_2 $测量的$ f $上的最小最差案例错误，可以通过$ n $函数评估来实现$ l_2 $。我们证明，在\ mathbb {n} $中有一个通用常数$ c \，因此，如果$ f $是可分离的复制核心Hilbert Space的单位球，则\ [g_ {cn}（f）^2 \，\ le \，\ le \，\ frac \ frac {1} n} {n} {n} {n} {n} {n} {n} \ sum ge f \ q frac^f）其中$ d_k（f）$是$ l_2 $中的$ f $的kolmogorov宽度（或近似编号）。我们还获得了更多通用类$ f $的相似上限，包括在有限域上连续功能空间的所有紧凑子集$ d \ subset \ mathbb {r}^d $，并通过提供逆向不平等的示例来表明这些界限是尖锐的。结果依赖于Kadison-Singer问题的解决方案，我们将其扩展到无限级别矩阵总和的亚采样。
For a class $F$ of complex-valued functions on a set $D$, we denote by $g_n(F)$ its sampling numbers, i.e., the minimal worst-case error on $F$, measured in $L_2$, that can be achieved with a recovery algorithm based on $n$ function evaluations. We prove that there is a universal constant $c\in\mathbb{N}$ such that, if $F$ is the unit ball of a separable reproducing kernel Hilbert space, then \[ g_{cn}(F)^2 \,\le\, \frac{1}{n}\sum_{k\geq n} d_k(F)^2, \] where $d_k(F)$ are the Kolmogorov widths (or approximation numbers) of $F$ in $L_2$. We also obtain similar upper bounds for more general classes $F$, including all compact subsets of the space of continuous functions on a bounded domain $D\subset \mathbb{R}^d$, and show that these bounds are sharp by providing examples where the converse inequality holds up to a constant. The results rely on the solution to the Kadison-Singer problem, which we extend to the subsampling of a sum of infinite rank-one matrices.
