Some recovery conditions for basis learning by L1-minimization

Rémi Gribonval 1 Karin Schnass 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 : Many recent works have shown that if a given signal admits a sufficiently sparse representation in a given dictionary, then this representation is recovered by several standard opti- mization algorithms, in particular the convex L1 minimization approach. Here we investigate the related problem of infering the dictionary from training data, with an approach where L1- minimization is used as a criterion to select a dictionary. We restrict our analysis to basis learning and identify necessary / sufficient / necessary and sufficient conditions on ideal (not necessarily very sparse) coefficients of the training data in an ideal basis to guarantee that the ideal basis is a strict local optimum of the L1-minimization criterion among (not necessarily orthogonal) bases of normalized vectors. We illustrate these conditions on deterministic as well as toy random models in dimension two and highlight the main challenges that remain open by this preliminary theoretical results.
Type de document :
Communication dans un congrès
3rd IEEE International Symposium on Communications, Control and Signal Processing (ISCCSP 2008), Mar 2008, St. Julians, Malta. IEEE, pp.768--773, 2008, 〈10.1109/ISCCSP.2008.4537326〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00544763
Contributeur : Rémi Gribonval <>
Soumis le : jeudi 27 janvier 2011 - 22:31:49
Dernière modification le : mercredi 16 mai 2018 - 11:23:03
Document(s) archivé(s) le : jeudi 28 avril 2011 - 02:32:39

Fichier

2008_ISCCSP_GribonvalSchnass_R...
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Rémi Gribonval, Karin Schnass. Some recovery conditions for basis learning by L1-minimization. 3rd IEEE International Symposium on Communications, Control and Signal Processing (ISCCSP 2008), Mar 2008, St. Julians, Malta. IEEE, pp.768--773, 2008, 〈10.1109/ISCCSP.2008.4537326〉. 〈inria-00544763〉

Partager

Métriques

Consultations de la notice

388

Téléchargements de fichiers

130