# Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2013.

## Built on by (most cited first, 24 of 24)

- [Large Multi-modal Models Can Interpret Features in Large Multi-modal Models](https://mlsanity.com/paper/2411.14982/) (2024)
- [Understanding approximate and unrolled dictionary learning for pattern recovery](https://mlsanity.com/paper/2106.06338/) (2021)
- [LF-Steering: Latent Feature Activation Steering for Enhancing Semantic Consistency in Large Language Models](https://mlsanity.com/paper/2501.11036/) (2025)
- [Simple Alternating Minimization Provably Solves Complete Dictionary Learning](https://mlsanity.com/paper/2210.12816/) (2022)
- [Optimal Regularization for a Data Source](https://mlsanity.com/paper/2212.13597/) (2022)
- [Personalized Dictionary Learning for Heterogeneous Datasets](https://mlsanity.com/paper/2305.15311/) (2023)
- [Unique sparse decomposition of low rank matrices](https://mlsanity.com/paper/2106.07736/) (2021)
- [On the convergence of group-sparse autoencoders](https://mlsanity.com/paper/2102.07003/) (2021)
- [Dictionary Learning for the Almost-Linear Sparsity Regime](https://mlsanity.com/paper/2210.10855/) (2022)
- [The Star Geometry of Critic-Based Regularizer Learning](https://mlsanity.com/paper/2408.16852/) (2024)
- [Mechanistic Interpretability with Sparse Autoencoder Neural Operators](https://mlsanity.com/paper/2509.03738/) (2025)
- [Weighed l1 on the simplex: Compressive sensing meets locality](https://mlsanity.com/paper/2104.13894/) (2021)
- [The Effect of SGD Batch Size on Autoencoder Learning: Sparsity, Sharpness, and Feature Learning](https://mlsanity.com/paper/2308.03215/) (2023)
- [DB-KSVD: Scalable Alternating Optimization for Disentangling High-Dimensional Embedding Spaces](https://mlsanity.com/paper/2505.18441/) (2025)
- [Low Rank Forecasting](https://mlsanity.com/paper/2101.12414/) (2021)
- [Gaussian Process Convolutional Dictionary Learning](https://mlsanity.com/paper/2104.00530/) (2021)
- [Convergence of alternating minimisation algorithms for dictionary learning](https://mlsanity.com/paper/2304.01768/) (2023)
- [Evaluating Sparse Autoencoders: From Shallow Design to Matching Pursuit](https://mlsanity.com/paper/2506.05239/) (2025)
- [Learning Large Scale Sparse Models](https://mlsanity.com/paper/2301.10958/) (2023)
- [Wave-informed dictionary learning for high-resolution imaging in complex media](https://mlsanity.com/paper/2310.12990/) (2023)
- [Efficient Matrix Factorization Via Householder Reflections](https://mlsanity.com/paper/2405.07649/) (2024)
- [Super-resolution in disordered media using neural networks](https://mlsanity.com/paper/2410.21556/) (2024)
- [Enhancing Performance of Explainable AI Models with Constrained Concept Refinement](https://mlsanity.com/paper/2502.06775/) (2025)
- [Iterative Atom Refinement: A Monotonicity Principle for Dictionary Learning](https://mlsanity.com/paper/2609.23812/) (2026)

## Abstract (arXiv)

We consider the problem of sparse coding, where each sample consists of a sparse linear combination of a set of dictionary atoms, and the task is to learn both the dictionary elements and the mixing coefficients. Alternating minimization is a popular heuristic for sparse coding, where the dictionary and the coefficients are estimated in alternate steps, keeping the other fixed. Typically, the coefficients are estimated via ℓ1 minimization, keeping the dictionary fixed, and the dictionary is estimated through least squares, keeping the coefficients fixed. In this paper, we establish local linear convergence for this variant of alternating minimization and establish that the basin of attraction for the global optimum (corresponding to the true dictionary and the coefficients) is order1/s2, where s is the sparsity level in each sample and the dictionary satisfies RIP. Combined with the recent results of approximate dictionary estimation, this yields provable guarantees for exact recovery of both the dictionary elements and the coefficients, when the dictionary elements are incoherent.