Sharp bounds for non-adaptive randomized approximation of high-dimensional vectors
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.00148
curl -X POST /api/v1/records/arxiv/2608.00148/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.00148/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'