A Caltech Library Service

Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization

Agarwal, Alekh and Anandkumar, Animashree and Jain, Prateek and Netrapalli, Praneeth (2016) Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization. SIAM Journal of Optimization, 26 (4). pp. 2775-2799. ISSN 1052-6234.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
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.
Funding AgencyGrant Number
Microsoft ResearchUNSPECIFIED
Office of Naval Research (ONR)N00014-14-1-0665
Air Force Office of Scientific Research (AFOSR)FA9550-15-1-0221
Subject Keywords:dictionary learning, sparse coding, alternating minimization, RIP, incoherence, lasso
Issue or Number:4
Classification Code:AMS Subject Headings: 90C26, 68T10
Record Number:CaltechAUTHORS:20170927-090108498
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:81869
Deposited By: Tony Diaz
Deposited On:27 Sep 2017 16:19
Last Modified:03 Oct 2019 18:48

Repository Staff Only: item control page