# Iterative Atom Refinement: A Monotonicity Principle for Dictionary Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 26 references that are in the map.
- First posted on arXiv 20 Sep 2026.

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

- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture](https://mlsanity.com/paper/1511.03607/) (2015)
- [Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in O(√n) iterations](https://mlsanity.com/paper/1908.10935/) (2019)
- [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)
- [Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initialization](https://mlsanity.com/paper/2207.09660/) (2022)
- [Simple Alternating Minimization Provably Solves Complete Dictionary Learning](https://mlsanity.com/paper/2210.12816/) (2022)
- [Dictionary Learning for the Almost-Linear Sparsity Regime](https://mlsanity.com/paper/2210.10855/) (2022)
- [Approximate Guarantees for Dictionary Learning](https://mlsanity.com/paper/1905.12091/) (2019)
- [Imaging with super-resolution in changing random media](https://mlsanity.com/paper/2511.14147/) (2025)

## Abstract (arXiv)

Dictionary learning seeks to recover an unknown dictionary A from observations bf yi = Abf xi with sparse coefficient vectors bf xi. We introduce the Iterative Atom Refinement (IAR) algorithm, a simple procedure for recovering individual dictionary atoms. Starting from a random direction, IAR repeatedly selects the observations most strongly correlated with the current iterate and updates the direction by averaging the selected data. Our main contribution is a rigorous convergence theory of IAR. Using high-dimensional probabilistic estimates and a novel monotonicity principle for atom-selection probabilities, we show that a small initial advantage of one atom is amplified until that atom is isolated. Under our model assumptions, IAR identifies a generating atom after only three refinement steps. Numerical experiments support the theory and show that the resulting dynamics accurately capture the behavior observed in dictionary refinement.