Cyclic Pure Greedy Algorithms for Recovering Compressively Sampled Sparse Signals

Bob L. Sturm; Mads Græsbøll Christensen; Remi Gribonval

doi:10.1109/ACSSC.2011.6190193

Cyclic Pure Greedy Algorithms for Recovering Compressively Sampled Sparse Signals

Bob L. Sturm, Mads Græsbøll Christensen, Remi Gribonval

Department of Architecture, Design and Media Technology

Research output: Contribution to journal › Conference article in Journal › Research › peer-review

11 Citations (Scopus)

374 Downloads (Pure)

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.

Original language	English
Journal	Asilomar Conference on Signals, Systems and Computers. Conference Record
Pages (from-to)	1143-1147
Number of pages	5
ISSN	1058-6393
DOIs	https://doi.org/10.1109/ACSSC.2011.6190193
Publication status	Published - 2011
Event	Asilomar Conference on Signals, Systems and computers, Nov. 6-9, 2011 - Pacific Grove, United States Duration: 6 Nov 2011 → 9 Nov 2011

Seminar

Seminar	Asilomar Conference on Signals, Systems and computers, Nov. 6-9, 2011
Country/Territory	United States
City	Pacific Grove
Period	06/11/2011 → 09/11/2011

Access to Document

10.1109/ACSSC.2011.6190193

Final versionAccepted author manuscript, 386 KB

http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6190193

AUB Link

Search for the material in Aalborg University Library's search engine

Cyclic matching pursuit for audio signal processing and recovery from compressed sensing
Sturm, B. L., Christensen, M. G. & Gribonval, R.
French Ambassador to Denmark, C. W. Obel's foundation
06/06/2011 → 24/06/2011
Project: Research

Cite this

@inproceedings{a2ca66c5ea5d470e91335093711219e6,

title = "Cyclic Pure Greedy Algorithms for Recovering Compressively Sampled Sparse Signals",

abstract = "The pure greedy algorithmsmatching 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 improvedwhile 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.",

author = "Sturm, {Bob L.} and Christensen, {Mads Gr{\ae}sb{\o}ll} and Remi Gribonval",

year = "2011",

doi = "10.1109/ACSSC.2011.6190193",

language = "English",

pages = "1143--1147",

journal = "Asilomar Conference on Signals, Systems and Computers. Conference Record",

issn = "1058-6393",

publisher = "I E E E Computer Society",

note = "Asilomar Conference on Signals, Systems and computers, Nov. 6-9, 2011 ; Conference date: 06-11-2011 Through 09-11-2011",

}

TY - GEN

T1 - Cyclic Pure Greedy Algorithms for Recovering Compressively Sampled Sparse Signals

AU - Sturm, Bob L.

AU - Christensen, Mads Græsbøll

AU - Gribonval, Remi

PY - 2011

Y1 - 2011

N2 - The pure greedy algorithmsmatching 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 improvedwhile 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.

AB - The pure greedy algorithmsmatching 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 improvedwhile 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.

U2 - 10.1109/ACSSC.2011.6190193

DO - 10.1109/ACSSC.2011.6190193

M3 - Conference article in Journal

SN - 1058-6393

SP - 1143

EP - 1147

JO - Asilomar Conference on Signals, Systems and Computers. Conference Record

JF - Asilomar Conference on Signals, Systems and Computers. Conference Record

T2 - Asilomar Conference on Signals, Systems and computers, Nov. 6-9, 2011

Y2 - 6 November 2011 through 9 November 2011

ER -

Cyclic Pure Greedy Algorithms for Recovering Compressively Sampled Sparse Signals

Abstract

Seminar

Access to Document

AUB Link

Fingerprint

Projects

Cyclic matching pursuit for audio signal processing and recovery from compressed sensing

Cite this