On The Sample Complexity Of Sparse Dictionary Learning

Matthias Seibert 1 Martin Kleinsteuber 1 Rémi Gribonval 2 Rodolphe Jenatton 3, 4 Francis Bach 3, 5
1 TUM - Technical University of Munich
2 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio
Inria Rennes – Bretagne Atlantique , IRISA-D5 - SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE
3 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
4 CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique
5 LIENS - Laboratoire d'informatique de l'école normale supérieure
Abstract : In the synthesis model signals are represented as a sparse combinations of atoms from a dictionary. Dictionary learning describes the acquisition process of the underlying dictionary for a given set of training samples. While ideally this would be achieved by optimizing the expectation of the factors over the underlying distribution of the training data, in practice the necessary information about the distribution is not available. Therefore, in real world applications it is achieved by minimizing an empirical average over the available samples. The main goal of this paper is to provide a sample complexity estimate that controls to what extent the empirical average deviates from the cost function. This estimate then provides a suitable estimate to the accuracy of the representation of the learned dictionary. The presented approach exemplifies the general results proposed by the authors in [1] and gives more concrete bounds of the sample complexity of dictionary learning. We cover a variety of sparsity measures employed in the learning procedure.
Keywords : Dictionary learning sample complexity sparse coding
Type de document :
Communication dans un congrès
SSP 2014 - IEEE Workshop on Statistical Signal Processing, Jun 2014, Jupiters, Gold Coast, Australia. IEEE, 2014, 〈10.1109/SSP.2014.6884621 〉
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-00990684
Contributeur : Rémi Gribonval <>
Soumis le : mardi 13 mai 2014 - 18:44:40
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:50:32

Fichier

sample_complexity.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | IRISA | X | PARISTECH | X-CMAP | CMAP | ENS-PARIS | IRISA-D5 | PSL | UR1-UFR-ISTIC | UNIV-RENNES | X-DEP-MATHA

Citation

Matthias Seibert, Martin Kleinsteuber, Rémi Gribonval, Rodolphe Jenatton, Francis Bach. On The Sample Complexity Of Sparse Dictionary Learning. SSP 2014 - IEEE Workshop on Statistical Signal Processing, Jun 2014, Jupiters, Gold Coast, Australia. IEEE, 2014, 〈10.1109/SSP.2014.6884621 〉. 〈hal-00990684〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

1621

Téléchargements de fichiers

218

Contact


archive-ouverte@inria.fr