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

arXiv (Cornell University)

Abstract

We study the complexity of approximating the finite-dimensional vector space embedding $\ell_p^m \hookrightarrow \ell_q^m$ for $2 \leq p < q \leq \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.

Authors 2

1. Robert J. Kunsch Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University , Mathematics for Uncertainty Quantification , Pontdriesch 10-16 , 52062 Aachen ,

2. Marcin Wnuk

   University of Passau

   Affiliation as printed

   Fakultät für Informatik und Mathematik , Passau University , Instraße 33 , 94032 Passau ,