Abstract

 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 , . . . , y n into an appropriate basis (dictionary) and sparse vectors  . Our algorithm is a simple alternating minimization procedure that switches between 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 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.Erratum, August 7, 2019: An earlier version of this paper appeared in NIPS 2017 which hadan erroneous claim about convergence guarantees with random initialization. The main result –Theorem 3 – has been corrected by adding an assumption about the initialization (Assumption B1).