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 a NP-hard problem. Despite 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 :
Article dans une revue
Signal Processing, Elsevier, 2006, special issue on Sparse Approximations in Signal and Image Processing, 86 (3), pp.496--510. 〈10.1016/j.sigpro.2005.05.026〉
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-00544941
Contributeur : Rémi Gribonval <>
Soumis le : mardi 8 février 2011 - 21:56:43
Dernière modification le : mercredi 16 mai 2018 - 11:23:03
Document(s) archivé(s) le : lundi 9 mai 2011 - 02:52:05

Fichier

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

Identifiants

Citation

Rémi Gribonval, Rosa Maria Figueras I Ventura, Pierre Vandergheynst. A simple test to check the optimality of sparse signal approximations. Signal Processing, Elsevier, 2006, special issue on Sparse Approximations in Signal and Image Processing, 86 (3), pp.496--510. 〈10.1016/j.sigpro.2005.05.026〉. 〈inria-00544941〉

Partager

Métriques

Consultations de la notice

275

Téléchargements de fichiers

189