A wavelet Plancherel theory with application to sparse continuous wavelet transform

Ron Levie, Nir A. SochenarXiv 2017 · arXiv · OpenReview

Abstract

Continuous wavelet theory is extended to enable efficient implementation of multiplicative operators in the coefficient space. By embedding the signal space into a larger "window-signal space," we establish the Wavelet-Plancherel Transform as an isometric isomorphism. This framework allows complex 2D phase-space operations to be "pulled back" into a 1D representation, enabling a new algorithm (WP4) that finds large wavelet coefficients in $O(N \log N)$ time, significantly improving upon the $O(N^2 \log N)$ complexity of traditional high-resolution grid searches.

Introduction

In signal processing, the Fourier transform is an isomorphism, allowing seamless movement between time and frequency domains. However, the Continuous Wavelet Transform (CWT) typically maps a 1D signal into a redundant 2D phase space (time-scale). Because the CWT is not "onto," the resulting coefficients fill only a small, often "blurry" subspace, making it difficult to apply filters or perform sparse approximations directly in the phase space without heavy computational overhead. Traditionally, processing a signal of length $N$ with high resolution requires $O(N^2 \log N)$ operations, which is prohibitive for large datasets.

Wavelet Plancherel Theory

The core innovation of this work is the definition of the window-signal space ($\mathcal{W} \otimes \mathcal{S}$). By expanding the input domain to include the window function as a variable, the wavelet transform is extended into the Wavelet-Plancherel Transform. This transform is a canonical isometric isomorphism between the window-signal space and the coefficient space $L^2(G)$.

The Wavelet-Plancherel Transform as an isometric isomorphism between the window-signal space and the coefficient space.

This isomorphism allows researchers to treat time and scale as operators (observables) and derive closed-form formulas to apply them directly within the window-signal space using functional calculus. Furthermore, the authors utilize a "slope" change of variables ($z = \omega' / \omega$) that simplifies the complex geometry of wavelet dilations into translations along slope rays, facilitating the solution of the underlying differential equations.

The WP4 Algorithm for Sparse Approximation

Leveraging this theory, we introduce the Wavelet Plancherel Phase-Space Projection Pursuit (WP4) algorithm. WP4 is a greedy matching pursuit method that avoids expensive 2D grid searches. Instead, it employs a bisection search that "projects" the signal onto increasingly smaller regions of the time-frequency plane. By representing the window-signal space using coarse B-splines for the window and fine grids for the signal, the algorithm maintains linear-logarithmic complexity.

Results and Computational Complexity

The WP4 algorithm achieves a resolution of $O(N^2)$ in phase space with only $O(N \log N)$ operations. This "resolution squaring" allows for high-precision signal analysis without the traditional quadratic cost. In practical tests, such as audio time-stretching (Wavelet Phase Vocoder), the method demonstrates superior handling of sharp transients (e.g., drum hits) compared to standard Short-Time Fourier Transform (STFT) approaches, as wavelets provide better temporal localization at high frequencies.

Conclusion and Future Work

Wavelet Plancherel Theory provides a robust mathematical framework for efficient phase-space operations. While the current implementation focuses on 1D signals, the underlying theory for semi-direct product groups suggests potential extensions to higher-dimensional data, such as 2D images via Shearlets. Future research will focus on the numerical stability of the bisection search and these multi-dimensional applications.

Summary updated

Abstract

We introduce an extension of continuous wavelet theory that enables an efficient implementation of multiplicative operators in the coefficient space. In the new theory, the signal space is embedded in a larger abstract signal space -- the so called window-signal space. There is a canonical extension of the wavelet transform to an isometric isomorphism between the window-signal space and the coefficient space. Hence, the new framework is called a wavelet-Plancherel theory, and the extended wavelet transform is called the wavelet-Plancherel transform. Since the wavelet-Plancherel transform is an isometric isomorphism, any operation in the coefficient space can be pulled-back to an operation in the window-signal space. It is then possible to improve the computational complexity of methods that involve a multiplicative operator in the coefficient space, by performing all computations directly in the window-signal space. As one example application, we show how continuous wavelet multipliers (also called Calder\'{o}n-Toeplitz Operators), with polynomial symbols, can be implemented with linear complexity in the resolution of the 1D signal. As another example, we develop a framework for efficiently computing greedy sparse approximations to signals based on elements of continuous wavelet systems.
BibTeX
@misc{levie2017wavelet,
  author = {Ron Levie and Nir A. Sochen},
  title = {{A wavelet Plancherel theory with application to sparse continuous wavelet transform}},
  year = {2017},
  eprint = {1712.02770},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1712.02770},
}
Figure