Iterative Atom Refinement: A Monotonicity Principle for Dictionary Learning
Not on the map. Why?
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.
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
12 of 26 references.
References · 12
- 2014Statistical guarantees for the EM algorithm: From population to sample-based analysiscited by 133
- 2015Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picturecited by 49
- 2019Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in O(√n) iterationscited by 27
- 2016A note on the sample complexity of the Er-SpUD algorithm by Spielman, Wang and Wright for exact recovery of sparsely used dictionariescited by 26
- 2013Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimizationcited by 24
- 2013New Algorithms for Learning Incoherent and Overcomplete Dictionariescited by 22
- 2014Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Methodcited by 22
- 2022Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initializationcited by 9
- 2022Simple Alternating Minimization Provably Solves Complete Dictionary Learningcited by 6
- 2022Dictionary Learning for the Almost-Linear Sparsity Regimecited by 3
- 2019Approximate Guarantees for Dictionary Learningcited by 1
- 2025Imaging with super-resolution in changing random mediacited by 1
Built on by
Not cited yet.