Skip to Main content Skip to Navigation
Conference papers

BEHAVIOR OF GREEDY SPARSE REPRESENTATION ALGORITHMS ON NESTED SUPPORTS

Abstract : In this work, we study the links between the recovery proper- ties 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 sup- port 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 com- plete 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.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-00837002
Contributor : Boris Mailhé <>
Submitted on : Friday, June 21, 2013 - 6:47:33 PM
Last modification on : Tuesday, April 24, 2018 - 4:16:02 PM
Long-term archiving on: : Wednesday, April 5, 2017 - 2:47:00 AM

File

ICASSP.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00837002, version 1

Collections

Citation

Boris Mailhé, Bob Sturm, Mark Plumbley. BEHAVIOR OF GREEDY SPARSE REPRESENTATION ALGORITHMS ON NESTED SUPPORTS. ICASSP - 38th International Conference on Acoustics, Speech and Signal Processing - 2013, May 2013, Vancouver, Canada. ⟨hal-00837002⟩

Share

Metrics

Record views

391

Files downloads

285