  We propose a new outline for adaptive dictionary learning methods for sparse
encoding based on a hierarchical clustering of the training data. Through
recursive application of a clustering method, the data is organized into a
binary partition tree representing a multiscale structure. The dictionary atoms
are defined adaptively based on the data clusters in the partition tree. This
approach can be interpreted as a generalization of a discrete Haar wavelet
transform. Furthermore, any prior knowledge on the wanted structure of the
dictionary elements can be simply incorporated. The computational complexity of
our proposed algorithm depends on the employed clustering method and on the
chosen similarity measure between data points. Thanks to the multiscale
properties of the partition tree, our dictionary is structured: when using
Orthogonal Matching Pursuit to reconstruct patches from a natural image,
dictionary atoms corresponding to nodes being closer to the root node in the
tree have a tendency to be used with greater coefficients.
