# On the strong uniqueness of highly sparse expansions from redundant dictionaries

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.
Document type :
Conference papers
Domain :

Cited literature [18 references]

https://hal.inria.fr/inria-00567341
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

### File

2004_ICA_GribonvalNielsen.pdf
Files produced by the author(s)

### Citation

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