Noisy Nonlinear Information and Entropy Numbers

Abstract It is impossible to recover a vector from $$\mathbb {R}^m$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>m</mml:mi> </mml:msup> </mml:math> with less than m linear measurements, even if the measurements are chosen adaptively. Recently, it has been shown that one can recover vectors from $$\mathbb {R}^m$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>m</mml:mi> </mml:msup> </mml:math> with arbitrary precision using only $$O(\log m)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>m</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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 information that is disturbed by deterministic noise in terms of entropy numbers. This shows that in the presence of noise the potential gain of continuous over linear measurements is limited, but significant in some cases.