Flexible tree-structured signal expansions using time-varying wavelet packets

Addresses the problem of finding the best time-varying filter bank tree-structured representation for a signal. The tree is allowed to vary at regular intervals, and the spacing of these changes can be arbitrarily short. The question of how to choose tree-structured representations of signals based on filter banks is considered. Wavelets and their adaptive version, known as wavelet packets, represent one approach that is popular. Wavelet packets are subband trees where the tree is chosen to match the characteristics of the signal. Variations where the tree varies over time have been proposed as the double tree and the time-frequency tree algorithms. Time-variation adds a further level of adaptivity. In all of the approaches proposed so far, the tree must be either fixed for the whole duration of the signal or fixed for its dyadic subintervals. The solution that we propose, as it allows more flexible variation, is an advance on the wavelet packet algorithm, the double tree algorithm, and the recently proposed time-frequency tree algorithm. Our solution is based on casting it in a dynamic programming (DP) setting. Focusing on compression applications, we use a Lagrangian cost of distortion +λ×rate as the objective function and explain our algorithm in detail, pointing out its relation to existing approaches to the problem. We demonstrate that the new algorithm indeed searches a larger library of representations than previously possible and that overcoming the constraint of dyadic time segmentations gives a significant improvement in practice