On the Local Correctness of L^1 Minimization for Dictionary Learning

By Quan Geng, Huan Wang, John Wright. 2011

76 citations recorded by the source corpus.

The idea that many important classes of signals can be well-represented by linear combinations of a small set of atoms selected from a given dictionary has had dramatic impact on the theory and practice of signal processing. For practical problems in which an appropriate sparsifying dictionary is not known ahead of time, a very popular and successful heuristic is to search for a dictionary that minimizes an appropriate sparsity surrogate over a given set of sample data. While this idea is appealing, the behavior of these algorithms is largely a mystery; although there is a body of empirical evidence suggesting they do learn very effective representations, there is little theory to guarantee when they will behave correctly, or when the learned dictionary can be expected to generalize. In this paper, we take a step towards such a theory. We show that under mild hypotheses, the dictionary learning problem is locally well-posed: the desired solution is indeed a local minimum of the $\ell^1$ norm. Namely, if $\mb A \in \Re^{m \times n}$ is an incoherent (and possibly overcomplete) dictionary, and the coefficients $\mb X \in \Re^{n \times p}$ follow a random sparse model, then with high probability $(\mb A,\mb X)$ is a local minimum of the $\ell^1$ norm over the manifold of factorizations $(\mb A',\mb X')$ satisfying $\mb A' \mb X' = \mb Y$, provided the number of samples $p = \Omega(n^3 k)$. For overcomplete $\mb A$, this is the first result showing that the dictionary learning problem is locally solvable. Our analysis draws on tools developed for the problem of completing a low-rank matrix from a small subset of its entries, which allow us to overcome a number of technical obstacles; in particular, the absence of the restricted isometry property.

Subfields: Biomedical Engineering, Computational Mechanics, Representation & Self-Supervised Learning, Optimization & Training, 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 Representation & Self-Supervised Learning

In Optimization & Training

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, 34, 53, 56].”
On the Identifiability of Overcomplete Dictionaries via the Minimisation Principle Underlying K-SVD (2013, background): “s themselves state that the algorithm is only of theoretical interest because of its computational complexity and also for the ‘ 1-minimisation principle, suggested in [43], [30] and studied in [21], [17], [22], ﬁnding a local minimum is computational sufﬁciently challenging to prohibit the learning”
Exact Recovery of Sparsely Used Overcomplete Dictionaries (2013, methodology): “Other works consider more sophisticated methods from an optimization viewpoint while still alternating between dictionary and coefficient updates [23, 17].”
Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization (2013, background): “al [12] both consider the noiseless setting, and analyze the following non-convex program”