A simple test to check the optimality of sparse signal approximations

Rémi Gribonval 1 Rosa Maria Figueras I Ventura 2 Pierre Vandergheynst 2
1 METISS - Speech and sound data modeling and processing
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : Approximating a signal or an image with a sparse linear expansion from an overcomplete dictionary of atoms is an extremely useful tool to solve many signal processing problems. Finding the sparsest approximation of a signal from an arbitrary dictionary is an NP-hard problem. Despite of this, several algorithms have been proposed that provide sub-optimal solutions. However, it is generally difficult to know how close the computed solution is to being ``optimal'', and whether another algorithm could provide a better result. In this paper we provide a simple test to check whether the output of a sparse approximation algorithm is nearly optimal, in the sense that no significantly different linear expansion from the dictionary can provide both a smaller approximation error and a better sparsity. As a by-product of our theorems, we obtain results on the identifiability of sparse overcomplete models in the presence of noise, for a fairly large class of sparse priors.
Type de document :
Communication dans un congrès
Acoustics, Speech and Signal Processing, 2005. ICASSP 2005. IEEE International Conference on, Mar 2005, Philadelphia, PA, United States. IEEE, 5, pp.V/717 -- V/720, 2005, 〈10.1109/ICASSP.2005.1416404〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00564503
Contributeur : Rémi Gribonval <>
Soumis le : mercredi 9 février 2011 - 09:08:15
Dernière modification le : mercredi 16 mai 2018 - 11:23:03
Document(s) archivé(s) le : mardi 10 mai 2011 - 02:55:00

Fichier

2005_ICASSP_GribonvalEtAl_Simp...
Accord explicite pour ce dépôt

Identifiants

Citation

Rémi Gribonval, Rosa Maria Figueras I Ventura, Pierre Vandergheynst. A simple test to check the optimality of sparse signal approximations. Acoustics, Speech and Signal Processing, 2005. ICASSP 2005. IEEE International Conference on, Mar 2005, Philadelphia, PA, United States. IEEE, 5, pp.V/717 -- V/720, 2005, 〈10.1109/ICASSP.2005.1416404〉. 〈inria-00564503〉

Partager

Métriques

Consultations de la notice

355

Téléchargements de fichiers

267