# Local Identification of Overcomplete Dictionaries

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

## Key facts

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

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

- [Simple Alternating Minimization Provably Solves Complete Dictionary Learning](https://mlsanity.com/paper/2210.12816/) (2022)
- [Non-Convex Compressed Sensing with Training Data](https://mlsanity.com/paper/2101.08310/) (2021)
- [Convergence of alternating minimisation algorithms for dictionary learning](https://mlsanity.com/paper/2304.01768/) (2023)
- [Learning Trees of ℓ0-Minimization Problems](https://mlsanity.com/paper/2302.02548/) (2023)
- [Seismic Traveltime Tomography with Label-free Learning](https://mlsanity.com/paper/2402.00310/) (2024)
- [Efficient Matrix Factorization Via Householder Reflections](https://mlsanity.com/paper/2405.07649/) (2024)
- [How Optimality Structures Sparse Dictionaries: Theory for Interpreting SAE Representations](https://mlsanity.com/paper/2606.02385/) (2026)

## Abstract (arXiv)

This paper presents the first theoretical results showing that stable identification of overcomplete μ-coherent dictionaries Phi ∈ ℝd× K is locally possible from training signals with sparsity levels S up to the order O(μ-2) and signal to noise ratios up to O(√d). In particular the dictionary is recoverable as the local maximum of a new maximisation criterion that generalises the K-means criterion. For this maximisation criterion results for asymptotic exact recovery for sparsity levels up to O(μ-1) and stable recovery for sparsity levels up to O(μ-2) as well as signal to noise ratios up to O(√d) are provided. These asymptotic results translate to finite sample size recovery results with high probability as long as the sample size N scales as O(K3dS tilde varepsilon-2), where the recovery precision tilde varepsilon can go down to the asymptotically achievable precision. Further, to actually find the local maxima of the new criterion, a very simple Iterative Thresholding and K (signed) Means algorithm (ITKM), which has complexity O(dKN) in each iteration, is presented and its local efficiency is demonstrated in several experiments.