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 $\Omega(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 $\epsilon$-approximate support recovery, the same scheme with $m=O(k\epsilon^{ -1}\log(n/k)\log n)$ and runtime $D=O(\epsilon^{ -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.
Categories: cs.IT cs.DM cs.DS math.IT