Learning Sparsely Used Overcomplete Dictionaries

Abstract

We consider the problem of learning sparsely used overcomplete dictionaries, where each observa-tion 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 follow-ing alternating steps: 1) estimation of the dictionary coefficients for each observation through ℓ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.