Partition mixture of 1D wavelets for multi-dimensional data

Meng Li, Li Ma

Abstract Traditional statistical wavelet analysis that carries out modeling and inference based on wavelet coefficients under a given, predetermined wavelet transform can quickly lose efficiency in multivariate problems, because such wavelet transforms, which are typically symmetric with respect to the dimensions, cannot adaptively exploit the energy distribution in a problem-specific manner. We introduce a principled probabilistic framework for incorporating such adaptivity—by (i) representing multivariate functions using one-dimensional (1D) wavelet transforms applied to a permuted version of the original function, and (ii) placing a prior on the corresponding permutation, thereby forming a mixture of permuted 1D wavelet transforms. Such a representation can achieve substantially better energy concentration in the wavelet coefficients. In particular, when combined with the Haar basis, we show that exact Bayesian inference under the model can be achieved analytically through a recursive message passing algorithm with a computational complexity that scales linearly with sample size. In addition, we propose a sequential Monte Carlo (SMC) inference algorithm for other wavelet bases using the exact Haar solution as the proposal. We demonstrate that with this framework even simple 1D Haar wavelets can achieve excellent performance in both 2D and 3D image reconstruction via numerical experiments, outperforming state-of-the-art multidimensional wavelet-based methods especially in low signal-to-noise ratio settings, at a fraction of the computational cost.

Introduction

Traditional wavelet transforms, such as the Discrete Wavelet Transform (DWT), are fundamental tools in signal processing due to their speed and compression capabilities. However, they suffer from a "fixed-grid" limitation: they are generally symmetric across dimensions and fail to adapt to the specific geometric structures inherent in a dataset. For instance, in medical imaging like retinal OCT scans, features may be elongated horizontally while varying sharply vertically. A standard 2D wavelet treats both directions identically, often smearing these delicate asymmetric features. While deep learning models can learn these features, they require massive training sets and significant computational resources. This research introduces WARP (WAvelets with Recursive Partitioning), a Bayesian framework that offers the speed of classical wavelets with the adaptivity of modern machine learning.

The WARP Framework

The core innovation of WARP is treating the order in which pixels are visited—the data-traversal path—as a latent variable. Instead of applying a fixed 1D wavelet transform to a standard vectorization of an image, the model searches for an optimal permutation that maximizes "energy concentration" in the wavelet coefficients.

Permutation and vectorization induced by Recursive Dyadic Partitioning (RDP).

This is achieved through Recursive Dyadic Partitioning (RDP), where a tree-based structure partitions the multi-dimensional index space. By placing a prior distribution over these possible trees, the model adaptively "warps" the wavelet transform to match the data's geometry. For the Haar wavelet basis, the authors derived an exact recursive message passing algorithm that allows for posterior mean computation with a complexity of $O(n)$, where $n$ is the number of pixels. This "node-autonomy" of the Haar basis ensures that the model remains computationally efficient even for large-scale images.

Results and Performance

The authors evaluated WARP against several benchmarks, including natural images from ImageNet, the BSD68 dataset, and real-world retinal OCT scans.

Comparison of MSE and MAE across different noise levels for various denoising methods.

Key findings include:

  • Superior Accuracy: WARP consistently achieved lower Mean Squared Error (MSE) and Mean Absolute Error (MAE) than other adaptive methods like SHAH, AWS, and Wedgelets, particularly in high-noise scenarios where it even outperformed popular deep learning denoisers like DnCNN.
  • Computational Speed: WARP is significantly faster than competing adaptive approaches. For a $512 \times 512$ image, WARP required approximately 7.2 seconds, compared to 76.9 seconds for SHAH and over 30 minutes for dictionary learning methods like BPFA.
  • Energy Concentration: The model required 70-80% fewer wavelet coefficients than standard 2D wavelets to capture the same signal energy, demonstrating a highly efficient data representation.

Conclusion

WARP provides a principled probabilistic framework for adaptive wavelet analysis. By combining the structural flexibility of recursive partitioning with the efficiency of 1D wavelet transforms, it achieves state-of-the-art performance in image reconstruction and denoising. Future work aims to extend the exact $O(n)$ solution beyond the Haar basis and explore the framework's potential for revolutionary advancements in image compression.

Summary updated

Abstract

Traditional statistical wavelet analysis that carries out modeling and inference based on wavelet coefficients under a given, predetermined wavelet transform can quickly lose efficiency in multivariate problems, because such wavelet transforms, which are typically symmetric with respect to the dimensions, cannot adaptively exploit the energy distribution in a problem-specific manner. We introduce a principled probabilistic framework for incorporating such adaptivity---by (i) representing multivariate functions using one-dimensional (1D) wavelet transforms applied to a permuted version of the original function, and (ii) placing a prior on the corresponding permutation, thereby forming a mixture of permuted 1D wavelet transforms. Such a representation can achieve substantially better energy concentration in the wavelet coefficients. In particular, when combined with the Haar basis, we show that exact Bayesian inference under the model can be achieved analytically through a recursive message passing algorithm with a computational complexity that scales linearly with sample size. In addition, we propose a sequential Monte Carlo (SMC) inference algorithm for other wavelet bases using the exact Haar solution as the proposal. We demonstrate that with this framework even simple 1D Haar wavelets can achieve excellent performance in both 2D and 3D image reconstruction via numerical experiments, outperforming state-of-the-art multidimensional wavelet-based methods especially in low signal-to-noise ratio settings, at a fraction of the computational cost.
BibTeX
@article{li2021partition,
  author = {Meng Li and Li Ma},
  title = {{Partition mixture of 1D wavelets for multi-dimensional data}},
  journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
  year = {2021},
  doi = {10.1109/tpami.2021.3110403},
}
Figure