Id: arxiv/2608.00148 Url: https://arxiv.org/abs/2608.00148 Tags: math.NA Score: 0 Title: Sharp bounds for non-adaptive randomized approximation of high-dimensional vectors Domain: math.NA Source: arxiv Authors: Robert J. Kunsch, Marcin Wnuk Reviews: 0 Subject: math.NA Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-31 Page: https://delphi.science/r/arxiv/2608.00148 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.