Wavelet bi-frames with few generators from multivariate refinable functions

Martin Ehler, Bin HanApplied and Computational Harmonic Analysis 2008 · DOI

TL;DR

This paper presents a novel method for constructing wavelet bi-frames with a significantly reduced number of generators, particularly for multivariate settings. By leveraging algebraic tools like syzygy modules and removing restrictive assumptions from prior work, the authors achieve more efficient wavelet systems, especially for box spline functions, which are crucial in signal and image processing.

What Problem Does This Paper Address?

Wavelet analysis is a powerful tool for signal and image processing, but constructing efficient wavelet systems, especially in higher dimensions, can be challenging. Orthonormal wavelet bases offer efficiency but lack flexibility. Biorthogonal wavelet bases provide more flexibility but can suffer from strong coupling between primal and dual wavelets, leading to inconvenient side effects. Wavelet frames offer a solution by allowing redundancy, decoupling primal and dual functions, and enabling greater flexibility in designing wavelets with desired properties like small support and high smoothness.

However, existing methods for constructing multivariate wavelet bi-frames often require a large number of generators (the building blocks of the wavelet system). This increases computational complexity. Furthermore, many previous approaches relied on strong assumptions, such as the refinable function being "fundamental" (a specific property related to its sampling) and its mask having a particular factorization, which are not met by many commonly used functions like box splines. This paper aims to overcome these limitations by developing a more general construction method that yields wavelet bi-frames with fewer generators, even for functions like box splines that don't satisfy the restrictive prior assumptions.

Methods

The core of this paper lies in a two-step construction strategy for wavelet bi-frames, building upon existing work but crucially removing restrictive assumptions. The method relies on the properties of multivariate refinable functions and their associated masks, which are represented by Laurent polynomials.

  1. General Setting and Wavelet Bi-frame Definition: The paper begins by defining wavelet frames and bi-frames in the context of multivariate refinable functions and dilation matrices. A wavelet frame is a collection of functions whose integer shifts and dilates form a frame, meaning they can represent any signal with bounded redundancy. A wavelet bi-frame involves two such collections, a primal and a dual, that allow for perfect reconstruction.
  2. Two-Step Construction Recipe: The authors adapt a construction recipe from prior work ([8]). This recipe involves finding auxiliary "wavelet symbols" (related to the masks of the wavelets) that satisfy specific algebraic conditions (conditions (S1) and (S2)). The key innovation here is the removal of the assumption that the refinable function must be fundamental and its mask must have a specific factorization.
  3. Algebraic Tools for Condition (S1): To satisfy condition (S1), which relates to the primal and dual wavelet symbols, the paper employs the concept of syzygy modules. These are algebraic structures that describe relationships between polynomials. The solvability of (S1) is linked to the properties of syzygy modules of the mask polynomials. The authors show that if the syzygy module of the primal or dual mask polynomial is generated by a small number of elements (specifically, $m-1$, where $m$ is the determinant of the dilation matrix), then (S1) is solvable with a minimal number of generators ($n_1 = m-1$). They also discuss conditions under which these syzygy modules are free, simplifying the problem.
  4. Algebraic Tools for Condition (S2): Condition (S2) deals with constructing the remaining wavelet symbols. This is achieved by analyzing the structure of a specific Laurent polynomial, $\eta(z)$, which is derived from the primal and dual mask polynomials. The paper shows that if $\eta(z)$ has a zero of order at least 2 at $z=1$, then (S2) is solvable with $n_2 = d$ generators (where $d$ is the dimension).
  5. Vanishing Moments: The paper also addresses how their construction method preserves or enhances vanishing moments of the wavelets. Vanishing moments are crucial for achieving high approximation orders in signal decomposition. They demonstrate that their approach allows for transforming the sum rule orders of the refinable functions into vanishing moments of the constructed wavelets.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and applies them to well-known mathematical objects (box splines) rather than empirical datasets.

Key Insights and Ideas

  • Generalization via Algebraic Conditions: The paper's main contribution is a generalized construction for wavelet bi-frames by reformulating the problem in terms of algebraic conditions on polynomial symbols and then solving these conditions using syzygy modules. This removes the need for restrictive assumptions like the "fundamental" property of refinable functions.
  • Syzygy Modules for Generator Reduction: The use of syzygy modules is a key insight. By understanding the structure of these modules, the authors can determine when condition (S1) can be satisfied with a minimal number of generators ($n_1 = m-1$), directly leading to fewer generators in the final wavelet bi-frame.
  • Box Splines as a Prime Target: The paper explicitly targets box splines, a fundamental class of multivariate refinable functions. The developed method significantly outperforms previous constructions for box splines in terms of the number of generators.
  • Flexibility in Vanishing Moments: The construction allows for control over vanishing moments, enabling the design of wavelets suitable for high-order approximation, a critical aspect for signal and image analysis.
  • Connection to Algebraic Geometry: The reliance on concepts like Laurent polynomials, unique factorization domains, and syzygy modules highlights the deep connection between wavelet theory and abstract algebra.

Key Results

  • Fewer Generators for Wavelet Bi-frames: The primary result is the ability to construct compactly supported wavelet bi-frames with significantly fewer generators compared to previous methods, especially for multivariate settings and box splines.
  • Minimal Generators for (S1): The paper establishes that condition (S1) can be solved with $n_1 = m-1$ generators (where $m = |\det(M)|$) if the syzygy module of the primal or dual mask polynomial is generated by $m-1$ elements.
  • Minimal Generators for (S2): Condition (S2) can be solved with $n_2 = d$ generators (where $d$ is the dimension) if the relevant polynomial $\eta(z)$ has a zero of order at least 2 at $z=1$.
  • Practical Examples with Box Splines: The paper provides concrete examples for 3- and 4-directional box splines, demonstrating that their approach yields bi-frames with at most 5 generators, a substantial reduction from the 6 to 80+ generators required by prior methods. For instance, a 3-directional box spline with multiplicity 2 results in a bi-frame with 5 generators, and a trivariate box spline leads to 10 generators.

Limitations and Future Work

  • Computational Complexity of Syzygy Modules: While the theoretical framework is powerful, computing syzygy modules can be computationally intensive for very high-dimensional problems or complex polynomials. The paper mentions the use of computer algebra software (like Singular) for verification, suggesting that practical implementation might rely on such tools.
  • Existence of $\eta(z)$ for (S2): The solvability of (S2) depends on the existence of specific polynomial factors for $\eta(z)$. While the paper provides conditions and examples, a general guarantee for all possible refinable functions might be complex.
  • Future Work: The authors suggest exploring further applications of their method to other classes of refinable functions and investigating specific optimality conditions (like smoothness or support size) for the constructed wavelet bi-frames. They also hint at the possibility of further reducing the number of generators in specific cases, as seen in their examples. The paper also implicitly points towards the need for efficient algorithms to compute syzygy modules in practice.

Summary updated

BibTeX
@inproceedings{ehler2008wavelet,
  author = {Martin Ehler and Bin Han},
  title = {{Wavelet bi-frames with few generators from multivariate refinable functions}},
  booktitle = {Applied and Computational Harmonic Analysis},
  year = {2008},
  doi = {10.1016/j.acha.2008.04.003},
}
Figure