@Article{CiCP-38-1389,
author = {Ding , ZhaoHuang , JunjunJiao , YulingLu , Xiliang and Yang , Jerry Zhijian},
title = {Robust Decoding from Binary Measurements with  Cardinality Constraint Least Squares},
journal = {Communications in Computational Physics},
year = {2025},
volume = {38},
number = {5},
pages = {1389--1416},
abstract = {<p style="text-align: justify;">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.</p>},
issn = {1991-7120},
doi = {https://doi.org/10.4208/cicp.OA-2023-0285},
url = {http://global-sci.org/intro/article_detail/cicp/24461.html}
}