On the strong uniqueness of highly sparse expansions from redundant dictionaries

Rémi Gribonval 1 Morten Nielsen 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 : A series of recent results shows that if a signal admits a sufficiently sparse representation (in terms of the number of nonzero coefficients) in an ``incoherent'' dictionary, this solution is unique and can be recovered as the unique solution of a linear programming problem. We generalize these results to a large class of sparsity measures which includes the ell^p-sparsity measures for 0 \le p \le 1. We give sufficient conditions on a signal such that the simple solution of a linear programming problem simultaneously solves all the non-convex (and generally hard combinatorial) problems of sparsest representation w.r.t. arbitrary admissible sparsity measures. Our results should have a practical impact on source separation methods based on sparse decompositions, since they indicate that a large class of sparse priors can be efficiently replaced with a Laplacian prior without changing the resulting solution.
Type de document :
Communication dans un congrès
Puntonet, Carlos G. and Prieto, Alberto. Independent Component Analysis and Blind Signal Separation, Fifth International Conference, ICA 2004, Sep 2004, Granada, Spain. Springer-Verlag, 3195, pp.201-208, 2004, LNCS. 〈10.1007/978-3-540-30110-3_26〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00567341
Contributeur : Rémi Gribonval <>
Soumis le : dimanche 20 février 2011 - 21:46:31
Dernière modification le : jeudi 11 janvier 2018 - 06:20:09
Document(s) archivé(s) le : samedi 21 mai 2011 - 02:46:00

Fichier

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

Identifiants

Collections

Citation

Rémi Gribonval, Morten Nielsen. On the strong uniqueness of highly sparse expansions from redundant dictionaries. Puntonet, Carlos G. and Prieto, Alberto. Independent Component Analysis and Blind Signal Separation, Fifth International Conference, ICA 2004, Sep 2004, Granada, Spain. Springer-Verlag, 3195, pp.201-208, 2004, LNCS. 〈10.1007/978-3-540-30110-3_26〉. 〈inria-00567341〉

Partager

Métriques

Consultations de la notice

359

Téléchargements de fichiers

109