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 initialised dictionaries
of various sizes on synthetic data and to learn meaningful dictionaries on
image data.
