Numerical Studies of the Generalized l₁ Greedy Algorithm for Sparse Signals

The generalized l ₁ greedy algorithm was recently introduced and used to reconstruct medical images in computerized tomography in the compressed sensing framework via total variation minimization. Experimental results showed that this algorithm is superior to the reweighted l ₁ -minimization and l ₁ greedy algorithms in reconstructing these medical images. In this paper the effectiveness of the generalized l ₁ greedy algorithm in finding random sparse signals from underdetermined linear systems is investigated. A series of numerical experiments demonstrate that the generalized l ₁ greedy algorithm is superior to the reweighted l ₁ -minimization and l ₁ greedy algorithms in the successful recovery of randomly generated Gaussian sparse signals from data generated by Gaussian random matrices. In particular, the generalized l ₁ greedy algorithm performs extraordinarily well in recovering random sparse signals with nonzero small entries. The stability of the generalized l ₁ greedy algorithm with respect to its parameters and the impact of noise on the recovery of Gaussian sparse signals are also studied.