Binary Least Squares: An Algorithm for Binary Sparse Signal Recovery (Journal of Computational Mathematics, 2024)
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 calledbinary 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$ iterationsof BLS based on the mutual coherence and restricted isometry property of the measurement matrix, respectively. Finally, extensive numerical tests are performed to compare theefficiency 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 leastsquares (OLS), compressive sampling matching pursuit (CoSaMP), hard thresholding pursuit (HTP), Newton-step-based iterative hard thresholding (NSIHT), Newton-step-basedhard thresholding pursuit (NSHTP), binary matching pursuit (BMP) and $ℓ_1$-regularizedleast squares. Test results show that: (1) BLS can be 10-200 times more efficient thanBatch-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 algorithmwith 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$ andhigher support reconstruction probability for large $K.$ Numerical tests on the generalizedspace shift keying (GSSK) detection indicate that although BLS is a little slower thanBMP, 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 theother seven algorithms.
Keywords: Binary sparse signal; Precise support reconstruction; Binary least squares.