Multi-Scale Vector Quantization with Reconstruction Trees
This work addresses the problem of efficient data compression and reconstruction for unsupervised learning, but it appears incremental as it builds on existing quantization methods with a novel tree-based approach.
The authors tackled the problem of vector quantization for unsupervised data by proposing a multi-scale algorithm called reconstruction trees, which uses a family of partitions to explore data from coarse to fine scales, and they derived theoretical bounds on expected distortion under distributional assumptions, including finite sample results.
We propose and study a multi-scale approach to vector quantization. We develop an algorithm, dubbed reconstruction trees, inspired by decision trees. Here the objective is parsimonious reconstruction of unsupervised data, rather than classification. Contrasted to more standard vector quantization methods, such as K-means, the proposed approach leverages a family of given partitions, to quickly explore the data in a coarse to fine-- multi-scale-- fashion. Our main technical contribution is an analysis of the expected distortion achieved by the proposed algorithm, when the data are assumed to be sampled from a fixed unknown distribution. In this context, we derive both asymptotic and finite sample results under suitable regularity assumptions on the distribution. As a special case, we consider the setting where the data generating distribution is supported on a compact Riemannian sub-manifold. Tools from differential geometry and concentration of measure are useful in our analysis.