Adaptive and non-adaptive randomized approximation of high-dimensional vectors

Abstract

We study approximation of the embedding ${\ell }_p^m\hookrightarrow {\ell }_q^m$, $1\le p<q\le \infty$, based on randomized algorithms that use up to $n$ arbitrary linear functionals as information on a problem instance where $n\ll m$. By analysing adaptive methods we show upper bounds for which the information-based complexity $n$ exhibits only a $(\log \log m)$-dependence. In the case $q<\infty$ we use a multi-sensitivity approach in order to reach optimal polynomial order in $n$ for the Monte Carlo error. We also improve on non-adaptive methods for $q<\infty$ by denoising known algorithms for uniform approximation.