Abstract:

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.

Key words: compressed sensing (CS), signal recovery, matching pursuit, subspace pursuit, pruning, backtracking, greedy algorithm