TY - JOUR T1 - Robust Decoding from Binary Measurements with Cardinality Constraint Least Squares AU - Ding , Zhao AU - Huang , Junjun AU - Jiao , Yuling AU - Lu , Xiliang AU - Yang , Jerry Zhijian JO - Communications in Computational Physics VL - 5 SP - 1389 EP - 1416 PY - 2025 DA - 2025/09 SN - 38 DO - http://doi.org/10.4208/cicp.OA-2023-0285 UR - https://global-sci.org/intro/article_detail/cicp/24461.html KW - 1-bit compressive sampling, least square with cardinality constraint, minimax estimation error, generalized Newton algorithm, support recovery. AB -

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.