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

Robert J. Kunsch, Marcin Wnuk

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 rand…