# On the uniqueness and stability of dictionaries for sparse representation of noisy signals

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2016.

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

- [Superposition Without Interference? Towards Isolated Interventions via Almost Orthogonal Features in Language Models](https://mlsanity.com/paper/2602.04718/) (2026)

## Abstract (arXiv)

Learning optimal dictionaries for sparse coding has exposed characteristic sparse features of many natural signals. However, universal guarantees of the stability of such features in the presence of noise are lacking. Here, we provide very general conditions guaranteeing when dictionaries yielding the sparsest encodings are unique and stable with respect to measurement or modeling error. We demonstrate that some or all original dictionary elements are recoverable from noisy data even if the dictionary fails to satisfy the spark condition, its size is overestimated, or only a polynomial number of distinct sparse supports appear in the data. Importantly, we derive these guarantees without requiring any constraints on the recovered dictionary beyond a natural upper bound on its size. Our results also yield an effective procedure sufficient to affirm if a proposed solution to the dictionary learning problem is unique within bounds commensurate with the noise. We suggest applications to data analysis, engineering, and neuroscience and close with some remaining challenges left open by our work.