  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.
