Using techniques developed recently in the field of compressed sensing we prove new upper bounds for general (non-linear) sampling numbers of (quasi-)Banach smoothness spaces in $L^2$. In relevant cases such as mixed and isotropic weighted Wiener classes or Sobolev spaces with mixed smoothness, sampling numbers in $L^2$ can be upper bounded by best $n$-term trigonometric widths in $L^{\infty}$. We describe a recovery procedure based on $\ell^1$-minimization (basis pursuit denoising) using only $m$ function values with $m$ close to $n$. With this method, a significant gain in the rate of convergence compared to recently developed linear recovery methods is achieved. In this deterministic worst-case setting we see an additional speed-up of $n^{-1/2}$ compared to linear methods in case of weighted Wiener spaces. For their quasi-Banach counterparts even arbitrary polynomial speed-up is possible. Surprisingly, our approach allows to recover mixed smoothness Sobolev functions belonging to $S^r_pW(\mathbb{T}^d)$ on the $d$-torus with a logarithmically better error decay than any linear method can achieve when $1 < p < 2$ and $d$ is large. This effect is not present for isotropic Sobolev spaces.
翻译:使用压缩遥感领域最近开发的技术,我们证明,对于(quasi-)Banach平滑空间的普通(非线性)采样数量,(quasi-)Banach平滑空间的(非线性)采样数量,我们证明了新的上限。在混合的和北偏加权的Wiener类或平滑混合的Sobolev空间等相关案例中,以$2美元采样数量,可以用美元为最优的美元中期三角度宽度($ ⁇ infty}$)进行上限。我们描述了一种基于$@ell_1$(basis 追逐去novis) 的回收程序。根据这种方法,只要使用美元,且美元接近于美元。使用这种方法,与最近开发的线性恢复方法相比,趋同率大幅增长。在这种确定性最差的情况下,我们看到比加权维纳空间的线性宽度宽度宽度宽度宽度宽度宽度宽度宽度宽度宽度宽度增加1美元。对于准的对应方,即使是任意的多球度加速度加速度加速度加速速度。因此,我们的方法可以做到在2美元以上的轨道上恢复这种顺滑度上为1美元的顺差的顺差的软度为1美元。