Recursive partitioning to reduce distortion

Adaptive partitioning of a multidimensional feature space plays a fundamental role in the design of data-compression schemes, Most partition-based design methods operate in an iterative fashion, seeking to reduce distortion at each stage of their operation by implementing a linear split of a selected cell, The operation and eventual outcome of such methods is easily described in terms of binary tree-structured vector quantizers. This paper considers a class of simple growing procedures for tree-structured vector quantizers, Of primary interest is the asymptotic distortion of quantizers produced by the unsupervised implementation of the procedures, It is shown that application of the procedures to a convergent sequence of distributions with a suitable limit yields quantizers whose distortion tends to zero. Analogous results are established for tree-structured vector quantizers produced from stationary ergodic training data, The analysis is applicable to procedures employing both axis-parallel and oblique splitting, and a variety of distortion measures, The results of the paper apply directly to unsupervised procedures that may be efficiently implemented on a digital computer.