(untitled) (Communications in Computational Physics, 2025)
The principal goal of 1-bit compressive sampling is to decode n-dimensional signals with a sparsity level of s from m binary measurements. This task presents significant challenges due to nonlinearity, noise, and sign flips. In this paper, we propose the use of the cardinality-constrained least squares decoder as an optimal solution. We establish that, with high probability, the proposed decoder achieves a minimax estimation error, up to a constant c, as long as m ≥ O(slog n). In terms of computational efficiency, we employ a generalized Newton algorithm (GNA) to solve the cardinality-constrained minimization problem. At each iteration, this approach incurs the cost of solving a least squares problem with a small size. Through rigorous analysis, we demonstrate that, with high probability, the ℓ_∞ norm of the estimation error between the output of GNA and the underlying target diminishes to O( log nm ) after at most O(log s) iterations. Furthermore, provided that the target signal is detectable, we can recover the underlying support with high probability within O(log s) steps. To showcase the robustness of our proposed decoder and the efficiency of the GNA algorithm, we present extensive numerical simulations and comparisons with state-of-the-art methods.