Iterative Atom Refinement: A Monotonicity Principle for Dictionary Learning

Alexander Christie; Miguel Moscoso; Alexei Novikov; George Papanicolaou; Chrysoula Tsogka

cs.LGSep 20, 2026

Iterative Atom Refinement: A Monotonicity Principle for Dictionary Learning

Authors: Alexander Christie, Miguel Moscoso, Alexei Novikov, George Papanicolaou, Chrysoula Tsogka

Abstract

Dictionary learning seeks to recover an unknown dictionary $A$ from observations ${\bf y}_i = A{\bf x}_i$ with sparse coefficient vectors ${\bf x}_i$ . We introduce the \emph{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.

Explore similar work

Multi-Dictionary Learning for Low Rank Sparse Coding
Sep 12, 2025Boya Ma, Abram Magner, Maxwell McNeil +1Unsupervised Dictionary Learning Sparse Recovery
On the Sparsity-Storage-Accuracy Tradeoff in Parsimoniously Activated Dictionary Learning
Jun 21, 2026Zihui Zhao, Yuanbo Tang, Yang LiUnsupervised Dictionary Learning Sparsity
Diverse Dictionary Learning
Apr 19, 2026Yujia Zheng, Zijian Li, Shunxing Fan +2Unsupervised Dictionary Learning Identifiability

Sep 12, 2025 · cs.LGJ/K move · Enter open · S save

Multi-Dictionary Learning for Low Rank Sparse Coding

Boya Ma, Abram Magner, Maxwell McNeil, Petko Bogdanov

University at Albany – SUNY, Computer Science, Albany, NY, USA

Sparse dictionary coding represents signals as linear combinations of a few dictionary atoms. It has been applied to images, time series, graph signals and multi-way spatio-temporal data by jointly employing temporal and spatial dictionaries. Data-agnostic analytical dictionaries, such as the discrete Fourier transform, wavelets and graph Fourier, have seen wide adoption due to efficient implementations and good practical performance. On the other hand, dictionaries learned from data offer sparser and more accurate solutions but require learning of both the dictionaries and the coding coefficients. This becomes especially challenging for multi-dictionary scenarios since encoding coefficients correspond to all atom combinations from the dictionaries. To address this challenge, we propose a low-rank coding model for 2-dictionary scenarios and study its data complexity. Namely, we establish upper and lower bounds on the number of samples needed to learn dictionaries that generalize to unseen samples from the same distribution. We propose an alternating convex optimization solution, called AODL, which employs alternating optimization between the sparse coding matrices and the learned dictionaries. We demonstrate its quality for data reconstruction and missing value imputation in both synthetic and real-world datasets. For a fixed reconstruction quality, AODL learns up to

90\%

sparser solutions compared to non-low-rank and analytical (fixed) dictionary baselines. In addition, the learned dictionaries reveal interpretable insights into patterns from training samples.

Unsupervised Dictionary Learning Sparse Recovery Codebooks Fourier

Open paper Ask about it PDF

Abstract

Explore similar work

Multi-Dictionary Learning for Low Rank Sparse Coding

On the Sparsity-Storage-Accuracy Tradeoff in Parsimoniously Activated Dictionary Learning

Diverse Dictionary Learning