Iterative Atom Refinement: A Monotonicity Principle for Dictionary Learning
In the authors' words
Dictionary learning seeks to recover an unknown dictionary from observations with sparse coefficient vectors . 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.
Appeared: Tuesday, September 22. arXiv. Preprint, not yet peer-reviewed.