TERMINATION AND CONTINUITY OF GREEDY GROWING FOR TREE-STRUCTURED VECTOR QUANTIZERS

Tree-structured vector quantizers (TSVQ) provide a computationally eff icient, variable-rate method of compressing vector-valued data. In app lications, the problem of designing a TSVQ from empirical training dat a is critical. Greedy growing algorithms are a common and effective ap proach to the design problem. They are recursive procedures that produ ce a TSVQ one node at a time by optimizing a simple splitting criterio n at each step. While unsupervised greedy growing algorithms are well- understood from an experimental point of view, there has been little t heory to support their use, or to examine their behavior on large trai ning sets. In this paper we present a rigorous analysis of a greedy gr owing algorithm proposed by Riskin and Gray, and Balakrishnan. The fir st part of the paper is a description of the algorithm and an examinat ion of its asymptotic behavior as it applies to a fixed, absolutely co ntinuous distribution. The second part of the paper establishes the st ructural consistency of the algorithm with respect to a convergent seq uence of distributions. As an application, we obtain results concernin g the large sample empirical behavior of the algorithm when it is appl ied to stationary ergodic training vectors.