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

arXiv: https://arxiv.org/abs/2511.10777 · HTML: https://mlsanity.com/paper/2511.10777/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2025.

## Built on by (most cited first, 1 of 1)

- [Efficient Support Recovery of Mixtures of Sparse Linear Classifiers with Fewer Measurements](https://mlsanity.com/paper/2609.32176/) (2026)

## Abstract (arXiv)

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∈ℝn, supp(x), from y=sgn(Ax), where A∈ℝm× n is the measurement matrix and |supp(x)|≤ kll 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(k2log(n/k)log n) measurements and decoding complexity D=O(km), and (ii) ε-approximate recovery with m=O(kε-1log(n/k)log n) and D=O(ε-1m). For probabilistic exact recovery, we design a scheme with m=O(klog klog 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.