Adaptive Sparsity Matching Pursuit Algorithm for Sparse Reconstruction

This letter presents a new greedy method, called Adaptive Sparsity Matching Pursuit (ASMP), for sparse solutions of underdetermined systems with a typical/random projection matrix. Unlike anterior greedy algorithms, ASMP can extract information on sparsity of the target signal adaptively with a well-designed stagewise approach. Moreover, it takes advantage of backtracking to refine the chosen supports and the current approximation in the process. With these improvements, ASMP provides even more attractive results than the state-of-the-art greedy algorithm CoSaMP without prior knowledge of the sparsity level. Experiments validate the proposed algorithm works well for both noiseless signals and noisy signals, with the recovery quality often outperforming that of l₁-minimization and other greedy algorithms.