Noisy nonlinear information and entropy numbers
David Krieg, Erich Novak, Leszek Plaskota, Mario Ullrich
即使测量值是自适应地选择的,也不可能从R^m中恢复矢量。 最近,已经表明,人们只能使用O(log m)连续(甚至Lipschitz)自适应测量,以任意精度从R^m中恢复向量,从而与各种近似问题的线性信息相比,连续信息呈指数级加速。 值本说明中,我们描述了在熵数方面受到确定性噪声干扰的最佳(非)连续信息的质量。 这表明,在噪声存在的情况下,连续在线性测量的潜在增益是有限的,但在某些情况下很重要。
It is impossible to recover a vector from ℝ^m with less than m linear measurements, even if the measurements are chosen adaptively. Recently, it has been shown that one can recover vectors from ℝ^m with arbitrary precision using only O(log m) continuous (even Lipschitz) adaptive measurements, resulting in an exponential speed-up of continuous information compared to linear information for various approximation problems. In this note, we characterize the quality of optimal (dis-)continuous inform...