Sample Complexity of Dictionary Learning and Other Matrix Factorizations

DOI10.1109/TIT.2015.2424238MaRDI QIDQ2978588zbMATH OpenOpenAlexWikidataFDO

Authors Rodolphe Jenatton, Francis Bach, Matthias Seibert, Rémi Gribonval, Martin Kleinsteuber

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.3790

Mathematics Subject Classification ID

General nonlinear regression (62J02) Learning and adaptive systems in artificial intelligence (68T05) Inequalities; stochastic orderings (60E15)

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 $sqrtlog(n)/n$ w.r.t. the number of samples $n$ for the considered matrix factorization techniques.

Cited in

(20)

• On statistical learning of simplices: unmixing problem revisited
• Convergence radius and sample complexity of ITKM algorithms for dictionary learning
• Learning semidefinite regularizers
• Dimensionality-dependent generalization bounds for \(k\)-dimensional coding schemes
• Alternating proximal regularized dictionary learning
• Multilinear compressive sensing and an application to convolutional linear networks
• Provably accurate double-sparse coding
• On the Purity and Entropy of Mixed Gaussian States
• Learning sparsity-promoting regularizers for linear inverse problems
• Optimal regularization for a data source
• Adaptive geometric multiscale approximations for intrinsically low-dimensional data
• Generalization Error in Deep Learning
• Customized dictionary learning for subdatasets with fine granularity
• Local identifiability of \(\ell_1\)-minimization dictionary learning: a sufficient and almost necessary condition
• Reprint of: A forward-backward greedy approach for sparse multiscale learning
• Compressive sensing and neural networks from a statistical learning perspective
• Minimax Lower Bounds on Dictionary Learning for Tensor Data
• Tensor Regression Using Low-Rank and Sparse Tucker Decompositions
• Structured dictionary learning of rating migration matrices for credit risk modeling
• A forward-backward greedy approach for sparse multiscale learning

This page was built for publication: Sample Complexity of Dictionary Learning and Other Matrix Factorizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2978588)