Sample complexity of Bayesian optimal dictionary learning

We consider a learning problem of identifying a dictionary matrix D ∈ R^M×N from a sample set of M dimensional vectors Y ∈ R^M×P = N^-1/2DX ∈ R^M×P, where X ∈ R^N×p is a sparse matrix in which the density of non-zero entries is 0 <; ρ <; 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 α = M/N > ρ is satisfied in the limit of N → ∞. Our analysis also implies that the posterior distribution given Y is condensed only at the correct dictionary D when the compression rate α is greater than a certain critical value α_M(p). This suggests that belief propagation may allow us to learn D with a low computational complexity using O(N) samples.