BEHAVIOR OF GREEDY SPARSE REPRESENTATION ALGORITHMS ON NESTED SUPPORTS

Boris Mailhé 1 Bob Sturm 2 Mark Plumbley 1
1 Centre for Digital Music, Queen Mary University of London
Centre for Digital Music
2 Department of Architecture and Design [Aalborg]
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.
Type de document :
Communication dans un congrès
ICASSP - 38th International Conference on Acoustics, Speech and Signal Processing - 2013, May 2013, Vancouver, Canada. IEEE, 2013
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-00837002
Contributeur : Boris Mailhé <>
Soumis le : vendredi 21 juin 2013 - 18:47:33
Dernière modification le : mardi 24 avril 2018 - 16:16:02
Document(s) archivé(s) le : mercredi 5 avril 2017 - 02:47:00

Fichier

ICASSP.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. IEEE, 2013. 〈hal-00837002〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

337

Téléchargements de fichiers

122

Contact


archive-ouverte@inria.fr