Learning Sparsely Used Overcomplete Dictionaries
Abstract
We consider the problem of learning sparsely used overcomplete dictionaries, where each observation is a sparse combination of elements from an unknown overcomplete dictionary. We establish exact recovery when the dictionary elements are mutually incoherent. Our method consists of a clustering-based initialization step, which provides an approximate estimate of the true dictionary with guaranteed accuracy. This estimate is then refined via an iterative algorithm with the following alternating steps: 1) estimation of the dictionary coefficients for each observation through \ell_1 minimization, given the dictionary estimate, and 2) estimation of the dictionary elements through least squares, given the coefficient estimates. We establish that, under a set of sufficient conditions, our method converges at a linear rate to the true dictionary as well as the true coefficients for each observation.
Cite
Text
Agarwal et al. "Learning Sparsely Used Overcomplete Dictionaries." Annual Conference on Computational Learning Theory, 2014.Markdown
[Agarwal et al. "Learning Sparsely Used Overcomplete Dictionaries." Annual Conference on Computational Learning Theory, 2014.](https://mlanthology.org/colt/2014/agarwal2014colt-learning/)BibTeX
@inproceedings{agarwal2014colt-learning,
title = {{Learning Sparsely Used Overcomplete Dictionaries}},
author = {Agarwal, Alekh and Anandkumar, Animashree and Jain, Prateek and Netrapalli, Praneeth and Tandon, Rashish},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2014},
pages = {123-137},
url = {https://mlanthology.org/colt/2014/agarwal2014colt-learning/}
}