We propose a new outline for dictionary learning methods 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 the wavelet transform. The computational bottleneck of the procedure is then the chosen clustering method: when using K-means the method runs much faster than K-SVD. 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.

A Tree-based Dictionary Learning Framework