Cyclic Pure Greedy Algorithms for Recovering Compressively Sampled Sparse Signals

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

Publikation: Bidrag til tidsskriftKonferenceartikel i tidsskriftForskningpeer review

9 Citationer (Scopus)
254 Downloads (Pure)

Resumé

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.
OriginalsprogEngelsk
TidsskriftAsilomar Conference on Signals, Systems and Computers. Conference Record
Sider (fra-til)1143-1147
Antal sider5
ISSN1058-6393
DOI
StatusUdgivet - 2011
BegivenhedAsilomar Conference on Signals, Systems and computers, Nov. 6-9, 2011 - Pacific Grove, USA
Varighed: 6 nov. 20119 nov. 2011

Seminar

SeminarAsilomar Conference on Signals, Systems and computers, Nov. 6-9, 2011
LandUSA
ByPacific Grove
Periode06/11/201109/11/2011

Fingerprint

Recovery
Inverse problems

Citer dette

@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",

}

Cyclic Pure Greedy Algorithms for Recovering Compressively Sampled Sparse Signals. / Sturm, Bob L.; Christensen, Mads Græsbøll; Gribonval, Remi.

I: Asilomar Conference on Signals, Systems and Computers. Conference Record, 2011, s. 1143-1147.

Publikation: Bidrag til tidsskriftKonferenceartikel i tidsskriftForskningpeer review

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

SP - 1143

EP - 1147

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

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

SN - 1058-6393

ER -