Support Recovery in One-bit Compressed Sensing with Near-Optimal Measurements and Sublinear Time

[2511.10777] Support Recovery in One-bit Compressed Sensing with Near-Optimal Measurements and Sublinear Time Skip to main content Search Submit Donate Log in Computer Science > Information Theory arXiv:2511.10777 (cs) [Submitted on 13 Nov 2025 ( v1 ), last revised 26 Aug 2026 (this version, v4)] Title: Support Recovery in One-bit Compressed Sensing with Near-Optimal Measurements and Sublinear Time Authors: Xiaxin Li , Arya Mazumdar View PDF HTML (experimental) Abstract: One-bit compressed sensing (1bCS) addresses the recovery of sparse signals from highly quantized measurements, retaining only the sign of each linear measurement. From a data compression perspective, the one-bit measurements form a compact binary representation of sparse signals. The support recovery problem seeks to recover the support of an unknown signal $x\in\mathbb{R}^n$, $\mathrm{supp}(x)$, from $y=\mathrm{sgn}(Ax)$, where $A\in\mathbb{R}^{m\times n}$ is the measurement matrix and $|\mathrm{supp}(x)|\le k\ll n$. Existing methods seek to minimize the number of measurements but often incur $\Omega(n)$ decoding complexity, limiting their applicability to large-scale problems. We propose new 1bCS schemes that achieve sublinear decoding complexity while maintaining near-optimal measurement bounds. For universal support recovery, our framework provides: (i) exact recovery with $m=O(k^2\log(n/k)\log n)$ measurements and decoding complexity $D=O(km)$, and (ii) $\epsilon$-approximate recovery with $m=O(k\epsilon^{-1}\log(n/k)\log n)$ and $D=O(\epsilon^{-1}m)$. For probabilistic exact recovery, we design a scheme with $m=O(k\log k\log n)$ and $D=O(m)$, achieving vanishing error probability. Our schemes leverage ideas from group testing to achieve near-optimal support compression with substantially reduced decoding complexity. Subjects: Information Theory (cs.IT) ; Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS) Cite as: arXiv:2511.10777 [cs.IT] (or arXiv:2511.10777v4 [cs.IT] for this version) https://doi.org/10.48550/arXiv.2511.10777 Focus to learn more arXiv-issued DOI via DataCite Submission history From: Xiaxin Li [ view email ] [v1] Thu, 13 Nov 2025 20:02:26 UTC (56 KB) [v2] Mon, 17 Nov 2025 02:52:53 UTC (56 KB) [v3] Sun, 12 Apr 2026 21:05:57 UTC (60 KB) [v4] Wed, 26 Aug 2026 23:40:48 UTC (149 KB) Full-text links: Access Paper: View PDF HTML (experimental) TeX Source view license Current browse context: cs.IT < prev | next > new | recent | 2025-11 Change to browse by: cs cs.DM cs.DS math math.IT References & Citations NASA ADS Google Scholar Semantic Scholar export BibTeX citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer ( What is the Explorer? ) Connected Papers Toggle Connected Papers ( What is Connected Papers? ) Litmaps Toggle Litmaps ( What is Litmaps? ) scite.ai Toggle scite Smart Citations ( What are Smart Citations? ) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv ( What is alphaXiv? ) Links to Code Toggle CatalyzeX Code Finder for Papers ( What is CatalyzeX? ) DagsHub Toggle DagsHub ( What is DagsHub? ) GotitPub Toggle Gotit.pub ( What is GotitPub? ) Huggingface Toggle Hugging Face ( What is Huggingface? ) ScienceCast Toggle ScienceCast ( What is ScienceCast? ) Demos Demos Replicate Toggle Replicate ( What is Replicate? ) Spaces Toggle Hugging Face Spaces ( What is Spaces? ) Spaces Toggle TXYZ.AI ( What is TXYZ.AI? ) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower ( What are Influence Flowers? ) Core recommender toggle CORE Recommender ( What is CORE? ) Author Venue Institution Topic About arXivLabs arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs . Which authors of this paper are endorsers? | Disable MathJax ( What is MathJax? ) We gratefully acknowledge support from our major funders , member institutions , and all contributors. About · Help · Contact · Subscribe · Copyright · Privacy · Accessibility · Operational Status (opens in new tab) Major funding support from

Related documents

• Support Recovery in One-bit Compressed Sensing with Near-Optimal Measurements and Sublinear Time#677445
• Demystifying compressive sensing#359235
• Learning to Transmit Over Unknown Erasure Channels with Empirical Erasure Rate Feedback#793456
• Learning to Transmit Over Unknown Erasure Channels with Empirical Erasure Rate Feedback#789452
• Phase Transition in Binary Compressed Sensing via Annealing with Adaptive Regularization#1122721