Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 8, 2016 | Published + Submitted
Journal Article Open

Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization


We consider the problem of sparse coding, where each sample consists of a sparse linear combination of a set of dictionary atoms, and the task is to learn both the dictionary elements and the mixing coefficients. Alternating minimization is a popular heuristic for sparse coding, where the dictionary and the coefficients are estimated in alternate steps, keeping the other fixed. Typically, the coefficients are estimated via ℓ_1 minimization, keeping the dictionary fixed, and the dictionary is estimated through least squares, keeping the coefficients fixed. In this paper, we establish local linear convergence for this variant of alternating minimization and establish that the basin of attraction for the global optimum (corresponding to the true dictionary and the coefficients) is O(1/s^2), where s is the sparsity level in each sample and the dictionary satisfies restricted isometry property. Combined with the recent results of approximate dictionary estimation, this yields provable guarantees for exact recovery of both the dictionary elements and the coefficients, when the dictionary elements are incoherent.

Additional Information

© 2016 Society for Industrial and Applied Mathematics. Received by the editors July 29, 2014; accepted for publication (in revised form) September 12, 2016; published electronically December 8, 2016. Part of this work was done when P. Netrapalli was a student at UT Austin and A. Anandkumar and P. Netrapalli were visiting Microsoft Research. An extended abstract containing an earlier version of these results appears in Proceedings of COLT 2014. The second author is supported in part by Microsoft Faculty Fellowship, Google Faculty Award, NSF Career Award CCF-1254106, ONR Award N00014-14-1-0665, and AFOSR YIP FA9550-15-1-0221.

Attached Files

Submitted - 1310.7991.pdf

Published - 140979861.pdf


Files (845.2 kB)
Name Size Download all
296.9 kB Preview Download
548.3 kB Preview Download

Additional details

August 19, 2023
August 19, 2023