Sample Complexity of Bayesian Optimal Dictionary Learning

2013/01/26 by Sakata, Ayaka, Kabashima, Yoshiyuki
#Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Statistical Mechanics (cond-mat.stat-mech)

paper · doi:10.48550/arxiv.1301.6199

Abstract

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 0rho 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.

Related

• Performance Limits of Dictionary Learning for Sparse Coding
• More Algorithms for Provable Dictionary Learning
• On the Minimax Risk of Dictionary Learning
• Approximate Guarantees for Dictionary Learning
• Dictionary Learning with Almost Sure Error Constraints