多路径支撑集回溯贪婪重构算法

Multipath backtracking greedy pursuit algorithm

针对现有压缩感知贪婪算法容易陷于局部最优、过拟合等问题,提出一种稀疏恢复算法,称为多路径支撑集回溯贪婪重构(multipath backtracking greedy pursuit,MBGP)算法。该算法以最小残差为重构目标,对候选原子展开多条路径同时搜索,且每次筛选多个原子,通过回溯过程剔除误选的原子。基于有限等距性质给出MBGP算法重构信号的充分条件,以确保其从测量值精确恢复任何K-稀疏信号,并通过信号重构能力来评估MBGP算法的性能。数值实验结果表明,该算法在相同信号条件下,能够在采样数更少、稀疏度更大的场合下精确重构信号,且性能更逼近理想Oracle-最小二乘估计器。

For the existing compressed sensing(CS)greedy algorithm,it is easy to fall into problems such as local optimum and overfitting.A sparse recovery algorithm called multipath backtracking greedy pursuit(MBGP)is proposed.MBGP algorithm searches the signal support set and iteratively examines multiple candidate support set estimates at the same time,and finally selects the one that minimizes the reconstruction residual.Based on the restricted isometry property,the sufficient conditions for the MBGP algorithm to reconstruct the signal are given to ensure that it can accurately recover any K-sparse signal from the measured value.The performance of the MBGP algorithm is evaluated by the signal reconstruction ability.Numerical experimental results show that the algorithm can accurately reconstruct signals with fewer samples and greater sparsity under the same signal conditions,and its performance is closer to the ideal Oracle-least square estimator.