论文标题
在最小二乘算法的最坏情况下，$ l_2 $ - approximation具有很高的概率
On the worst-case error of least squares algorithms for $L_2$-approximation with high probability
论文作者
论文摘要
最近在[4]中显示，对于$ l_2 $ - 对希尔伯特空间的函数的应用，功能值几乎与任意线性信息一样强大，如果近似编号是正方形的，则功能值。也就是说，我们证明了\ [ e_n \，\ sillsim \，\ sqrt {\ frac {1} {k_n} \ sum_ {采样数字和$ a_k $是近似编号。特别是，如果$（a_k）\ in \ ell_2 $，则$ e_n $和$ a_n $的$ e_n $是相同的多项式订单。为此，我们基于I.I.D.提出了一种明确的（加权最小二乘）算法。随机点并证明这有正概率。这意味着存在良好的确定性抽样算法。 在这里，我们提出了[4]中证明的修改，该修改表明，同一算法的概率至少可用于$ 1- {n^{ - c}} $，用于所有$ c> 0 $。
It was recently shown in [4] that, for $L_2$-approximation of functions from a Hilbert space, function values are almost as powerful as arbitrary linear information, if the approximation numbers are square-summable. That is, we showed that \[ e_n \,\lesssim\, \sqrt{\frac{1}{k_n} \sum_{j\geq k_n} a_j^2} \qquad \text{ with }\quad k_n \asymp \frac{n}{\ln(n)}, \] where $e_n$ are the sampling numbers and $a_k$ are the approximation numbers. In particular, if $(a_k)\in\ell_2$, then $e_n$ and $a_n$ are of the same polynomial order. For this, we presented an explicit (weighted least squares) algorithm based on i.i.d. random points and proved that this works with positive probability. This implies the existence of a good deterministic sampling algorithm. Here, we present a modification of the proof in [4] that shows that the same algorithm works with probability at least $1-{n^{-c}}$ for all $c>0$.
