Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization

By Alekh Agarwal, Anima Anandkumar, Prateek Jain, Praneeth Netrapalli. 2013

178 citations recorded by the source corpus.

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 $\ell_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 $\order{1/s^2}$, where $s$ is the sparsity level in each sample and the dictionary satisfies RIP. 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.

Subfields: Artificial Intelligence, Computational Mechanics, Representation & Self-Supervised Learning, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Representation & Self-Supervised Learning

In Signal Processing

Citations in the corpus

Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, methodology): “[10] provides a neurally-plausible algorithm for learning sparse coding along with other works using alternative minimization [1, 2, 37, 56, 59].”
Sparse Modeling for Image and Vision Processing (2014, result): “[2011], and recently it has been shown that under additional assumptions, a good initializer could be found so that the previous type of local consistency results can be applied [Agarwal et al., 2013].”
Generalized Low Rank Models (2014, methodology): “Recently, there has been a resurgence of interest in methods based on alternating minimization, as numerous authors have shown that alternating minimization (suitably initialized, and under a few technical assumptions) provably converges to the global minimum for a range of problems including matrix”
Simple, Efficient, and Neural Algorithms for Sparse Coding (2015, methodology): “Arora et al. (2014) and Agarwal et al. (2013, 2014) independently gave algorithms in the overcomplete case assuming that A ∗ is µ -incoherent (which we deﬁne in the next section).”
Phase Retrieval Using Alternating Minimization (2013, background): “We would like to stress that not only does a natural variant of our proposed algorithm have rigorous theoretical guarantees, it also is eﬀective practically as each of its iterations is fast, has a closed form solution and does not require SVD computation.”
New Algorithms for Learning Incoherent and Overcomplete Dictionaries (2013, methodology): “Their second [1] gives an algorithm –a version of alternating minimization– that converges to the correct dictionary given a good initial dictionary (such a good initialization can only be found using [2] in special cases, or more generally using this paper).”
Non-convex Optimization for Machine Learning (2017, background): “Some notable works in this area include [Agarwal et al., 2016, Arora et al., 2014, Gribonval et al., 2015, Spielman et al., 2012].”