# Sample Complexity of Bayesian Optimal Dictionary Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jan 2013.

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

- [Statistical limits of dictionary learning: random matrix theory and the spectral replica method](https://mlsanity.com/paper/2109.06610/) (2021)
- [On the phase diagram of extensive-rank symmetric matrix denoising beyond rotational invariance](https://mlsanity.com/paper/2411.01974/) (2024)

## Abstract (arXiv)

We consider a learning problem of identifying a dictionary matrix D (M times N dimension) from a sample set of M dimensional vectors Y = N^{-1/2} DX, where X is a sparse matrix (N times P dimension) in which the density of non-zero entries is 0<rho< 1. In particular, we focus on the minimum sample size P_c (sample complexity) necessary for perfectly identifying D of the optimal learning scheme when D and X are independently generated from certain distributions. By using the replica method of statistical mechanics, we show that P_c=O(N) holds as long as alpha = M/N >rho is satisfied in the limit of N to infinity. Our analysis also implies that the posterior distribution given Y is condensed only at the correct dictionary D when the compression rate alpha is greater than a certain critical value alpha_M(rho). This suggests that belief propagation may allow us to learn D with a low computational complexity using O(N) samples.