When is sparse dictionary learning well-posed?

HE emergence of response properties of neurons in the mammalian visual cortex from the optimization of dictionaries for sparse coding of natural images marked an exciting development in computational neuroscience [1]-[4]. Many dictionary learning algorithms have since been developed and applied to a variety of problems in signal processing and machine learning (see [5] for a comprehensive review). A popular formulation of the idea is to encode each of N data points as a linear combination of at most k n-dimensional vectors from an inferred dictionary of size m, where k m N. Certain applications to data analysis call for a unique such "sparse structure". For instance, detecting forgeries by analysis of local painting style [6], [7] requires that all dictionaries consistent with training data do not differ appreciably in their ability to sparsely encode new samples. Recently, algorithms with proven convergence under certain conditions have been proposed (see [8, Sec.