Learning Sparsely Used Overcomplete Dictionaries

Alekh Agarwal
Microsoft Research

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].

Back to Stochastic Gradient Methods