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.

翻译：单比特压缩感知（1bCS）中的支撑集恢复问题旨在从观测值 $y=\\text{sign}(Ax)$ 中恢复信号 $x\\in \\mathbb{R}^n$ 的支撑集，记为 $\\text{supp}(x)$，其中 $A\\in \\mathbb{R}^{m\\times n}$ 为感知矩阵，且 $|\\text{supp}(x)|\\leq k, k \\ll n$。在此设定下，现有大多数工作的恢复运行时间为 $\\Omega(n)$。本文提出了两种具有亚线性 $o(n)$ 运行时间的方案。（1）对于通用精确支撑集恢复，提出一种方案，其测量次数 $m=O(k^2\\log(n/k)\\log n)$，运行时间 $D=O(km)$。对于通用 $\\epsilon$-近似支撑集恢复，采用相同方案，其测量次数 $m=O(k\\epsilon^{-1}\\log(n/k)\\log n)$，运行时间 $D=O(\\epsilon^{-1}m)$。与当前最优结果（Matsumoto 等人，2023）相比，该方案在测量次数上增加了一个 $O(\\log n)$ 因子，但显著改善了运行时间。（2）对于亚线性区域内的概率精确支撑集恢复，提出一种方案，其测量次数 $m:=O(k\\frac{\\log k}{\\log\\log k}\\log n)$，运行时间 $O(m)$，且具有趋于零的错误概率，改进了 Yang 等人（2025）的最新结果。