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

1. Problem Statement

The paper addresses the One-bit Compressed Sensing (1bCS) problem, specifically focusing on support recovery.

• Goal: Recover the support (the set of indices of non-zero entries) of an unknown $k$-sparse signal $x \in \mathbb{R}^n$ from highly quantized measurements $y = \text{sign}(Ax)$, where $A \in \mathbb{R}^{m \times n}$ is the sensing matrix and $m \ll n$.
• Challenge: Existing 1bCS support recovery algorithms typically require iterating over all $n$ columns of the sensing matrix during decoding, resulting in a computational complexity of $\Omega(n)$. This limits scalability for large $n$.
• Objective: Design 1bCS schemes that achieve sublinear decoding complexity (ideally $O(m)$ or $O(km)$) while maintaining near-optimal bounds on the number of measurements $m$.

2. Methodology

The authors bridge the gap between compressed sensing and nonadaptive group testing by leveraging structural properties of combinatorial matrices. Their approach involves two main strategies: Universal Recovery (works for all sparse vectors) and Probabilistic Recovery (works for a fixed vector with high probability).

A. Core Techniques

1. Combinatorial Matrices:

   • The authors utilize $(k, l)$-distinguishable matrices and List Union-Free (UF) families.
   • Distinguishability: Ensures that for any $k$-sparse support, a large fraction of indices can be uniquely identified as "singletons" (measurements where only one support element contributes).
   • List UF: Used to filter out false positives by ensuring that the union of columns from a "bad" set does not mimic the signature of a "good" set.

2. Block Decoding & U-Magnification:

   • To achieve sublinear time, the authors adapt the SAFFRON algorithm from group testing.
   • They employ a signature matrix $U$ (based on binary representations of indices) to "magnify" the sensing matrix.
   • Mechanism: Each non-zero entry in a base matrix $M$ is replaced by a column of $U$. This creates a structure where "singleton" measurements (those intersecting exactly one support element) produce a unique signature in the measurement vector, allowing for $O(1)$ identification of candidate indices.

3. Two-Stage Decoding:

   • Stage 1 (Candidate Generation): Identify a superset $S$ of the true support by detecting singletons in the magnified measurements. This step is fast ($O(m)$).
   • Stage 2 (Pruning): Refine $S$ by checking against a secondary List UF matrix ($A''$) to eliminate false positives. The complexity depends on the size of $S$ (which is small) rather than $n$.

4. Handling "Accidental Zeros" (Probabilistic Scheme):

   • In 1bCS, unlike group testing, a measurement can be zero even if the support intersects the measurement row (if the weighted sum is zero).
   • To mitigate this, the authors use Totally Invertible Matrices (AsTIM). They repeat each group testing measurement $k_\alpha$ times with random coefficients. This ensures that if a measurement intersects the support, the probability of the sum being exactly zero is negligible.

3. Key Contributions & Results

The paper proposes three specific schemes, collectively termed EDOCS (Efficient Decoding One-bit Compressed Sensing):

A. Universal $\epsilon$-Approximate Recovery (EDOCS-AA)

• Guarantee: Recovers a set $S$ such that the symmetric difference with the true support is at most $\epsilon k$.
• Measurements ($m$): $O(k \epsilon^{-1} \log(n/k) \log n)$.
• Decoding Complexity ($D$): $O(\epsilon^{-1} m)$.
• Significance: Achieves sublinear time while allowing a small approximation error.

B. Universal Exact Recovery (EDOCS-AE)

• Guarantee: Recovers the exact support $S = \text{supp}(x)$ for all $k$-sparse vectors.
• Measurements ($m$): $O(k^2 \log(n/k) \log n)$.
• Decoding Complexity ($D$): $O(km)$.
• Significance: This is the first universal scheme for 1bCS to achieve sublinear decoding complexity. It trades a slight increase in measurements (factor of $\log n$) for a massive reduction in time complexity (from $O(n)$ to $O(km)$).

C. Probabilistic Exact Recovery (EDOCS-EE)

• Guarantee: Recovers the exact support with high probability for a fixed signal $x$.
• Measurements ($m$): $O\left(k \frac{\log k}{\log \log k} \log n\right)$.
• Decoding Complexity ($D$): $O(m)$.
• Significance: Improves upon prior work [YZG25] by significantly reducing the measurement count (from $O(k^2 \log^2 n)$ to near-linear in $k$) and achieving linear decoding time.

4. Comparison with State-of-the-Art

• Prior Art: Most existing 1bCS support recovery algorithms have decoding complexity $\Omega(n)$ because they must check every column of $A$.
• Improvement: The proposed schemes reduce decoding complexity to be dependent on $m$ and $k$ (sublinear in $n$).
  • Approximate Recovery: Complexity reduced from $O(n \epsilon^{-1} \log(n/k))$ to $O(k \epsilon^{-2} \log n \log(n/k))$.
  • Exact Recovery: Complexity reduced from $O(nk \log n)$ to $O(k^3 \log n \log(n/k))$.
• Trade-off: The schemes introduce an additional $O(\log n)$ factor in the number of measurements compared to some non-sublinear methods, but this is a minor price for the exponential gain in decoding speed.

5. Significance and Future Directions

• Scalability: The work makes 1bCS feasible for massive-scale applications (e.g., high-dimensional genomics, massive MIMO) where $n$ is too large for linear-time decoding.
• Theoretical Bridge: It successfully adapts group testing techniques (specifically fast binary splitting and list UF families) to the continuous, sign-based domain of 1bCS, overcoming the "accidental zero" challenge.
• Future Work: The authors identify open problems, including:
  • Designing schemes that achieve optimal measurement complexity and sublinear decoding simultaneously.
  • Extending the framework to noisy settings (e.g., Massart noise).
  • Developing universal $\epsilon$-superset recovery schemes with better performance.

In summary, this paper provides a breakthrough in the computational efficiency of one-bit compressed sensing, demonstrating that near-optimal support recovery is possible in sublinear time by cleverly combining combinatorial matrix design with group testing decoding strategies.