Skip to Main content Skip to Navigation
Reports

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.
Complete list of metadata

Cited literature [42 references]  Display  Hide  Download

https://hal.inria.fr/inria-00564038
Contributor : Rémi Gribonval <>
Submitted on : Monday, February 7, 2011 - 8:47:33 PM
Last modification on : Tuesday, June 15, 2021 - 4:26:38 PM
Long-term archiving on: : Sunday, May 8, 2011 - 3:50:46 AM

Files

R-2003-16.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00564038, version 1

Citation

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⟩

Share