Beyond sparsity : recovering structured representations by $\ell^1$-minimization and greedy algorithms.

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 : Finding a sparse approximation of a signal from an arbitrary dictionary is a very useful tool to solve many problems in signal processing. Several algorithms, such as Basis Pursuit (BP) and Matching Pursuits (MP, also known as greedy algorithms), have been introduced to compute sparse approximations of signals, but such algorithms a priori only provide sub-optimal solutions. In general, it is difficult to estimate how close a computed solution is from the optimal one. In a series of recent results, several authors have shown that both BP and MP can successfully recover a sparse representation of a signal provided that it is sparse enough, that is to say if its support (which indicates where are located the nonzero coefficients) is of sufficiently small size. In this paper we define identifiable structures that support signals that can be recovered exactly by L1 minimization (Basis Pursuit) and greedy algorithms. In other words, if the support of a representation belongs to an identifiable structure, then the representation will be recovered by BP and MP. In addition, we obtain that if the output of an arbitrary decomposition algorithm is supported on an identifiable structure, then one can be sure that the representation is optimal within the class of signals supported by the structure. As an application of the theoretical results, we give a detailed study of a family of multichannel dictionaries with a special structure (corresponding to the representation problem X = AS Phi^T ) often used in, e.g., under-determined source separation problems or in multichannel signal processing. An identifiable structure for such dictionaries is defined using a generalization of Tropp's Babel function which combines the coherence of the mixing matrix A with that of the time-domain dictionary Phi, and we obtain explicit structure conditions which ensure that both L1 minimization and a multichannel variant of Matching Pursuit can recover structured multichannel representations. The multichannel Matching Pursuit algorithm is described in detail and we conclude with a discussion of some implications of our results in terms of blind source separation based on sparse decompositions
Type de document :
Article dans une revue
Advances in Computational Mathematics, Springer Verlag, 2008, 28 (1), pp.23--41. 〈10.1007/s10444-005-9009-5〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger
Contributeur : Rémi Gribonval <>
Soumis le : dimanche 6 février 2011 - 22:49:59
Dernière modification le : vendredi 16 novembre 2018 - 01:24:23
Document(s) archivé(s) le : samedi 7 mai 2011 - 02:28:30


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



Rémi Gribonval, Morten Nielsen. Beyond sparsity : recovering structured representations by $\ell^1$-minimization and greedy algorithms.. Advances in Computational Mathematics, Springer Verlag, 2008, 28 (1), pp.23--41. 〈10.1007/s10444-005-9009-5〉. 〈inria-00544767〉



Consultations de la notice


Téléchargements de fichiers