Iterative Atom Refinement: A Monotonicity Principle for Dictionary Learning

arXiv:2609.23812v1 Announce Type: new Abstract: Dictionary learning seeks to recover an unknown dictionary A from observations {f y}_i = A{f x}_i with sparse coefficient vectors {f x}_i. 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.

Source: arXiv cs.LG | 2026-09-22