New Algorithms for Learning Incoherent and Overcomplete Dictionaries

By Sanjeev Arora, Rong Ge, Ankur Moitra. 2013

212 citations recorded by the source corpus.

In sparse recovery we are given a matrix $A$ (the dictionary) and a vector of the form $A X$ where $X$ is sparse, and the goal is to recover $X$. This is a central notion in signal processing, statistics and machine learning. But in applications such as sparse coding, edge detection, compression and super resolution, the dictionary $A$ is unknown and has to be learned from random examples of the form $Y = AX$ where $X$ is drawn from an appropriate distribution --- this is the dictionary learning problem. In most settings, $A$ is overcomplete: it has more columns than rows. This paper presents a polynomial-time algorithm for learning overcomplete dictionaries; the only previously known algorithm with provable guarantees is the recent work of Spielman, Wang and Wright who gave an algorithm for the full-rank case, which is rarely the case in applications. Our algorithm applies to incoherent dictionaries which have been a central object of study since they were introduced in seminal work of Donoho and Huo. In particular, a dictionary is $\mu$-incoherent if each pair of columns has inner product at most $\mu / \sqrt{n}$. The algorithm makes natural stochastic assumptions about the unknown sparse vector $X$, which can contain $k \leq c \min(\sqrt{n}/\mu \log n, m^{1/2 -\eta})$ non-zero entries (for any $\eta > 0$). This is close to the best $k$ allowable by the best sparse recovery algorithms even if one knows the dictionary $A$ exactly. Moreover, both the running time and sample complexity depend on $\log 1/\epsilon$, where $\epsilon$ is the target accuracy, and so our algorithms converge very quickly to the true dictionary. Our algorithm can also tolerate substantial amounts of noise provided it is incoherent with respect to the dictionary (e.g., Gaussian). In the noisy setting, our running time and sample complexity depend polynomially on $1/\epsilon$, and this is necessary.

Subfields: Biomedical Engineering, Computational Mechanics, Statistical Learning Theory, Algorithms & Complexity, 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 Biomedical Engineering

In Computational Mechanics

In Statistical Learning Theory

In Algorithms & Complexity

In Signal Processing

Citations in the corpus

Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, background): “There are many existing theoretical works studying algorithm for sparse coding [9, 17, 43, 47, 54, 68, 85, 91, 94], however, these algorithms share little similarity to training a neural network.”
Example Selection For Dictionary Learning (2014, methodology): “The algorithm in Arora et al. (2013) also makes use of a sophisticated example grouping procedure to provably recover dictionaries.”
Efficient Representations for Lifelong Learning and Autoencoding (2014, background): “It would be interesting to see whether an analog of the anchor-set assumption could be applied to dictionary learning problems such as in [3].”
Provable Bounds for Learning Some Deep Representations (2013, background): “Furthermore, learning even a a single layer sparse denoising autoencoder seems much harder than learning sparse-used overcomplete dictionaries —which correspond to a single hidden layer with linear operations— and even for this much simpler problem there were no provable bounds at all until the very”
Score Function Features for Discriminative Learning: Matrix and Tensor Framework (2014, background): “, 2014a,c), sparse coding (Agarwal et al., 2014; Arora et al., 2014), and deep representations (Arora et al.”
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].”
Exact Recovery of Sparsely Used Overcomplete Dictionaries (2013, result): “Finally, concurrently with our work, an approximate recovery result with a similar procedure as our initialization step was recently announced by Arora et al. [7].”
Simple, Efficient, and Neural Algorithms for Sparse Coding (2015, background): “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).”
Variance Reduction for Faster Non-Convex Optimization (2016, methodology): “For some models, probabilistic and other assumptions on the input can be used to give specially designed polynomial-time algorithms (Arora et al., 2014; 2013; Hsu et al., 2012).”
On the Identifiability of Overcomplete Dictionaries via the Minimisation Principle Underlying K-SVD (2013, methodology): “eral not be guaranteed to converge to a local minimiser 1. For the sake of completeness we also mention (without discussion) some very recent results, developed while this work has been under review, [5], [2], [1] . April 3, 2015 DRAFT 5 of (1) unless S= 1 and a greedy algorithm is used, see also th”
Sparse Modeling for Image and Vision Processing (2014, methodology): “Finally, recent algorithms have emerged in the theoretical science community, which are not explicitly based on optimization [see, e.g., Spielman et al., 2013, Recht et al., 2012, Arora et al., 2014].”
Sparse Matrix Factorization (2013, background): “Sparse encoding [2] can be viewed as the problem of writing Y = X 1 X 2 where X 1 is a dictionary that has much fewer columns than Y (which is a special case of sparse) and X 2 is sparse.”
An Analysis of the t-SNE Algorithm for Data Visualization (2018, background): “Researchers have managed to rigorously analyze non-convex optimization algorithms in a host of settings (Dasgupta, 1999; Arora et al., 2012, 2014; Bho-janapalli et al., 2016; Ge et al., 2015a; Sun et al., 2017; Ge et al., 2017, 2016; Park et al., 2017).”
Making Method of Moments Great Again? -- How can GANs learn the target distribution (2020, methodology): “Method of Moments has been used in many other machine learning problems such as mixture of Gaussian distribution [71, 60], topic models [11], hidden Markov models [12], dictionary learning [17], mixture of linear regression [48] and so on, and has been used to design practical GANs [46] as well.”
When can Wasserstein GANs minimize Wasserstein Distance? (2020, methodology): “Method of Moments has been used in many other machine learning problems such as mixture of Gaussian distribution [35, 27], topic models [1], hidden Markov models [2], dictionary learning [5], mixture of linear regression [20] and so on, and has been used to design practical GANs [19] as well.”
Complete dictionary recovery over the sphere (2015, methodology): “[9, 10] and [11, 12] have subsequently given efficient algorithms for the overcomplete setting (m ≥ n), based on a combination of {clustering or spectral initialization} and local refinement.”