# Convergence radius and sample complexity of ITKM algorithms for dictionary learning

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

## Key facts

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

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

- [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)
- [The Star Geometry of Critic-Based Regularizer Learning](https://mlsanity.com/paper/2408.16852/) (2024)
- [Convergence of alternating minimisation algorithms for dictionary learning](https://mlsanity.com/paper/2304.01768/) (2023)

## Abstract (arXiv)

In this work we show that iterative thresholding and K-means (ITKM) algorithms can recover a generating dictionary with K atoms from noisy S sparse signals up to an error tilde varepsilon as long as the initialisation is within a convergence radius, that is up to a log K factor inversely proportional to the dynamic range of the signals, and the sample size is proportional to K log K tilde varepsilon-2. The results are valid for arbitrary target errors if the sparsity level is of the order of the square root of the signal dimension d and for target errors down to K-ℓ if S scales as S ≤ d/(ℓ log K).