Learning Sparsely Used Overcomplete Dictionaries

• Activity Number: 542
• Type: Invited
• Date/Time: Wednesday, August 6, 2014 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Computing
• Author(s): Alekh Agarwal*+ and Animashree Anandkumar and Prateek Jain and Praneeth Netrapalli and Rashish Tandon
• Companies: Microsoft and University of California, Irvine and Microsoft and University of Texas at Austin and University of Texas at Austin
• Keywords: Dictionary learning ; Sparse coding ; Alternating minimization ; Sparse estimation

Abstract

We consider the problem of learning sparsely used overcomplete dictionaries, where each observation consists of a sparse combination of the mutually incoherent dictionary elements. Our method consists of a clustering-based initialization step that gives a reasonably accurate initial estimate of the true dictionary. This estimate is further improved 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.

[Joint work with Anima Anandkumar, Prateek Jain, Praneeth Netrapalli and Rashish Tandon]