{"ID":6138865,"CreatedAt":"2026-07-09T01:07:32.349475501Z","UpdatedAt":"2026-07-10T19:18:29.002700277Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.06750","arxiv_id":"2607.06750","title":"Near-Optimal Lower Bounds on One-Bit Compressed Sensing of Approximately Sparse Signals","abstract":"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 uniform Euclidean error are of order $\\widetilde{O}((k/m)^{1/3})$, where $m$ is the number of measurements. Under sub-Gaussian matrices, we establish nearly matching lower bounds for both the canonical one-bit compressed sensing model and the uniformly dithered model. Our argument is to first embed a small Euclidean ball into the signal set, which is straightforward for the dithered model but relies on a lifting map for the canonical model, and then construct two signals in this small ball that are separated in Euclidean distance by at least $(k/m)^{1/3}$ (up to logarithmic factor) but are indistinguishable from the binary measurements. Moreover, our argument extends to approximately sparse signals that live in a properly scaled $\\ell_q$ ball $(q\\in [0,1])$, yielding a lower bound $\\widetildeΩ((k/m)^{\\frac{2-q}{2+q}})$ that smoothly bridges the cases of exact sparsity ($q=0$) and $\\ell_1$ sparsity ($q=1$). Finally, we discuss the extensions of our lower bounds to sub-Weibull matrices, adversarial bit flipping, matrix recovery, and characterize the transition to the non-sparse case.","short_abstract":"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 uniform Euclidean error are of order $\\widet...","url_abs":"https://arxiv.org/abs/2607.06750","url_pdf":"https://arxiv.org/pdf/2607.06750v1","authors":"[\"Junren Chen\",\"Arya Mazumdar\",\"Ming Yuan\"]","published":"2026-07-07T19:31:38Z","proceeding":"cs.IT","tasks":"[\"cs.IT\",\"eess.SP\"]","methods":"[]","has_code":false}