arxivcs.ITeess.SP2026-07-07
Near-Optimal Lower Bounds on One-Bit Compressed Sensing of Approximately Sparse Signals
Junren Chen, Arya Mazumdar, Ming Yuan
This paper provides the first near-optimal lower bounds for one-bit compressed sensing of approximately sparse signals lying in a scaled $\ell_1$ ball, which is a commonly adopted relaxation of the exactly $k$-sparse assumption. In prior works, the best known upper bounds on unif…