The wavelet packet transform (WPT) - the binary-tree generalization of the discrete wavelet transform that partitions the spectrum into 2n2^n subbands - inherits two classical pathologies from critically sampled filter banks: shift-variance (a one-sample input shift changes packet energies) and 'mirrored' frequency ordering (downsampling after high-pass filtering folds the Nyquist component to DC, so packet indices are not in increasing-frequency order). Kobayashi and Nakano's 2013 ITNG paper analyzed both for the complex dual-tree WPT built from two conjugate quadrature filter (CQF) banks related by a half-sample delay, arguing that simultaneous shift-invariance of all packets is impossible in that architecture (only low-pass children inherit it), and proposing a recursive permutation table that restores frequency order. The authors' own 2017 follow-up restates that the shift-invariance issue is not settled: their theory 'cannot make all packets shift-invariant in a classical wavelet packet transform tree'. The surviving open core, acknowledged by the authors themselves, is therefore: within the classical critically sampled wavelet packet tree built from finite-impulse-response CQF banks and its delay-based dual-tree complex extensions - two banks related by the generalized half-sample delay G0I(z)=z−λ/2G0R(z)G_0^I(z)=z^{-\lambda/2}G_0^R(z), equivalently H0I(z)=zλ/2H0R(z)H_0^I(z)=z^{\lambda/2}H_0^R(z), including the bi-orthogonal generalization treated in the 2017 companion - determine whether an architecture exists that makes every packet simultaneously shift-invariant in the energy sense. The broader capability question is already served outside the classical setting - by undecimated packets, the approximately shift-invariant dual-tree WPT of Bayram and Selesnick, and the perfect-translation-invariant Meyer-based complex WPTs of Toda, Zhang and Imamura - which leaves the classical-FIR-tree case untouched.

Background

The discrete wavelet transform (DWT) represents a discrete signal by recursive filtering of its low-pass band: at each level, complementary low-pass and high-pass finite-impulse-response (FIR) filters are followed by downsampling (keeping every second sample), which halves the band. The wavelet packet transform (WPT) generalizes this by recursing on both channels, producing a binary tree whose level-LL leaves ('packets') partition the spectrum into 2L2^L subbands; a best-basis algorithm (Coifman and Wickerhauser, 1992) then selects a subtree adapted to the signal.

Two pathologies of this construction are classical. First, shift-variance: because downsampling keeps only every second sample, shifting the input by one sample changes which samples enter the computation, so the energy of each packet can vary under a one-sample shift - harmful for change detection, denoising, and pattern recognition. Shift-invariance here means that the total energy of a packet's coefficients (sum of squares over the real and imaginary parts in a complex transform) is unchanged under a one-sample input shift. The stationary (undecimated) wavelet transform removes downsampling and is exactly shift-invariant at the price of redundancy (Nason and Silverman, 1995). The dual-tree complex wavelet transform (DT-CWT) of Kingsbury achieves approximate shift-invariance with only 2×2\times redundancy by running two filter banks whose low-pass filters differ by a half-sample delay, making the corresponding wavelets an approximate Hilbert transform pair - a pair of functions whose Fourier spectra occupy disjoint positive and negative frequency halves (Kingsbury, 2001; Selesnick, Baraniuk and Kingsbury, 2005). A conjugate quadrature filter (CQF) bank is an orthonormal perfect-reconstruction two-channel FIR filter bank, the standard vehicle for orthonormal wavelets.

Second, the mirrored frequency order: after high-pass filtering, downsampling folds the original Nyquist frequency ω=π\omega=\pi onto DC (ω=0\omega=0), reversing the frequency axis of every high-pass channel; consequently the natural (tree) index of a packet does not sort packets by frequency (for example, in a two-level WPT the packet with index 3 carries a higher band than the packet with index 4). Standard wavelet software accordingly exposes both a 'natural' and a 'frequency' node ordering (for instance the PyWavelets wavelet packet tree interface).

Kobayashi and Nakano (2013) analyzed both pathologies for the complex dual-tree WPT built from two CQF banks whose low-pass filters satisfy H0I(z)=z−1/2H0R(z)H_0^I(z)=z^{-1/2}H_0^R(z). Using z-domain delay analysis they showed that under this relation the low-pass child of each packet inherits the 1:z−1/21:z^{-1/2} delay that creates a parallel-DWT structure (whose combined real-plus-imaginary energy equals the energy of the signal before downsampling and is therefore shift-invariant), while the high-pass child inherits a 1:11:1 relation that leaves it shift-variant; they concluded that within this architecture simultaneous shift-invariance of all packets is impossible. They also proposed the recursive reordering table c0=[1]c_0=[1], cL+1=[cL,reverse⁡(cL)+max⁡(cL)]c_{L+1}=[c_L,\operatorname{reverse}(c_L)+\max(c_L)], in which cLc_L lists the 2L2^L level-LL packets in increasing frequency order (giving [1,2,4,3][1,2,4,3] at level 2 and [1,2,4,3,7,8,6,5][1,2,4,3,7,8,6,5] at level 3), which relabels packets into increasing frequency order without touching the filter bank. The Meyer wavelet, used in the adjacent constructions below, is defined in the frequency domain and is exactly band-limited, unlike compactly supported FIR wavelets.

Adjacent literature leaves the classical-FIR-tree case open from several directions. The dual-tree complex WPT of Bayram and Selesnick (2008) is only approximately shift-invariant. Toda, Zhang and Imamura (2009, 2010) design complex WPTs with perfect translation invariance, but from band-limited Meyer-type wavelets rather than classical FIR CQF trees. Pesquet, Krim and Carfantan (1996) and Cohen, Raz and Malah (1995) constructed time-invariant or shift-invariant wavelet packet representations by other means, and Yu (2009) analyzes a generalized notion (mu-shift-invariance) under which critically sampled systems can be invariant. Kobayashi and Nakano's 2017 follow-up, a quasi-shift-invariant complex DWT, restates explicitly that making all packets of the classical WPT tree shift-invariant remains unsolved within their theory; that theory fixes the architecture analyzed here: two CQF (or bi-orthogonal) banks whose reconstruction low-pass filters satisfy the generalized half-sample-delay relation G0I(z)=z−λ/2G0R(z)G_0^I(z)=z^{-\lambda/2}G_0^R(z), λ∈{+1,−1}\lambda\in\{+1,-1\}, equivalently H0I(z)=zλ/2H0R(z)H_0^I(z)=z^{\lambda/2}H_0^R(z) on the decomposition side, together with an inter-tree input delay z−βz^{-\beta}.

Problem Statement

The problem is the unfinished agenda of Kobayashi and Nakano's analysis of the classical wavelet packet transform, restated by the authors themselves as unsolved in 2017. It concerns the wavelet packet tree built from classical finite-impulse-response conjugate quadrature filter (CQF) banks, including the delay-based dual-tree complex extensions of the source line of work, in which a real bank and an imaginary bank are related by the generalized half-sample delay G0I(z)=z−λ/2G0R(z)G_0^I(z)=z^{-\lambda/2}G_0^R(z) on the reconstruction side, equivalently H0I(z)=zλ/2H0R(z)H_0^I(z)=z^{\lambda/2}H_0^R(z), λ∈{+1,−1}\lambda\in\{+1,-1\}, on the decomposition side, together with the bi-orthogonal generalization treated in the 2017 companion (its Eqs. 13, 19, 20, 47). The objective is a complete theoretical account of the shift-invariance pathology of this specific architecture - the same setting the source papers analyzed. Its research target is the existence question stated below.

The existence question - simultaneous shift-invariance of all packets. Working inside the classical critically sampled tree structure (with at most the bounded dual-tree/complex extension of the source line of work, not the undecimated stationary transform whose invariance is trivial), determine whether an architecture exists in which every packet of a full wavelet packet tree is simultaneously shift-invariant in the energy sense - the sum of squared coefficients over the real and imaginary parts of each packet is unchanged when the input signal is shifted by one sample. The admissible architecture class is fixed by the source structure rather than chosen by the solver: two critically sampled FIR CQF or bi-orthogonal banks at the dual-tree 2×2\times redundancy, whose low-pass filters satisfy the generalized half-sample-delay relation above, together with the inter-tree input delay z−βz^{-\beta} of the 2017 companion; the strict relation H0I(z)=z−1/2H0R(z)H_0^I(z)=z^{-1/2}H_0^R(z) analyzed in 2013 is a case of it. The authors' own theory provably cannot achieve all-packet invariance - the 2017 companion lists '(P2) Our theory cannot make all packets shift-invariant in a classical wavelet packet transform tree' among its unsolved problems - which is what keeps the question open. The existing partially-invariant constructions lie outside this class and provide context rather than answers: the approximately shift-invariant dual-tree complex wavelet packet transform of Bayram and Selesnick (2008), and the perfect-translation-invariant Meyer-based complex wavelet packet transforms of Toda, Zhang and Imamura (2009, 2010), which rely on exactly band-limited wavelets designed in the frequency domain.

References

  1. M. Kobayashi and K. Nakano, 'Two Problems of Wavelet Packet Transform', in Proc. 2013 10th International Conference on Information Technology: New Generations (ITNG), Las Vegas, NV, USA, pp. 153-159, IEEE, 2013. DOI: 10.1109/ITNG.2013.27, URL: https://doi.org/10.1109/ITNG.2013.27
  2. M. Kobayashi and K. Nakano, 'Development of Quasi-Shift-Invariant Complex Discrete Wavelet Transform', Journal of Signal Processing, Vol. 21, No. 5, pp. 211-224, 2017. DOI: 10.2299/jsp.21.211, URL: https://doi.org/10.2299/jsp.21.211
  3. I. Bayram and I. W. Selesnick, 'On the Dual-Tree Complex Wavelet Packet and M-Band Transforms', IEEE Transactions on Signal Processing, Vol. 56, No. 6, pp. 2298-2310, 2008. DOI: 10.1109/TSP.2007.916129, URL: https://doi.org/10.1109/TSP.2007.916129
  4. H. Toda and Z. Zhang, 'Perfectly translation-invariant complex wavelet packet transforms', in Proc. 2009 International Conference on Wavelet Analysis and Pattern Recognition (ICWAPR), Baoding, China, pp. 374-379, IEEE, 2009. DOI: 10.1109/ICWAPR.2009.5207462, URL: https://doi.org/10.1109/ICWAPR.2009.5207462
  5. H. Toda, Z. Zhang and T. Imamura, 'The design of complex wavelet packet transforms based on perfect translation invariance theorems', International Journal of Wavelets, Multiresolution and Information Processing, Vol. 08, No. 04, pp. 537-558, 2010. DOI: 10.1142/S0219691310003638, URL: https://doi.org/10.1142/S0219691310003638
  6. J.-C. Pesquet, H. Krim and H. Carfantan, 'Time-invariant orthonormal wavelet representations', IEEE Transactions on Signal Processing, Vol. 44, No. 8, pp. 1964-1970, 1996. DOI: 10.1109/78.533717, URL: https://doi.org/10.1109/78.533717
  7. I. Cohen, S. Raz and D. Malah, 'Shift invariant wavelet packet bases', in Proc. 1995 International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Vol. 2, pp. 1081-1084, IEEE, 1995. DOI: 10.1109/ICASSP.1995.480422, URL: https://doi.org/10.1109/ICASSP.1995.480422
  8. N. Kingsbury, 'Complex wavelets for shift invariant analysis and filtering of signals', Applied and Computational Harmonic Analysis, Vol. 10, No. 3, pp. 234-253, 2001. DOI: 10.1006/acha.2000.0343, URL: https://doi.org/10.1006/acha.2000.0343
  9. I. W. Selesnick, R. G. Baraniuk and N. C. Kingsbury, 'The dual-tree complex wavelet transform', IEEE Signal Processing Magazine, Vol. 22, No. 6, pp. 123-151, 2005. DOI: 10.1109/MSP.2005.1550194, URL: https://doi.org/10.1109/MSP.2005.1550194
  10. G. P. Nason and B. W. Silverman, 'The stationary wavelet transform and some statistical applications', in Wavelets and Statistics, Lecture Notes in Statistics, Vol. 103, pp. 281-299, Springer, 1995. DOI: 10.1007/978-1-4612-2544-7_17, URL: https://doi.org/10.1007/978-1-4612-2544-7_17
  11. R. R. Coifman and M. V. Wickerhauser, 'Entropy-based algorithms for best basis selection', IEEE Transactions on Information Theory, Vol. 38, No. 2, pp. 713-718, 1992. DOI: 10.1109/18.119732, URL: https://doi.org/10.1109/18.119732
  12. R. Yu, 'A new shift-invariance of discrete-time systems and its application to discrete wavelet transform analysis', IEEE Transactions on Signal Processing, Vol. 57, No. 7, pp. 2527-2537, 2009. DOI: 10.1109/TSP.2009.2019232, URL: https://doi.org/10.1109/TSP.2009.2019232
  13. PyWavelets project, 'Wavelet Packets - PyWavelets Documentation' (documents the wavelet packet tree node ordering parameter with values 'natural' and 'freq'), software documentation. URL: https://pywavelets.readthedocs.io/en/latest/ref/wavelet-packets.html