Skip to Main content Skip to Navigation
Conference papers

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

Cited literature [18 references]  Display  Hide  Download
Contributor : Rémi Gribonval Connect in order to contact the contributor
Submitted on : Sunday, February 20, 2011 - 9:46:31 PM
Last modification on : Friday, February 4, 2022 - 3:22:18 AM
Long-term archiving on: : Saturday, May 21, 2011 - 2:46:00 AM


Files produced by the author(s)



Rémi Gribonval, Morten Nielsen. On the strong uniqueness of highly sparse expansions from redundant dictionaries. Independent Component Analysis and Blind Signal Separation, Fifth International Conference, ICA 2004, Sep 2004, Granada, Spain. pp.201-208, ⟨10.1007/978-3-540-30110-3_26⟩. ⟨inria-00567341⟩



Record views


Files downloads