{"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","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-31","reactions":{}}