| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Cited literature [12 references]
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
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)