Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1109/ICASSP.2013.6638758 | Acoustics, Speech and Signal Processing |
Keywords | DocType | ISSN |
greedy algorithms,iterative methods,signal processing,omp,tropp proof,general mp class,greedy sparse representation algorithms,nested supports,orthogonal matching pursuit,s-sparse signals,basis pursuit,compressed sensing,performance analysis and bounds,sparsity | Conference | 1520-6149 |
Citations | PageRank | References |
3 | 0.55 | 4 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Boris Mailhé | 1 | 103 | 7.22 |
Bob L. Sturm | 2 | 241 | 29.88 |
M. D. Plumbley | 3 | 1915 | 202.38 |