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.

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)