Zur Hauptnavigation / To main navigation

Zur Sekundärnavigation / To secondary navigation

Zum Inhalt dieser Seite / To the content of this page

  • EN

Hauptnavigation / Main Navigation

Sekundärnavigation / Secondary navigation

The Multivariate Periodic Anisotropic Wavelet Library

Inhaltsbereich / Content

The Multivariate Periodic Anisotropic Wavelet Library

Abstract

The following few sections introduce the basic notation and terminology used throughout the MPAWL in order to follow the function names and examples provided. For more details see the literature below or you can directly go to the download section.

Pattern and Generating Set

The pattern \(\mathcal P(\mathbf{M})\), \(\mathbf M = {\small\begin{pmatrix} 8 & -4\\0&16\end{pmatrix}}\)

For a regular matrix \(\mathbf{M}\in\mathbb Z^{d\times d}\) the corresponding lattice is given by \(\Lambda(\mathbf{M}) := \mathbf{M}^{-1}\mathbb Z^d\), which posesses \(\mathbb Z^d\) as a subset and hence is \(1\)-periodic. In other words, the set \(\mathcal P(\mathbf{M}) := \Lambda(\mathbf{M})\cap [0,1)^d \), also called the pattern generalizes the equidistant points on the (one dimensional) unit interval, see the figure on the right. Similarly, the generating set \(\mathcal G(\mathbf{M}) := \mathbf{M}\mathcal P(\mathbf{M}) = \bigl\{\mathbf{k}\in\mathbb Z^d\,:\, \mathbf{M}^{-1}\mathbf{k}\in\mathcal P(\mathbf{M})\bigr\} \) generalizes the set of integers \(\{0,1,\ldots,N-1\}\), which can also be seen as congreunce class representants with respect to \(\bmod N\) on the integers. This concept is generalised by the generating set \(\mathcal G(\mathbf{M})\) into the integer valued vectors and the congruence with respect to \(\mathbf{M}\), which is given by\[\mathbf{k}\equiv\mathbf{h}\bmod\mathbf{M} \Leftrightarrow \exists \mathbf{z}\in\mathbb Z^d\,:\,\mathbf{h} = \mathbf{k} + \mathbf{M}\mathbf{z}\text{.}\]

The MPAWL provides functions to generate both these sets \(\mathcal P(\mathbf{M})\) and \(\mathcal G(\mathbf{M})\) and basis to adress elements in an ordered way.

Translation Invariant Spaces

Sampling a function on the pattern \(2\pi\mathcal P(\mathbf{M})\) from the figure above.

In the MPAWL the shifts \(T_{\mathbf{y}}f := f(\circ-2\pi\mathbf{y}) \), \(\mathbf{y}\in\mathcal P(\mathbf{M})\), of a multivariate \(2\pi\)-periodic function \(f: \mathbb T^d \to\mathbb C \), \(\mathbb T^d \cong [-\pi,\pi)^d\), \(d\in\mathbb N\), are used to define shift invariant spaces, depending on \(\mathbf{M}\) and \(f\) defined by \[ V_{\mathbf{M}}^{f} := \,\mathrm{span}\;\bigl\{ T_{\mathbf{y}}f\,;\,\mathbf{y}\in\mathcal P(\mathbf{M})\bigr\}\text{,} \]

i.e. each function \(g\in V_{\mathbf{M}}^{f}\) can be written as a weighted sum of the translates \[ g = \sum_{\mathbf{y}\in\mathcal P(\mathbf{M})} a_{\mathbf{y}}T_{\mathbf{y}}f,\qquad\text{where each } a_{\mathbf{y}}\in\mathbb C,\ \mathbf{y}\in\mathcal P(\mathbf{M})\text{.} \] For any function \(f\in L_2(\mathbb T^d) \) the library provides functions to work in or with the corresponding translation invariant space \(V_{\mathbf{M}}^{f}\) with respect to any regular matrix \(\mathbf{M}\) this includes

  • finding a function \(f^{\text{on}}\in V_{\mathbf{M}}^{f}\), whose translates form an orthonormal basis of \(V_{\mathbf{M}}^{f}\)
  • computing the bracket sums and attenuation factors of \(f\) with respect to \(\mathbf{M}\)
  • sampling a function \(g\in V_{\mathbf{M}}^{f}\) at the points \(2\pi\mathbf{y}\), \(\mathbf y \in \mathcal P(\mathbf{M})\), i.e. obtaining the data values \(d_{\mathbf{y}} = g(2\pi\mathbf{y}) \) and finding the coefficients with respect to the translates of \(f\)

Most of these algorithms use the characterization of the shift invariant spaces in the Fourier domain, i.e. with respect to the Fourier coefficients \(c_{\mathbf{k}}(f) := \langle f,\textrm{e}^{\textrm{i}\mathbf{k}^\text{T}\circ}\rangle \) of \(f\in L_2(\mathbb T^d)\).

Fast Fourier Transform

Besides the introduction of sampling methods for arbitrary multivariate \(2\pi\)-periodic functions — or usual functions sampled on \(\mathbb T^d\)—, the MPAWL also introduces a Fourier transform on arbitrary sampling lattices \(2\pi\mathcal P(\mathbf{M})\), which yields discrete Fourier coefficients \(c_{\mathbf{h}}^{\mathbf{M}}\), \(\mathbf{h}\in\mathcal G(\mathbf{M}^{\text{T}})\). Using the Smith Normal Form of a regular integer matrix, the Fourier transform on the pattern can be computed as a kronecker product of at most \(d\) one dimensional Fourier transforms, where the actual number of Fourier transforms depends on the rank of the lattice \(\Lambda(\mathbf{M})\).

Fast Wavelet Transform

If the regular integral matrix \(\mathbf{M}\) posesses a factorization \(\mathbf{M} = \mathbf{J}\mathbf{N}\), we obtain a subpattern \(\mathcal P(\mathbf{N})\subseteq\mathcal P(\mathbf{M})\), where \(|\mathcal P(\mathbf{M})| = |\det\mathbf{J}|\cdot|\mathcal P(\mathbf{N})|\). Especially for the dyadic decomposition, i.e. \(|\det\mathbf{J}|=2\), the pattern of \(\mathbf{M}\) is bisected.

For a function \(\xi\in L_2(\mathbb T^d)\) such that \(\dim V_{\mathbf{M}}^{\xi} = m = |\det\mathbf{M}|\) and a second function \(\varphi\) such that for a factorization \(\mathbf{M} = \mathbf{J}\mathbf{N}\) we have \(\dim V_{\mathbf{N}}^{\varphi} = \frac{m}{2}\) or in other words the translates \(T_{\mathbf x}\varphi\), \(\mathbf{x}\in \mathcal P (\mathbf{N})\), are linearly independent, we obtain an orthogonal deconposition \[ V_{\mathbf{M}}^{\xi} = V_{\mathbf{N}}^{\varphi} \oplus V_{\mathbf{N}}^{\psi}\text{,} \]

where the second function \(\psi\), whose translates span the orthogonal complement of \(V_{\mathbf{N}}^{\varphi}\), can be computed directly, because it is unique up to scaling. For this setting of an dyadic decomposition, the package provides a fast decompostion algorithm for a function \(f\in V_{\mathbf{M}}^{\xi}\) to be decomposed into the two parts \( f = f_1+f_2\), where \(f_1\in V_{\mathbf{N}}^{\varphi}\) and \(f_2\in V_{\mathbf{N}}^{\psi}\).

De la Vallée Poussin Wavelets

A de la Vallée Poussin type wavelet.

Taking a d-dimensional Box spline \(B_{\mathbf{\Xi}}\), where the collection \(\mathbf{\Xi}\) includes \(d\) linear independet vectors, e.g. the unit vectors, the de la Vallée Poussin means are defined in their Fourier coefficients taking certain samplings of the Box spline \(B_{\mathbf\Theta}(\mathbf{M}^{\text{T}}\circ)\) or a sum of shifts of this Box spline.

For certain box splines, these generalized de la Vallée Poussin means even provide an MRA, but starting from a certain sampling and decomposing a certain function works for all of them.

The library provides several functions to define and work with these multivariate generalizations of the de la Vallée Poussin means and their corresponding wavelets.

Download

The software is available as a Mathematica-package at the Wolfram Archive Library or at GitHub, where you can also get a version including the PDF files of the examples. The software was developed using Mathematica 9.0.1 and is published under the GPL 3.

Literature

[1] R. Bergmann, J. Prestin (2015).
Multivariate periodic wavelets of de la Vallée Poussin type.
Journal of Fourier Analysis and Applications, 21(2), 342–369. doi, pdf (ArXiv).

[2] R. Bergmann, J. Prestin (2014).
Multivariate anisotropic interpolation on the torus.
in: G. Fasshauer and L. Schumaker (eds.). Approximation Theory XIV: San Antonio 2013. 27–44. doi, pdf (ArXiv).

[3] R. Bergmann (2013).
The fast Fourier transform and fast wavelet transform for patterns on the torus.
Applied and Computational Harmonic Analysis, 35(1), 39–51. doi, pdf (ArXiv).

[4] R. Bergmann (2013).
Translationsinvariante Räume multivariater anisotroper Funktionen auf dem Torus. (Translation invariant spaces of multivariate anisotropic functions on the torus, german)
Dissertation, University of Lübeck, Shaker Verlag, 2013, pdf.

[5] D. Langemann, J. Prestin (2010).
Multivariate periodic wavelet analysis.
Applied and Computational Harmonic Analysis, 28(1), 46–66. doi