Dictionary learning—from local towards global and adaptive.

This paper studies the convergence behaviour of dictionary learning via the Iterative Thresholding and K-residual Means (ITKrM) algorithm. On one hand, it is proved that ITKrM is a contraction under much more relaxed conditions than previously necessary. On the other hand, it is shown that there seem to exist stable fixed points that do not correspond to the generating dictionary, which can be characterised as very coherent. Based on an analysis of the residuals using these bad dictionaries, replacing coherent atoms with carefully designed replacement candidates is proposed. In experiments on synthetic data, this outperforms random or no replacement and always leads to full dictionary recovery. Finally, the question how to learn dictionaries without knowledge of the correct dictionary size and sparsity level is addressed. Decoupling the replacement strategy of coherent or unused atoms into pruning and adding, and slowly carefully increasing the sparsity level, leads to an adaptive version of ITKrM. In several experiments, this adaptive dictionary learning algorithm is shown to recover a generating dictionary from randomly initialized dictionaries of various sizes on synthetic data and to learn meaningful dictionaries on image data. [ABSTRACT FROM AUTHOR]