# Convergence of alternating minimisation algorithms for dictionary learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 42 references that are in the map.
- First posted on arXiv 4 Apr 2023.

## Builds on (most cited first, 14 of 14)

- [Simple, Efficient, and Neural Algorithms for Sparse Coding](https://mlsanity.com/paper/1503.00778/) (2015)
- [Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization](https://mlsanity.com/paper/1310.7991/) (2013)
- [Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method](https://mlsanity.com/paper/1511.04777/) (2015)
- [New Algorithms for Learning Incoherent and Overcomplete Dictionaries](https://mlsanity.com/paper/1308.6273/) (2013)
- [Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method](https://mlsanity.com/paper/1407.1543/) (2014)
- [Complete Dictionary Recovery over the Sphere](https://mlsanity.com/paper/1504.06785/) (2015)
- [On the Computational Intractability of Exact and Approximate Dictionary Learning](https://mlsanity.com/paper/1405.6664/) (2014)
- [Sparse and spurious: dictionary learning with noise and outliers](https://mlsanity.com/paper/1407.5155/) (2014)
- [A Clustering Approach to Learn Sparsely-Used Overcomplete Dictionaries](https://mlsanity.com/paper/1309.1952/) (2013)
- [Local Identification of Overcomplete Dictionaries](https://mlsanity.com/paper/1401.6354/) (2014)
- [Convergence radius and sample complexity of ITKM algorithms for dictionary learning](https://mlsanity.com/paper/1503.07027/) (2015)
- [Alternating minimization for dictionary learning: Local Convergence Guarantees](https://mlsanity.com/paper/1711.03634/) (2017)
- [Dictionary learning -- from local towards global and adaptive](https://mlsanity.com/paper/1804.07101/) (2018)
- [Adapted variable density subsampling for compressed sensing](https://mlsanity.com/paper/2206.13796/) (2022)

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

- [Coupled Training with Privileged Information and Unlabeled Data](https://mlsanity.com/paper/2605.23268/) (2026)

## Abstract (arXiv)

In this paper we derive sufficient conditions for the convergence of two popular alternating minimisation algorithms for dictionary learning - the Method of Optimal Directions (MOD) and Online Dictionary Learning (ODL), which can also be thought of as approximative K-SVD. We show that given a well-behaved initialisation that is either within distance at most 1/log(K) to the generating dictionary or has a special structure ensuring that each element of the initialisation only points to one generating element, both algorithms will converge with geometric convergence rate to the generating dictionary. This is done even for data models with non-uniform distributions on the supports of the sparse coefficients. These allow the appearance frequency of the dictionary elements to vary heavily and thus model real data more closely.