Multi-scale vector quantization with reconstruction trees. (12th May 2020)

• Record Type: Journal Article
• Authors: Cecini, Enrico; De Vito, Ernesto; Rosasco, Lorenzo
• Is Part Of: Information and inference. Volume 10:Number 3(2021)
• Page Start: 955
• Page End: 986
• Publication Date: 2020-05-12
• Subjects: vector quantization -- reconstruction trees -- multi-resolution analysis -- adaptive approximation -- manifold learning; Mathematical models -- Periodicals; 519.605
• DOI: 10.1093/imaiai/iaaa004
• Languages: English
• ISSNs: 2049-8764

Abstract

Abstract: We propose and study a multi-scale approach to vector quantization (VQ). 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 VQ 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 submanifold. Tools from differential geometry and concentration of measure are useful in our analysis.