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

2026/07/31 by Robert J. Kunsch, Marcin Wnuk
Mathematics · Computer Science · #math.NA #cs.NA #msc:65C #msc:65D #msc:46 #msc:60

paper · pdf

arxiv created 2026/07/31 · arxiv updated 2026/08/04

Abstract

We study the complexity of approximating the finite-dimensional vector space embedding ℓ_p^m \hookrightarrow ℓ_q^m for 2 ≤ p < q ≤ ∞ based on non-adaptive randomized algorithms that use up to n arbitrary linear functionals as information on a problem instance x ∈ ℝ^m, where n ≪ m. We prove lower bounds on the non-adaptive randomized approximation error with a joint dependence on (n,m) matching previously known upper bounds.

Citations

• Adaptive and non-adaptive randomized approximation of high-dimensional vectors
• Uniform approximation of vectors using adaptive randomized information
• Randomized approximation of summable sequences -- adaptive and non-adaptive
• High-Dimensional Function Approximation: Breaking the Curse with Monte Carlo Methods
• Lower Bounds for Adaptive Sparse Recovery
• Lower Bounds for Sparse Recovery