RECURSIVE PARTITIONING TO REDUCE DISTORTION

Adaptive partitioning of a multidimensional feature space plays a fund amental role in the design of data-compression schemes, Most partition -based design methods operate in an iterative fashion, seeking to redu ce distortion at each stage of their operation by implementing a linea r 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 asy mptotic distortion of quantizers produced by the unsupervised implemen tation of the procedures, It is shown that application of the procedur es to a convergent sequence of distributions with a suitable limit yie lds quantizers whose distortion tends to zero. Analogous results are e stablished for tree-structured vector quantizers produced from station ary ergodic training data, The analysis is applicable to procedures em ploying both axis-parallel and oblique splitting, and a variety of dis tortion measures, The results of the paper apply directly to unsupervi sed procedures that may be efficiently implemented on a digital comput er.