  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.
