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

The problem of support recovery in one-bit compressed sensing (1bCS) aim to recover the support of a signal $x\in \mathbb{R}^n$, denoted as supp$(x)$, from the observation $y=\text{sign}(Ax)$, where $A\in \mathbb{R}^{m\times n}$ is a sensing matrix and $|\text{supp}(x)|\leq k, k \ll n$. Under this setting, most preexisting works have a recovery runtime $Ω(n)$. In this paper, we propose two schemes that have sublinear $o(n)$ runtime. (1): For the universal exact support recovery, a scheme of $m=O(k^2\log(n/k)\log n)$ measurements and runtime $D=O(km)$. For the universal $ε$-approximate support recovery, the same scheme with $m=O(kε^{-1}\log(n/k)\log n)$ and runtime $D=O(ε^{-1}m)$, improving the runtime significantly with an extra $O(\log n)$ factor in the number of measurements compared to the current optimal (Matsumoto et al., 2023). (2): For the probabilistic exact support recovery in the sublinear regime, a scheme of $m:=O(k\frac{\log k}{\log\log k}\log n)$ measurements and runtime $O(m)$, with vanishing error probability, improving the recent result of Yang et al., 2025.