# More Algorithms for Provable Dictionary Learning

arXiv: https://arxiv.org/abs/1401.0579 · HTML: https://mlsanity.com/paper/1401.0579/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jan 2014.

## Built on by (most cited first, 6 of 6)

- [Dictionary Learning for the Almost-Linear Sparsity Regime](https://mlsanity.com/paper/2210.10855/) (2022)
- [Non-Convex Compressed Sensing with Training Data](https://mlsanity.com/paper/2101.08310/) (2021)
- [Symphony in the Latent Space: Provably Integrating High-dimensional Techniques with Non-linear Machine Learning Models](https://mlsanity.com/paper/2212.00852/) (2022)
- [Robust Correlation Clustering with Asymmetric Noise](https://mlsanity.com/paper/2110.08385/) (2021)
- [Learning Trees of ℓ0-Minimization Problems](https://mlsanity.com/paper/2302.02548/) (2023)
- [Hiding Data Helps: On the Benefits of Masking for Sparse Coding](https://mlsanity.com/paper/2302.12715/) (2023)

## Abstract (arXiv)

In dictionary learning, also known as sparse coding, the algorithm is given samples of the form y = Ax where x∈ ℝm is an unknown random sparse vector and A is an unknown dictionary matrix in ℝn× m (usually m > n, which is the overcomplete case). The goal is to learn A and x. This problem has been studied in neuroscience, machine learning, visions, and image processing. In practice it is solved by heuristic algorithms and provable algorithms seemed hard to find. Recently, provable algorithms were found that work if the unknown feature vector x is √n-sparse or even sparser. Spielman et al. citeDBLP:journals/jmlr/SpielmanWW12 did this for dictionaries where m=n; Arora et al. citeAGM gave an algorithm for overcomplete (m >n) and incoherent matrices A; and Agarwal et al. citeDBLP:journals/corr/AgarwalAN13 handled a similar case but with weaker guarantees. This raised the problem of designing provable algorithms that allow sparsity gg √n in the hidden vector x. The current paper designs algorithms that allow sparsity up to n/poly(log n). It works for a class of matrices where features are individually recoverable, a new notion identified in this paper that may motivate further work. The algorithm runs in quasipolynomial time because they use limited enumeration.