Support Recovery in One-bit Compressed Sensing with Near-Optimal Measurements and Sublinear Time
This work addresses the bottleneck of high decoding complexity in one-bit compressed sensing for large-scale sparse signal recovery, offering a practical trade-off between measurement efficiency and computational cost.
This paper proposes one-bit compressed sensing schemes that achieve sublinear decoding complexity while maintaining near-optimal measurement bounds for support recovery. For universal exact recovery, they achieve m = O(k^2 log(n/k) log n) measurements with O(km) decoding time, and for probabilistic exact recovery, m = O(k (log k / log log k) log n) with O(m) decoding time.
One-bit compressed sensing (1bCS) addresses the recovery of sparse signals from highly quantized measurements, retaining only the sign of each linear measurement. In the support recovery setting, the goal is to identify $\text{supp}(x)$, the nonzero coordinates of an unknown signal $x \in \mathbb{R}^n$ from $y = \text{sign}(Ax)$, where $A \in \mathbb{R}^{m \times n}$ and $|\text{supp}(x)| \le k \ll n$. Existing methods minimize the number of measurements but often incur $Ω(n)$ decoding complexity, limiting large-scale applicability. 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) $ε$-approximate recovery with $m = O(k ε^{-1} \log(n/k) \log n)$ and $D=O(ε^{-1} m)$. For probabilistic exact recovery, we design a scheme with $m = O\big(k \frac{\log k}{\log\log k} \log n\big)$ and $D=O(m)$, achieving vanishing error probability. Our approach leverages ideas from group testing to bridge classical sparse recovery techniques with modern algorithmic efficiency considerations, highlighting a new trade-off between compression efficiency and computational complexity.