Sample Complexity of Dictionary Learning and other Matrix Factorizations - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2013

Sample Complexity of Dictionary Learning and other Matrix Factorizations

Résumé

Many modern tools in machine learning and signal processing, such as sparse dictionary learning, principal component analysis (PCA), non-negative matrix factorization (NMF), $K$-means clustering, etc., rely on the factorization of a matrix obtained by concatenating high-dimensional vectors from a training collection. While the idealized task would be to optimize the expected quality of the factors over the underlying distribution of training vectors, it is achieved in practice by minimizing an empirical average over the considered collection. The focus of this paper is to provide sample complexity estimates to uniformly control how much the empirical average deviates from the expected cost function. Standard arguments imply that the performance of the empirical predictor also exhibit such guarantees. The level of genericity of the approach encompasses several possible constraints on the factors (tensor product structure, shift-invariance, sparsity \ldots), thus providing a unified perspective on the sample complexity of several widely used matrix factorization schemes.
Fichier principal
Vignette du fichier
sample_complexity_matrix_factorization.pdf (369.35 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00918142 , version 1 (12-12-2013)
hal-00918142 , version 2 (26-11-2014)
hal-00918142 , version 3 (08-04-2015)

Identifiants

Citer

Rémi Gribonval, Rodolphe Jenatton, Francis Bach, Martin Kleinsteuber, Matthias Seibert. Sample Complexity of Dictionary Learning and other Matrix Factorizations. 2013. ⟨hal-00918142v1⟩
1195 Consultations
939 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More