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

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.