Highly sparse representations from dictionaries are unique and independent of the sparseness measure

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 : The purpose of this paper is to study sparse representations of signals from a general dictionary in a Banach space. For so-called localized frames in Hilbert spaces, the canonical frame coefficients are shown to provide a near sparsest expansion for several sparseness measures. However, for frames which are not localized, this no longer holds true and sparse representations may depend strongly on the choice of the sparseness measure. A large class of admissible sparseness measures is introduced, and we give sufficient conditions for having a unique sparse representation of a signal from the dictionary w.r.t. such a sparseness measure. Moreover, 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 of the signal w.r.t. arbitrary admissible sparseness measures.
Type de document :
[Research Report] R-2003-16, 2003
Liste complète des métadonnées

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

Contributeur : Rémi Gribonval <>
Soumis le : lundi 7 février 2011 - 20:47:33
Dernière modification le : vendredi 16 novembre 2018 - 01:23:27
Document(s) archivé(s) le : dimanche 8 mai 2011 - 03:50:46


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00564038, version 1


Rémi Gribonval, Morten Nielsen. Highly sparse representations from dictionaries are unique and independent of the sparseness measure. [Research Report] R-2003-16, 2003. 〈inria-00564038〉



Consultations de la notice


Téléchargements de fichiers