PreprintCC BY 4.0arXiv
Sharp bounds for non-adaptive randomized approximation of high-dimensional vectors
Abstract
We study the complexity of approximating the finite-dimensional vector space embedding ℓpm ↪ ℓqm 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.
Related
- Adaptive Randomized Pivoting for Tensor Cross Approximation in the T-Product Framework
- Optimal Sobolev Rate for Gaussian Density Approximation of Wiener Chaos Vectors
- Bang vectors in the real polarization problem: The exact dimensional range
- Lower bounds in H2-rational approximation to Blaschke products
- Wasserstein bounds for invariant measures in the Smoluchowski-Kramers approximation with stable noise
BibTeX
@misc{kunsch2026sharp,
title = {{Sharp bounds for non-adaptive randomized approximation of high-dimensional vectors}},
author = {Robert J. Kunsch and Marcin Wnuk},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.00148},
eprint = {2608.00148},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.00148},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sharp bounds for non-adaptive randomized approximation of high-dimensional vectors
AU - Robert J. Kunsch
AU - Marcin Wnuk
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2608.00148
UR - https://arxiv.org/abs/2608.00148
AB - We study the complexity of approximating the finite-dimensional vector space embedding ℓ_p^m ↪ ℓ_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.
ER -