Cyclic Pure Greedy Algorithms for Recovering Compressively Sampled Sparse Signals

Bob Sturm 1 Mads Christensen 1 Rémi Gribonval 2
2 METISS - Speech and sound data modeling and processing
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : 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.
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download
Contributor : Rémi Gribonval <>
Submitted on : Monday, December 17, 2012 - 5:41:45 PM
Last modification on : Friday, November 16, 2018 - 1:23:29 AM
Long-term archiving on : Sunday, December 18, 2016 - 4:01:47 AM


Files produced by the author(s)



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



Record views


Files downloads