A Clustering Approach to Learning Sparsely Used Overcomplete Dictionaries
Alekh Agarwal, Animashree Anandkumar, Praneeth Netrapalli · IEEE Transactions on Information Theory · 2016
We consider the problem of learning over complete dictionaries in the context of sparse coding, where each sample selects a sparse subset of dictionary elements. Our main result is a strategy to approximately recover the unknown dictionary using an efficient algorithm. Our algorithm is a clustering-style procedure, where each cluster is used to estimate a dictionary element. The resulting solution can often be further cleaned up to obtain a high accuracy estimate, and we provide one simple scenario where ℓ1-regularized regression can be used for such a second stage.