NOODL: Provable Online Dictionary Learning and Sparse Coding
  We consider the dictionary learning problem, where the aim is to model the
given data as a linear combination of a few columns of a matrix known as a
dictionary, where the sparse weights forming the linear combination are known
as coefficients. Since the dictionary and coefficients, parameterizing the
linear model are unknown, the corresponding optimization is inherently
non-convex. This was a major challenge until recently, when provable algorithms
for dictionary learning were proposed. Yet, these provide guarantees only on
the recovery of the dictionary, without explicit recovery guarantees on the
coefficients. Moreover, any estimation error in the dictionary adversely
impacts the ability to successfully localize and estimate the coefficients.
This potentially limits the utility of existing provable dictionary learning
methods in applications where coefficient recovery is of interest. To this end,
we develop NOODL: a simple Neurally plausible alternating Optimization-based
Online Dictionary Learning algorithm, which recovers both the dictionary and
coefficients exactly at a geometric rate, when initialized appropriately. Our
algorithm, NOODL, is also scalable and amenable for large scale distributed
implementations in neural architectures, by which we mean that it only involves
simple linear and non-linear operations. Finally, we corroborate these
theoretical results via experimental evaluation of the proposed algorithm with
the current state-of-the-art techniques.
  Keywords: dictionary learning, provable dictionary learning, online
dictionary learning, non-convex, sparse coding, support recovery, iterative
hard thresholding, matrix factorization, neural architectures, neural networks,
noodl, sparse representations, sparse signal processing.
