Multi-Scale Vector Quantization with Reconstruction Trees

Dealing with large high-dimensional data-sets is a hallmark of modern signal processing and machine learning. In this context, finding parsimonious representation from unlabeled data is often key to both reliable estimation and efficient computations, and more generally for exploratory data analysis. A classical approach to this problem is principal component analysis (PCA), relying on the assumption that data are well represented by a linear subspace. Starting from PCA a number of developments can be considered to relax the linearity assumption. For example kernel PCA is based on performing PCA after a suitable nonlinear embedding [26]. Sparse dictionary learning tries to find a set of vectors on which the data can be written as sparse linear combinations [21]. Another line of works assumes the data to be sampled from a distribution supported on a manifold and include isomap [29], hessian eigenmaps [8], laplacian eigenmaps [3] and related developments such as diffusion maps [20]. A more recent and original perspective has been proposed in [14], and called geometric multi-resolution analysis (GMRA). Here the idea is to borrow and generalize ideas from multi-resolution analysis and wavelet theory [17], to derive locally linear representation organized in a multi-scale fashion.