Sharp bounds for non-adaptive randomized approximation of high-dimensional noisy vectors

Abstract

We study the complexity of approximating the finite-dimensional vector space embedding ${\ell }_p^m\hookrightarrow {\ell }_q^m$ for $2\le p<q\le \infty$ based on non-adaptive randomized algorithms that use up to $n$ arbitrary linear functionals as information on a problem instance $x\in {\mathbb{R}}^m$, where $n\ll m$. We prove lower bounds on the non-adaptive randomized approximation error with a joint dependence on $(n,m)$ matching previously known upper bounds.