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

CREATORRobert J. Kunsch, Marcin Wnuk
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2608.00148

Browse the full library · About the Tower of Babel