Alternating minimization for dictionary learning: Local Convergence
  Guarantees
  We present theoretical guarantees for an alternating minimization algorithm
for the dictionary learning/sparse coding problem. The dictionary learning
problem is to factorize vector samples $y^{1},y^{2},\ldots, y^{n}$ into an
appropriate basis (dictionary) $A^*$ and sparse vectors $x^{1*},\ldots,x^{n*}$.
Our algorithm is a simple alternating minimization procedure that switches
between $\ell_1$ minimization and gradient descent in alternate steps.
Dictionary learning and specifically alternating minimization algorithms for
dictionary learning are well studied both theoretically and empirically.
However, in contrast to previous theoretical analyses for this problem, we
replace a condition on the operator norm (that is, the largest magnitude
singular value) of the true underlying dictionary $A^*$ with a condition on the
matrix infinity norm (that is, the largest magnitude term). Our guarantees are
under a reasonable generative model that allows for dictionaries with growing
operator norms, and can handle an arbitrary level of overcompleteness, while
having sparsity that is information theoretically optimal. We also establish
upper bounds on the sample complexity of our algorithm.
