BINARY LEAST SQUARES:AN ALGORITHM FOR BINARY SPARSE SIGNAL RECOVERY  

作　　者：Jinming Wen 

机构地区：[1]College of Information Science and Technology,Jinan University,Guangzhou 510632,China

出　　处：《Journal of Computational Mathematics》2025年第2期493-514,共22页计算数学(英文)

基　　金：supported by the NSFC(Grant Nos.12271215,12326378 and 11871248);by the Guangdong Basic and Applied Basic Research Foundation(Grant No.2022A1515010029);by the Guangzhou Science and Technology Foundation Committee(Grant No.202201011126).

摘　　要：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(BatchOMP)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.

关 键 词：Binary sparse signal Precise support reconstruction Binary least squares 

分 类 号：O17[理学—数学]