# Sample Complexity of Dictionary Learning and other Matrix Factorizations

arXiv: https://arxiv.org/abs/1312.3790 · HTML: https://mlsanity.com/paper/1312.3790/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Dec 2013.

## Built on by (most cited first, 8 of 8)

- [Generalization Error Bounds for Iterative Recovery Algorithms Unfolded as Neural Networks](https://mlsanity.com/paper/2112.04364/) (2021)
- [Optimal Regularization for a Data Source](https://mlsanity.com/paper/2212.13597/) (2022)
- [Learning sparsity-promoting regularizers for linear inverse problems](https://mlsanity.com/paper/2412.16031/) (2024)
- [A Forward Backward Greedy approach for Sparse Multiscale Learning](https://mlsanity.com/paper/2102.07068/) (2021)
- [Learning Low-dimensional Latent Dynamics from High-dimensional Observations: Non-asymptotics and Lower Bounds](https://mlsanity.com/paper/2405.06089/) (2024)
- [Optimal Regularization Under Uncertainty: Distributional Robustness and Convexity Constraints](https://mlsanity.com/paper/2510.03464/) (2025)
- [Estimation of Models with Limited Data by Leveraging Shared Structure](https://mlsanity.com/paper/2310.02864/) (2023)
- [Multi-Dictionary Learning for Low Rank Sparse Coding](https://mlsanity.com/paper/2509.10033/) (2025)

## Abstract (arXiv)

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