Sharp bounds for non-adaptive randomized approximation of high-dimensional noisy vectors
Robert J. Kunsch, Marcin Wnuk · 2026
Read Sharp bounds for non-adaptive randomized approximation of high-dimensional noisy vectors by Robert J. Kunsch, Marcin Wnuk (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2608-00148.txt.
Description
Kunsch and Wnuk study randomized approximation of high-dimensional vectors. The target is the embedding of l_p into l_q in finite dimension m. They allow only non-adaptive randomized algorithms. Such an algorithm may use up to n linear measurements of the input. Here n is much smaller than m.
They prove lower bounds on the approximation error for that setting. The bounds depend jointly on n and m. They match upper bounds known before, the authors show. The range runs from p equal to two up to q equal to infinity, with p below q. Readers get sharp complexity for a clean, basic problem.
Catalog record
| CREATOR | Robert J. Kunsch, Marcin Wnuk |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2608.00148