# Simple Alternating Minimization Provably Solves Complete Dictionary Learning

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 59 references that are in the map.
- First posted on arXiv 23 Oct 2022.

## Builds on (most cited first, 25 of 25)

- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture](https://mlsanity.com/paper/1511.03607/) (2015)
- [Simple, Efficient, and Neural Algorithms for Sparse Coding](https://mlsanity.com/paper/1503.00778/) (2015)
- [A note on the sample complexity of the Er-SpUD algorithm by Spielman, Wang and Wright for exact recovery of sparsely used dictionaries](https://mlsanity.com/paper/1601.02049/) (2016)
- [Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization](https://mlsanity.com/paper/1310.7991/) (2013)
- [New Algorithms for Learning Incoherent and Overcomplete Dictionaries](https://mlsanity.com/paper/1308.6273/) (2013)
- [Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method](https://mlsanity.com/paper/1407.1543/) (2014)
- [Complete Dictionary Recovery over the Sphere](https://mlsanity.com/paper/1504.06785/) (2015)
- [Finding a sparse vector in a subspace: Linear sparsity using alternating directions](https://mlsanity.com/paper/1412.4659/) (2014)
- [Subgradient Descent Learns Orthogonal Dictionaries](https://mlsanity.com/paper/1810.10702/) (2018)
- [Stable and Interpretable Unrolled Dictionary Learning](https://mlsanity.com/paper/2106.00058/) (2021)
- [Exact Guarantees on the Absence of Spurious Local Minima for Non-negative Rank-1 Robust Principal Component Analysis](https://mlsanity.com/paper/1812.11466/) (2018)
- [Sparse and spurious: dictionary learning with noise and outliers](https://mlsanity.com/paper/1407.5155/) (2014)
- [Understanding approximate and unrolled dictionary learning for pattern recovery](https://mlsanity.com/paper/2106.06338/) (2021)
- [Efficient Dictionary Learning with Gradient Descent](https://mlsanity.com/paper/1809.10313/) (2018)
- [Local Identification of Overcomplete Dictionaries](https://mlsanity.com/paper/1401.6354/) (2014)
- [Identifiability of Complete Dictionary Learning](https://mlsanity.com/paper/1808.08765/) (2018)
- [Complete Dictionary Learning via ℓp-norm Maximization](https://mlsanity.com/paper/2002.10043/) (2020)
- [Analysis of Fast Structured Dictionary Learning](https://mlsanity.com/paper/1805.12529/) (2018)
- [NOODL: Provable Online Dictionary Learning and Sparse Coding](https://mlsanity.com/paper/1902.11261/) (2019)
- [Convergence radius and sample complexity of ITKM algorithms for dictionary learning](https://mlsanity.com/paper/1503.07027/) (2015)
- [Alternating minimization for dictionary learning: Local Convergence Guarantees](https://mlsanity.com/paper/1711.03634/) (2017)
- [Dictionary learning -- from local towards global and adaptive](https://mlsanity.com/paper/1804.07101/) (2018)
- [Compressed Dictionary Learning](https://mlsanity.com/paper/1805.00692/) (2018)

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

- [Personalized Dictionary Learning for Heterogeneous Datasets](https://mlsanity.com/paper/2305.15311/) (2023)
- [SPEAR++: Scaling Gradient Inversion via Sparsely-Used Dictionary Learning](https://mlsanity.com/paper/2510.24200/) (2025)
- [Efficient Matrix Factorization Via Householder Reflections](https://mlsanity.com/paper/2405.07649/) (2024)
- [Fast Structured Orthogonal Dictionary Learning using Householder Reflections](https://mlsanity.com/paper/2409.09138/) (2024)
- [Enhancing Performance of Explainable AI Models with Constrained Concept Refinement](https://mlsanity.com/paper/2502.06775/) (2025)
- [Iterative Atom Refinement: A Monotonicity Principle for Dictionary Learning](https://mlsanity.com/paper/2609.23812/) (2026)

## Abstract (arXiv)

This paper focuses on the noiseless complete dictionary learning problem, where the goal is to represent a set of given signals as linear combinations of a small number of atoms from a learned dictionary. There are two main challenges faced by theoretical and practical studies of dictionary learning: the lack of theoretical guarantees for practically-used heuristic algorithms and their poor scalability when dealing with huge-scale datasets. Towards addressing these issues, we propose a simple and efficient algorithm that provably recovers the ground truth when applied to the nonconvex and discrete formulation of the problem in the noiseless setting. We also extend our proposed method to mini-batch and online settings where the data is huge-scale or arrives continuously over time. At the core of our proposed method lies an efficient preconditioning technique that transforms the unknown dictionary to a near-orthonormal one, for which we prove a simple alternating minimization technique converges linearly to the ground truth under minimal conditions. Our numerical experiments on synthetic and real datasets showcase the superiority of our method compared with the existing techniques.