Polyphase Filter Implementation for oversampled (undecimated) wavelet lifting scheme?

I am learning about lifting schemes, and for my project, it seems as though it would be beneficial to use an undecimated wavelet transform (UWT).

I have found a paper by Lee, Lee, and Yoo (New lifting based structure for undecimated wavelet transform), and in it they provide a polyphase representation of the lifting operators in an UWT. In one line, they state "We upsample the lifting operators during the progressive stages of processing."

My question is: How is this done? What is the signal-space representation of this upsampling, and can it be implemented in sample space?

Polyphase interpolation can be constructed with the following process:

The filter is designed based on the same approach used for interpolation using the process of inserting zeros (zero stuffing) in between the existing samples, and the filter needed is that which would remove the images in the spectrum that the zero stuffing produces.

I demonstrate this with the graphics below. First shown is an original spectrum of waveform with approximately 1 KHz of double-sided bandwidth sampled at 10 KSps, with the frequency axis extending to Nyquist at +/- 5KHz:

This is upsampled to 40 KSps by inserting three zeros in between every existing sample, which replicates the original spectrum without adding any distortion in band, but creates additional images as shown in the plot below, now with the frequency axis expanded to +/-20 KHz consistent with the sampling rate being increased to 40 KSps:

A "perfect" interpolator would pass the original spectrum with no distortion and completely eliminate the images. Such perfection cannot be physically realized for practical reasons, but we can reduce the distortion to any desired level at the trade of filter complexity (and time delay). An elegant approach is to use multi-band FIR filters which concentrate the rejection only where needed and thus providing superior performance at a relatively small number of taps. Below demonstrates how I achieved greater than 100 dB of image rejection and equally less than that much distortion to the passband with only a 15 tap FIR filter!

The interpolation approach can be completed at this point of inserting zeros and FIR filtering. Transforming this to a polyphase structure does not change the result but provides yet an even more efficient implementation since all of the operations can be done at the lower sampling rate.

To implement a polyphase we would use a multiple of the interpolation rate as the number of taps. So in this example where I interpolated by 4, the filter length would be increased to 16. This will then result in 4 polyphase filters each with 4 coefficients. The coefficients are mapped from our original filter in "row to column" form; meaning if the original coefficients are given as [c0, c1, c2, ...c15], the first polyphase filter would have coefficients [c0, c4, c8, c12], the second would have coefficients [c1, c5, c9, c13], etc. Notice that we are decimating the original filter by 4, and each filter is one shift delayed (at the higher rate) from the previous. This results in a set of "all-pass" filters which all have the same output for a given input, but shifted to a different position in time! An notably each filter is still running at the original (lower) rate. These are each then "fractional delay filters" providing sub-sample delays at our original sampling rate, which is exactly what we would want to interpolate new samples in between our existing ones. A commutator at the filter outputs can then step through each output at the higher rate to create the higher sampled waveform.

I detail polyphase implementations further at this link.

• This demonstration of interpolating filters is brilliant! I am not sure I understand the polyphase upsampling however... In an example with a linear lifting scheme (the interpolation is linear) we find the linear interpolant between x[2] and x[4] (for example) and use this to predict x[3]. If we are upsampling the linear prediction, would we find the interpolant between x[2] and x[6] to predict x[4]? Jan 14 at 15:34
• Yes exactly- that would be at the same position in time and with the higher up-sampling you get more options of time offsets in between Jan 14 at 15:42
• So, when upsampling a polyphase operator, you can just treat the corresponding signal positions as upsampled? As a side-question (my background is very much not in signal processing) is the polyphase representation just a matrix representation of the interpolation operation? Or, it is a clever matrix representation which skips the samples that are decimated out? Jan 14 at 15:56
• Read my linked page as it details what that is. If you are not familiar with FIR filtering; start with getting your head around that. We’re discouraged from using the chat here for back and forth discussion but the above and the linked page should hopefully answer your question Jan 14 at 15:59