On the uniqueness and stability of dictionaries for sparse representation of noisy signals
This work addresses a foundational issue in signal processing and machine learning by providing stability guarantees for sparse representations, which is crucial for applications in data analysis, engineering, and neuroscience, though it is incremental in extending existing theory.
The paper tackles the problem of ensuring uniqueness and stability of dictionaries for sparse coding in noisy conditions, providing general conditions that guarantee recoverability of dictionary elements even with overestimated size or limited sparse supports, and offering a procedure to verify solution uniqueness within noise bounds.
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.