# Sparse and spurious: dictionary learning with noise and outliers

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jul 2014.

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

- [White-Box Transformers via Sparse Rate Reduction](https://mlsanity.com/paper/2306.01129/) (2023)
- [Understanding approximate and unrolled dictionary learning for pattern recovery](https://mlsanity.com/paper/2106.06338/) (2021)
- [Simple Alternating Minimization Provably Solves Complete Dictionary Learning](https://mlsanity.com/paper/2210.12816/) (2022)
- [Stop Probing, Start Coding: Why Linear Probes and Sparse Autoencoders Fail at Compositional Generalisation](https://mlsanity.com/paper/2603.28744/) (2026)
- [A consistent and flexible framework for deep matrix factorizations](https://mlsanity.com/paper/2206.10693/) (2022)
- [Convergence of alternating minimisation algorithms for dictionary learning](https://mlsanity.com/paper/2304.01768/) (2023)
- [Hiding Data Helps: On the Benefits of Masking for Sparse Coding](https://mlsanity.com/paper/2302.12715/) (2023)
- [Estimation of Models with Limited Data by Leveraging Shared Structure](https://mlsanity.com/paper/2310.02864/) (2023)
- [Dictionary Learning: The Complexity of Learning Sparse Superposed Features with Feedback](https://mlsanity.com/paper/2502.05407/) (2025)
- [How Optimality Structures Sparse Dictionaries: Theory for Interpreting SAE Representations](https://mlsanity.com/paper/2606.02385/) (2026)
- [Math for AI safety: an invitation for mathematicians](https://mlsanity.com/paper/2609.15289/) (2026)

## Abstract (arXiv)

A popular approach within the signal processing and machine learning communities consists in modelling signals as sparse linear combinations of atoms selected from a learned dictionary. While this paradigm has led to numerous empirical successes in various fields ranging from image to audio processing, there have only been a few theoretical arguments supporting these evidences. In particular, sparse coding, or sparse dictionary learning, relies on a non-convex procedure whose local minima have not been fully analyzed yet. In this paper, we consider a probabilistic model of sparse signals, and show that, with high probability, sparse coding admits a local minimum around the reference dictionary generating the signals. Our study takes into account the case of over-complete dictionaries, noisy signals, and possible outliers, thus extending previous work limited to noiseless settings and/or under-complete dictionaries. The analysis we conduct is non-asymptotic and makes it possible to understand how the key quantities of the problem, such as the coherence or the level of noise, can scale with respect to the dimension of the signals, the number of atoms, the sparsity and the number of observations.