Sample Complexity of Dictionary Learning and other Matrix Factorizations

Rémi Gribonval 1 Rodolphe Jenatton 2, 3 Francis Bach 2, 4 Martin Kleinsteuber 5 Matthias Seibert 5
1 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
2 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
Abstract : 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. The derived generalization bounds behave proportional to $\sqrt{\log(n)/n}$ w.r.t.\ the number of samples $n$ for the considered matrix factorization techniques.
Liste complète des métadonnées

https://hal.inria.fr/hal-00918142
Contributeur : Rémi Gribonval <>
Soumis le : mercredi 8 avril 2015 - 22:54:55
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : jeudi 9 juillet 2015 - 10:55:21

Fichiers

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

Identifiants

Citation

Rémi Gribonval, Rodolphe Jenatton, Francis Bach, Martin Kleinsteuber, Matthias Seibert. Sample Complexity of Dictionary Learning and other Matrix Factorizations. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2015, pp.18. 〈10.1109/TIT.2015.2424238〉. 〈hal-00918142v3〉

Partager

Métriques

Consultations de la notice

1524

Téléchargements de fichiers

531