Cyclic Pure Greedy Algorithms for Recovering Compressively Sampled Sparse Signals

Bob L. Sturm (1) , Mads Græsbøll Christensen (1) , Rémi Gribonval (2)

1 Department of Architecture and Design [Aalborg]
2 METISS - Speech and sound data modeling and processing

The pure greedy algorithms matching pursuit (MP) and complementary MP (CompMP) are extremely computationally simple, but can perform poorly in solving the linear inverse problems posed by the recovery of compressively sampled sparse signals. We show that by applying a cyclic minimization principle, the performance of both are significantly improved while remaining computationally simple. Our simulations show that while MP and CompMP may not be competitive with state-of-the-art recovery algorithms, their cyclic variations are. We discuss ways in which their complexity can be further reduced, but our simulations show these can hurt recovery performance. Finally, we derive the exact recovery condition of CompMP and both cyclic algorithms.

Domaines: Traitement du signal et de l'image [eess.SP]; Traitement du signal et de l'image [eess.SP]

Bob L. Sturm, Mads Græsbøll Christensen, Rémi Gribonval. Cyclic Pure Greedy Algorithms for Recovering Compressively Sampled Sparse Signals. ASILOMAR 2011 - Forty Fifth Asilomar Conference on Signals, Systems and Computers, Nov 2011, Asilomar, United States. pp.1143--1147, ⟨10.1109/ACSSC.2011.6190193⟩. ⟨hal-00766199⟩