Robust Decoding from Binary Measurements with Cardinality Constraint Least Squares

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 ≥ \mathcal{O}(s{\rm log} \ 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 $\mathcal{O}( \sqrt{\frac{{\rm log} \ n}{m}})$ after at most $\mathcal{O}({\rm log} \ s)$ iterations. Furthermore, provided that the target signal is detectable, we can recover the underlying support with high probability within $\mathcal{O}({\rm 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.