TY - JOUR
T1 - Binary Least Squares: An Algorithm for Binary Sparse Signal Recovery
AU - Wen , Jinming
JO - Journal of Computational Mathematics
VL - 2
SP - 493
EP - 514
PY - 2024
DA - 2024/11
SN - 43
DO - http://doi.org/10.4208/jcm.2308-m2023-0044
UR - https://global-sci.org/intro/article_detail/jcm/23547.html
KW - Binary sparse signal, Precise support reconstruction, Binary least squares.
AB - <p style="text-align: justify;">A fundamental problem in some applications including group testing and communications is to acquire the support of a $K$-sparse signal $x,$ whose nonzero elements are 1,
from an underdetermined noisy linear model. This paper first designs an algorithm called
binary least squares (BLS) to reconstruct $x$ and analyzes its complexity. Then, we establish two sufficient conditions for the exact reconstruction of $x$’s support with $K$ iterations
of BLS based on the mutual coherence and restricted isometry property of the measurement matrix, respectively. Finally, extensive numerical tests are performed to compare the
efficiency and effectiveness of BLS with those of batch orthogonal matching pursuit (Batch-OMP) which to our best knowledge is the fastest implementation of OMP, orthogonal least
squares (OLS), compressive sampling matching pursuit (CoSaMP), hard thresholding pursuit (HTP), Newton-step-based iterative hard thresholding (NSIHT), Newton-step-based
hard thresholding pursuit (NSHTP), binary matching pursuit (BMP) and $ℓ_1$-regularized
least squares. Test results show that: (1) BLS can be 10-200 times more efficient than
Batch-OMP, OLS, CoSaMP, HTP, NSIHT and NSHTP with higher probability of support reconstruction, and the improvement can be 20%-80%; (2) BLS has more than 25%
improvement on the support reconstruction probability than the explicit BMP algorithm
with a little higher computational complexity; (3) BLS is around 100 times faster than $ℓ_1$-regularized least squares with lower support reconstruction probability for small $K$ and
higher support reconstruction probability for large $K.$ Numerical tests on the generalized
space shift keying (GSSK) detection indicate that although BLS is a little slower than
BMP, it is more efficient than the other seven tested sparse recovery algorithms, and although it is less effective than $ℓ_1$-regularized least squares, it is more effective than the
other seven algorithms.</p>