We formulate the basis selection problem as finding the optimal pruning of the space and frequency graph. The pruning technique was first suggested for wavelet packets in [CMQW90] and was also used in [RV93]. These previous works applied the pruning algorithm to a tree with two decision points at each node: prune vs. not prune. The difference here is that the data structure is a graph with a three-way decision at each node: (1) terminate, (2) branch by frequency, or (3) branch by segmentation. However, the tree algorithm is easily extended to the graph. The algorithm works as follows: first, a coding cost value is assigned to each node. Then, by iterating over the full graph, the least cost embedded sub-graphs from each node are found. The final structure left after all pruning is the graph with the lowest total cost.
Figure 13: (a) adaptive pruning, (b) rate-distortion operating point computation.