Behavior of greedy sparse representation algorithms on nested supports

In this work, we study the links between the recovery properties of sparse signals for Orthogonal Matching Pursuit (OMP) and the whole General MP class over nested supports. We show that the optimality of those algorithms is not locally nested: there is a dictionary and supports I and J with J inclu...

Full description

Saved in:
Bibliographic Details
Main Authors: Mailhe, Boris, Sturm, Bob, Plumbley, Mark D.
Format: Conference Proceeding
Language:English
Subjects:
Approximation methods
Basis Pursuit
Compressed sensing
Dictionaries
Greedy algorithms
Matching pursuit algorithms
Orthogonal Matching Pursuit
Performance analysis and bounds
Signal processing algorithms
Sparks
Sparsity
Vectors
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this work, we study the links between the recovery properties of sparse signals for Orthogonal Matching Pursuit (OMP) and the whole General MP class over nested supports. We show that the optimality of those algorithms is not locally nested: there is a dictionary and supports I and J with J included in I such that OMP will recover all signals of support I, but not all signals of support J. We also show that the optimality of OMP is globally nested: if OMP can recover all s-sparse signals, then it can recover all s'-sparse signals with s' smaller than s. We also provide a tighter version of Donoho and Elad's spark theorem, which allows us to complete Tropp's proof that sparse representation algorithms can only be optimal for all s-sparse signals if s is strictly lower than half the spark of the dictionary.
ISSN:1520-6149
2379-190X
DOI:10.1109/ICASSP.2013.6638758