On the complexity of optimal tree pruning for source coding

Tree-structured vector quantization is a technique to represent a codebook that simplifies encoding as well as quantizer design. The authors define the notion of an optimal pruned tree subject to a cost constraint, and study the computational complexity of finding such a tree. Under the assumption that all trees are equally probable, it is shown that on average the number of pruned trees in a given tree is exponential in the number of leaves. Finding an optimal pruned tree subject to constraints such as entropy or the expected depth is NP-hard. However, when the constraint is the number of leaves, the problem can be solved in O(nk) time, where n is the size of the initial tree and k the constraint size. Experimental results for image compression show the performance of the optimal pruned tree to be comparable with that of full-search vector quantizers