and Multiresolution Analysis

(1)

Here, t ₊ ^mdenotes the one-sided power function, i.e., t ₊ ^m= 0 for t < 0 and t ₊ ^m= t ^mfor t ≥ 0. The B-splines β ^mcan be easily generated by an iterative process. Let β ⁰(t) = χ _{[0, 1)}(t) be the characteristic function of the interval [0, 1). Then the B-spline of degree m is derived by the convolution product

$\displaystyle{ \beta ^{m} =\beta ^{0} {\ast}\beta ^{m-1} =\mathop{\underbrace{ \beta ^{0} {\ast}\ldots {\ast}\beta ^{0}}}\limits _{ m+1\mbox{ -times}}\quad \mbox{ for}\;m \in \; \mathbb{N}, }$

(2)

where

$\displaystyle{\beta ^{0} {\ast}\beta ^{m-1}(x) =\int _{ \mathbb{R}}\beta ^{0}(y)\beta ^{m-1}(x - y)\mathit{dy} =\int _{ 0}^{1}\beta ^{m-1}(x - y)\mathit{dy}.}$

For an illustration of the cardinal B-splines , see Fig. 1.

Fig. 1

Cardinal B-splines of degree m = 0, …, 4

Splines had their second breakthrough as Battle [4] and Lemarié [38] discovered that B-splines generate multiresolution analyses . The simple form of the B-splines and their compact support, in particular, were convenient for designing multiresolution algorithms and fast implementations.

Definition 1.

Let $A: \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}$ be a linear mapping that leaves $\mathbb{Z}^{n}$ invariant, i.e., $A(\mathbb{Z}^{n}) \subset \mathbb{Z}^{n}$ and that has (real or complex) eigenvalues with absolute values greater than 1.

A multiresolution analysis associated with the dilation matrix A is a sequence of nested subspaces $(V _{j})_{j\in \mathbb{Z}}$ of $L^{2}(\mathbb{R}^{n})$ such that the following conditions hold:

(i)

$\ldots \subset V _{-1} \subset V _{0} \subset V _{1} \subset \ldots$ ,

(ii)

$\cap _{j\in \mathbb{Z}}V _{j} =$ {0},

(iii)

Span $\cup _{j\in \mathbb{Z}}V _{j}$ is dense in L²( $\mathbb{R}^{n})$ ,

(iv)

$f \in V _{j} \Leftrightarrow f(A^{-j}\cdot ) \in V _{0}$ ,

(v)

$f \in V _{0} \Leftrightarrow f(\cdot - k) \in V _{0}$ for all $k \in \mathbb{Z}^{n}$ .

(vi)

There exists a so-called scaling function ϕ ∈ V ₀ such that the family $\{\phi (\bullet -k)\}_{k\in \mathbb{Z}^{n}}$ of translates of ϕ forms a Riesz basis of V ₀.

Here, $L^{2}(\mathbb{R}^{n})$ denotes the vector space of square-integrable functions f: $\mathbb{R}^{n} \rightarrow \mathbb{C}$ with norm

$\displaystyle{\Vert f\Vert _{2} = \left (\int _{\mathbb{R}^{n}}\vert f(x)\vert ^{2}\mathit{dx}\right )^{\frac{1} {2} }}$

and corresponding inner product

$\displaystyle{\langle f,g\rangle =\int _{\mathbb{R}^{n}}f(x)\overline{g(x)}\;\mathit{dx},}$

where $\bar{g}$ denotes the complex conjugate of g. The elements in $L^{2}(\mathbb{R}^{n})$ are also called functions of finite energy.

Riesz bases are a slightly more general concept than orthonormal bases. In fact, Riesz bases are equivalent to orthonormal bases and therefore can be generated by applying a topological isomorphism on some orthonormal basis.

Definition 2.

A sequence of functions{f _n} $_{n\in \mathbb{Z}}$ in a Hilbert space V is called a Riesz sequence if there exist positive constants A and B, the Riesz bounds, such that

$\displaystyle{A\Vert c\Vert _{l^{2}} \leq \left \|\sum \nolimits _{k\in \mathbb{Z}^{n}}c_{k}f_{k}\right \|_{V } \leq B\Vert c\Vert _{l^{2}}}$

for all scalar sequences $C = (c_{k})_{k\in \mathbb{Z}^{n}} \subset l^{2}(\mathbb{Z}^{n})$ .

A Riesz sequence is called a Riesz basis if it additionally spans the space V.

A good introduction to Riesz bases, their properties, and their relation to orthonormal bases is given in the monography by Young [75]. Multiresolution constructions with splines are treated in numerous sources. As a starting point, there are, e.g., the books by Christensen [13, 14] and Wojtaszczyk [74].

The mathematical properties in Definition 1 have intuitive interpretations. A function $f \in L^{2}(\mathbb{R}^{n})$ , which is projected orthogonally on V _j, is approximated with the so-called resolution A ^j. In fact, let

$\displaystyle{P_{j}: L^{2}(\mathbb{R}^{n}) \rightarrow V _{ j}}$

denote the orthogonal projection operator. Then (ii) yields that by going to lower resolutions, all details are lost:

$\displaystyle{\mathop{\lim }\limits _{j\rightarrow -\infty }\left \Vert P_{j}f\right \Vert \; = 0.}$

In contrast, when the resolution is increased, j → ∞, more and more details are added. By (iii), the projection then converges to the original function f:

$\displaystyle{\mathop{\lim }\limits _{j\rightarrow \infty }\left \Vert f - P_{j}f\right \Vert \; = 0.}$

Hereby, the rate of convergence depends on the regularity of f.

The approximation spaces V _jare nested, which allows for computing coarser approximations in V _kfor k < j for functions f ∈ V _j. The scaling A ^kenlarges details. Property (iv) shows that the approximation spaces have a similar structure over the scales and emanate from one another. The translation invariance (v) ensures that the analysis of a function in V _jis independent of the starting time or location.

And property (vi) finally ensures the beautiful and mighty property that the whole sequence of nested approximation spaces can be generated by translates and scalings of one single function – the scaling function .In fact, (vi) together with (iv) yields that

$\displaystyle{\{\phi (A^{j}\bullet - k),k \in \; \mathbb{Z}^{n}\}}$

is a Riesz basis for V _j.

While moving from the coarser approximation space V _jto the finer, larger space V _j+1, information has to be added. In fact, there is an orthogonal complement W _j, $j \in \mathbb{Z}$ , such that

$\displaystyle{V _{j+1} = V _{j} \oplus W_{j}.}$

These spaces are called detail spaces or wavelet spaces. It is well known that these spaces also possess a Riesz basis spanned by shifts of $\vert$ detA | − 1 generators, the wavelets ψ ₁, …, ψ _{| detA | −1}. Here, A is the dilation matrix in Definition 1. The wavelets can be constructed from the scaling function. As a consequence, the knowledge of just the single function ϕ allows for the construction of the approximation spaces V _jand for the wavelet spaces W _j. Detailed information on the generation of wavelets and their properties can be found in various books, e.g., [16, 21, 41, 44, 74].

Example 1.

A simple example for a multiresolution analysis on $L^{2}(\mathbb{R})$ is given by piecewise constant functions. Consider the characteristic function ϕ = χ _{[0, 1)} of the interval semi-open interval [0, 1). Then ϕ generates a dyadic multiresolution analysis, i.e., for A = 2. The approximation spaces are

$\displaystyle{V _{j} = \overline{\mbox{ span}\;\{\chi _{[0,1)}(2^{j}\bullet - k)\}_{k\in \mathbb{Z}}}^{L^{2}(\mathbb{R}) }.}$

They consist of functions constant on intervals of the form [k2^−j, (k + 1)2^−j). The spaces are obviously nested and separate $L^{2}(\mathbb{R})$ in the sense of Definition 1 (ii). Since piecewise constant functions with compact support are dense in $L^{2}(\mathbb{R})$ , (iii) holds. (iv) – (vi) hold by construction. In fact, this multiresolution analysis is generated by the B-spline β ⁰ as scaling function. The B-spline basis operates as mean-value operator over the support interval. The corresponding wavelet extracts the details, i.e., the deviation from the mean value. To this end, it operates as a difference operator. Figure 2 shows the scaling function β ⁰ and the corresponding wavelet, the so-called Haar wavelet. In Fig. 3, an example of a multiresolution is given.

Fig. 2

Left: The B-spline β ⁰ is a scaling function and operates as mean value. Right: The corresponding wavelet, the Haar wavelet, operates as a local difference operator

Fig. 3

Multiresolution decomposition of the step function (a) with β ⁰ as scaling function and with the Haar wavelet. The approximations (left column) are further iterated and decomposed into a coarser approximation and details (right column), until the coarsest approximation step, here the mean value, is reached. The sum of the coarsest approximation in the third iteration and of all details yields the original function (a). No information is lost in a multiresolution decomposition

2 Historical Notes

The idea of piecewise polynomial functions and splines goes back to Schoenberg [59, 60]. In the 1960s, when computer power started to be used for numerical procedures such as data fitting, interpolation, solving differential equations, and computer-aided geometric design, splines experienced an extreme upsurge. Schoenberg invented and strongly contributed to the concept of cardinal splines, which have equidistant nodes on the integers; see, e.g., [40, 61, 62] and many more.

As a parallel development, in the 1980s, the adaption of signal resolution to only process relevant details for a particular task evolved. For example, for computer vision, a multiresolution pyramid was introduced by Burt and Adelson [8]. It allowed to process an image first on a low-resolution level and then selectively increase the resolution and add more detailed information when needed. The definition of a dyadic multiresolution analysis , i.e., A = 2Id, was contributed by Mallat [43] and Meyer [46]. An interesting and in some parts historical collection on the most important articles in multiresolution and wavelet theory was assembled by Heil and Walnut [33].

The concepts of splines and multiresolution were joined by Lemarié [38] and Battle [4], when they showed that cardinal B-splines are scaling functions for multiresolution analyses. This led to many more developments of piecewise polynomial scaling functions for various settings and also multidimensions [15], as, e.g., polyharmonic B-splines [53, 54] and other functions inspired from radial basis functions [7].

In 1989, S. Mallat published his famous algorithm for multiresolution and wavelet analysis [43]. He had developed an efficient numerical method such that multiresolution decompositions could be calculated in a fast way. For the splines, M. Unser et al. proposed a fast implementation [66, 68, 69] which strongly contributed to the breakthrough of splines for signal and image analysis. In the last years, periodic, fractional, and complex versions of splines for multiresolution were developed, e.g., [11, 27, 28, 51, 65]. Many of them use a Fourier domain filter algorithm which allows for infinite impulse response filters. The former important feature of compact support of the cardinal B-splines and other functions is no longer a limiting criterion. Therefore, it can be expected that many new contributions on splines will still be made in the future by modeling signal and image features in Fourier domain.

3 Fourier Transform, Multiresolution, Splines, and Wavelets

Mathematical Foundations

Regularity and Decay Under the Fourier Transform

An important idea behind splines and multiresolution is the relation between regularity in time domain and decay in frequency domain and, respectively, between decay in time domain and regularity in frequency domain. To illustrate this, the notion of the Schwartz space is very useful [10, 34, 56, 63].

Definition 3.

The subspace of functions $f \in C^{\infty }(\mathbb{R}^{n})$ with

$\displaystyle{\mathop{\sup }\limits _{\vert \alpha \vert \leq N}\mathop{ \sup }\limits _{x\in \mathbb{R}^{n}}(1 +\Vert x\Vert ^{2})^{N}\vert D^{\alpha }f(x)\vert \; <\; \infty \quad \mbox{ for}\;\mbox{ all}\;N = 0,\;1,\;2,\;\ldots }$

is called the space of rapidly decreasing functions or Schwartz space $\mathcal{S}(\mathbb{R}^{n})$ . The norms induce a Fréchet space topology, i.e., the space $\mathcal{S}(\mathbb{R}^{n})$ is complete and metrizable.

Here, $D^{\alpha } = \left ( \frac{\partial } {\partial x_{1}} \right )^{\alpha _{1}}\cdots \left ( \frac{\partial } {\partial x_{n}}\right )^{\alpha _{n}}$ for every multi-index $\alpha = (\alpha _{1},\ldots,\alpha _{n}) \in \; \mathbb{N}_{o}^{n}$ .

The dual space $\mathcal{S}^{{\prime}}(\mathbb{R}^{n})$ , endowed with the weak-* topology, is called space of tempered distributions.

The following famous linear transform relates the viewpoints of the space domain and of the frequency domain:

Definition 4.

The Fourier transform, defined by

$\displaystyle{\mathcal{F}f(\omega ):=\hat{ f}(\omega ):=\int _{\mathbb{R}^{n}}f(x)e^{-i\langle \omega,x\rangle }dx,\quad \omega \in \; \mathbb{R}^{n},}$

is a topological isomorphism on $L^{2}(\mathbb{R}^{n})$ and on $\mathcal{S}(\mathbb{R}^{n})$ . Its inverse is given by

$\displaystyle{f(x) = \frac{1} {(2\pi )^{n}}\int _{\mathbb{R}^{n}}\hat{f}(\omega )e^{i\langle \omega,x\rangle }d\omega \quad \mbox{ in}\;L^{2}(\mathbb{R}^{n})\;\mbox{ resp}.\;\mbox{ in}\;\mathcal{S}(\mathbb{R}^{n}).}$

The Fourier transform can be extended to the space of tempered distributions. For $T \in \mathcal{S}^{{\prime}}(\mathbb{R}^{n})$ , the Fourier transform is defined in a weak sense as

$\displaystyle{\mathcal{F}T(\phi ):\;=\hat{ T}(\phi ):\;= T(\hat{\phi })\;\mbox{ for}\;\mbox{ all}\;\phi \in \;\mathcal{S}(\mathbb{R}^{n}).}$

Also on $\mathbb{S}^{{\prime}}(\mathbb{R}^{n})$ , the Fourier transform is a topological isomorphism.

The Fourier transform has the nice property to relate polynomials and differential operators.

Theorem 1.

(i)

Let $f \in \mathcal{S}(\mathbb{R})$ . Then for all $k \in \mathbb{N}$

$\displaystyle{\mathcal{F}\left (f^{(k)}\right )(\omega ) = (i\omega )^{k}\hat{f}(\omega ),}$

and

$\displaystyle{\hat{f}^{(k)}(\omega ) = \mathcal{F}\left ((-i\bullet )^{k}f\right )(\omega ).}$

(ii)

Let P be an algebraic polynomial in $\mathbb{R}^{n}$ , say $P(x) =\sum \nolimits _{\alpha }c_{\alpha }x_{1}^{\alpha _{1}}\ldots x_{n}^{\alpha _{n}}$ , and let $f \in \mathcal{S}(\mathbb{R}^{n})$ . Then

$\displaystyle{\mathcal{F}\left (P\left (\frac{1} {i} D\right )f\right ) = P\hat{f}\quad \mbox{ and}\quad \widehat{Pf} = P(iD)\hat{f},}$

where $P(iD) =\sum \nolimits _{\alpha }c_{\alpha }i^{\vert \alpha \vert }D^{\alpha }$ .

(iii)

Part (ii) also holds for $f \in \mathcal{S}^{{\prime}}(\mathbb{R}^{n})$ .

Example 2.

The Fourier transform of the polynomial x ^kis the tempered distribution $i^{k} \frac{d^{k}} {dx^{k}}\delta$ , $k \in \mathbb{N}_{0}$ .

For the construction of a multiresolution analysis, the scaling function can be used as a starting point. The idea is to choose a scaling function of a certain regularity, such that the generated multiresolution analysis inherits the smoothness properties. In particular, for the splines, the idea is to model the regularity via decay in Fourier domain. The following theorem gives a motivation for this. The result can be deduced from the considerations above, and the fact that $\mathcal{S}(\mathbb{R}^{n})$ is dense in $L^{2}(\mathbb{R}^{n})$ :

Theorem 2.

Let $f \in L^{2}(\mathbb{R}^{n})$ and its Fourier-transform decay as

$\displaystyle{\vert \hat{f}(\omega )\vert \; \leq C(1+ \parallel \omega \parallel )^{-N-\epsilon }}$

for some $$$\varepsilon > 0$$” src=”/wp-content/uploads/2016/04/A183156_2_En_28_Chapter_IEq48.gif”></SPAN>. <SPAN class=EmphasisTypeItalic>Then all partial derivatives of order ≤N − n are continuous and in</SPAN> <SPAN id=IEq49 class=InlineEquation><IMG alt=$$L^{2}(\mathbb{R}^{n})$$ src=$ .

These results allow to construct a scaling function with explicit regularity and decay properties, in space and in frequency domain. However, some criteria are needed to verify that the constructed function generates a multiresolution analysis.

Criteria for Riesz Sequences and Multiresolution Analyses

The following is an explicit criterion to verify whether some function ϕ is a scaling function.

Theorem 3.

Let A be a dilation matrix and let $\phi \in L^{2}(\mathbb{R}^{n})$ be some function satisfying the following properties:

(i)

$\{\phi (\bullet -k)\}_{k\in \mathbb{Z}^{n}}$ is a Riesz sequence in $L^{2}(\mathbb{R}^{n})$ .

(ii)

ϕ satisfies a scaling relation. That is, there is a sequence of coefficients $(a_{k})_{k\in \mathbb{Z}^{n}}$ such that

$\displaystyle{ \phi (A^{-1}x) =\sum \nolimits _{ k\in \mathbb{Z}^{n}}a_{k}\phi (x + k)\quad \mathit{in}\;L^{2}(\mathbb{R}^{n}). }$

(3)

(iii)

$\vert \hat{\phi }\vert$ is continuous at 0 and $\hat{\phi }(0)\neq 0$ .

Then the spaces

$\displaystyle{V _{j} = \mbox{ span}\;\{\phi (A^{j}\bullet - k)\}_{ k\in \mathbb{Z}^{n}},\quad j \in \; \mathbb{Z},}$

form a multiresolution analysis of $L^{2}(\mathbb{R}^{n})$ with respect to the dilation matrix A.

Proof.

See, e.g., [74, Theorem 2.13] for the 1D case.

For particular applications, the Riesz basis property (i) of $\{\phi (\bullet -k)\}_{k\in \mathbb{Z}^{n}}$ in V ₀ is not enough, but an orthonormal basis is needed. An example for such an application is the denoising of signals contaminated with Gaussian white noise [44, Chap. X, Sect. 10.2.1]. However, there is an elegant mathematical method to orthonormalize Riesz bases generated by shifts of a single function.

Theorem 4.

Let $\phi \in L^{2}(\mathbb{R}^{n})$ . Then the following holds:

(i)

$\{\phi (\bullet -k)\}_{k\in \mathbb{Z}^{n}}$ is a Riesz sequence in $L^{2}(\mathbb{R}^{n})$ if and only if there are constants c and C, such that

$\displaystyle{0 < c \leq \sum \nolimits _{k\in \mathbb{Z}^{n}}\vert \hat{\phi }(\omega +2\pi k)\vert ^{2} \leq C < \infty \ \text{almost everywhere}.}$

That is, the autocorrelation filter $M(\omega ):=\sum \nolimits _{k\in \mathbb{Z}^{n}}\vert \hat{\phi }(\omega +2\pi k)\vert ^{2}$ is strictly positive and bounded from above.

(ii)

$\{\phi (\bullet -k)\}_{k\in \mathbb{Z}^{n}}$ is an orthonormal sequence if and only if

$\displaystyle{\sum \nolimits _{k\in \mathbb{Z}^{n}}\vert \hat{\phi }(\omega +2\pi k)\vert ^{2} = 1\ \text{almost everywhere}.}$

(iii)

If $\{\phi (\bullet -k)\}_{k\in \mathbb{Z}^{n}}$ is a Riesz basis of a subspace X of $L^{2}(\mathbb{R}^{n})$ , then there exists a function $\varPhi \in L^{2}(\mathbb{R}^{n})$ , namely,

$\displaystyle{ \hat{\varPhi }(\omega ) = \frac{\hat{\phi }(\omega )} {\sqrt{\sum \nolimits _{k\in \mathbb{Z}^{n } } \vert \hat{\phi }(\omega +2\pi k)\vert ^{2}}} }$

(4)

such that $\{\varPhi (\bullet -k)\}_{k\in \mathbb{Z}^{n}}$ is an orthonormal basis of X.

Proof.

See, e.g., [74] and [44, Chap. VII].

Due to this theorem, every scaling function can be orthonormalized. Let $\phi \in L^{2}(\mathbb{R}^{n})$ be some scaling function that generates a multiresolution analysis {V _j} $_{j\in \mathbb{Z}}$ of $L^{2}(\mathbb{R}^{n})$ . Then the family $\{\varPhi _{j,k}\}_{k\in \mathbb{Z}^{n}}$ with

$\displaystyle{\varPhi _{j,k}(x) = 2^{-j/2}\varPhi (2^{-j}(x - k)),}$

and Φ as defined in (4) is an orthonormal basis of the space $V _{j},j \in \mathbb{Z}$ .

Example 3.

A simple possibility to construct a dyadic multiresolution analysis in $L^{2}(\mathbb{R}^{n})$ is the tensor product approach. Let $(V _{j})_{j\in \mathbb{Z}}$ be a dyadic (i.e., A = 2) multiresolution analysis of $L^{2}(\mathbb{R})$ with scaling function ϕ. Then ( $\boldsymbol{V }_{j})_{j\in \mathbb{Z}}$ with $\boldsymbol{V }_{j} =\mathop{\underbrace{ V _{j} \otimes \cdots \otimes \; V _{j}}}\limits _{n-{\mathrm{times}}}$ together with the scaling function $\boldsymbol{\phi }(x_{1},\ldots,x_{n}) =\phi (x_{1}) \cdot \cdots \cdot \phi (x_{n})$ forms a multiresolution analysis of $L^{2}(\mathbb{R}^{n})$ and dilation matrix 2Id.

In the same way, the scaling function $\boldsymbol{\phi }(x_{1},\ldots,x_{n}) =\phi _{1}(x_{1}) \cdot \ldots \cdot \phi _{n}(x_{n})$ generates a multiresolution analysis of $L^{2}(\mathbb{R}^{n})$ , if every $\phi _{k},k = 1,\ldots,n$ , is a scaling function of some 1D multiresolution analysis with dilation factor $a \in \mathbb{N}\setminus$ {1}.

Regularity of Multiresolution Analysis

In signal and image analysis, the choice of an appropriate analysis basis is crucial. Here, appropriate means that the features of the basis such as smoothness should be in accordance with the properties of the functions to analyze. To give a blatant example: Analyzing a smooth signal or image with a fractal basis in general yields results that are difficult to interpret and to work with in practice. In this case, the signal resp. the image model does not match the model of the basis.

The next section will show that the family of spline bases helps to avoid such difficulties, because the splines allow for a good adjustment due to their regularity parameter m; cf. (1) and (2). The following definition specifies the term “regular.” (See [74].)

Definition 5.

Denote C ^rthe class of r-times continuously differentiable functions in $\mathbb{R}^{n},C^{0}$ the class of continuous functions, and C ⁻¹ the class of measurable functions.

(i)

Let r = −1, 0, 1, …. A function $f: \mathbb{R}^{n} \rightarrow \mathbb{C}$ is called r-regular, iff ∈ C ^rand

$\displaystyle{\left \vert \frac{\partial ^{\alpha }} {\partial x^{\alpha }}f(x)\right \vert \leq \frac{A_{k}} {(1 +\Vert x\Vert )^{k}}}$

for every $k \in \mathbb{N}_{0}$ , every multi-index α with | α | ≤ max(r, 0) and constants A _k.

(ii)

A multiresolution analysis of $L^{2}(\mathbb{R}^{n})$ is called r-regular if it is generated by an r-regular scaling function.

It is important to note that the orthonormalization procedure (4) does not affect the regularity of the corresponding basis. For the orthonormalized scaling function Φ of a multiresolution analysis, the same regularity properties hold.

Proposition 1.

Let $\phi \in L^{2}(\mathbb{R}^{n})$ be an r-regular function, such that $\{\phi (\bullet -k)\}_{k\in \mathbb{Z}^{n}}$ forms a Riesz sequence. Then the via (4) orthonormalized function Φ is also r-regular [ 74 ].

Order of Approximation

Having found a scaling function that generates a multiresolution analysis, how good do the corresponding approximation spaces V _japproximate some function $f \in L^{2}(\mathbb{R}^{n})$ of a certain regularity? Let

$\displaystyle{H^{k}(\mathbb{R}^{n}) =\{ f \in L^{2}(\mathbb{R}^{n}):\;\Vert f\Vert _{ H^{k}}:\;= \frac{1} {(2\pi )^{n}}\Vert (1 +\Vert \bullet \Vert _{\mathbb{R}^{n}})^{k}\hat{f}\Vert _{ L^{2}} < \infty \},\quad k \in \; \mathbb{N}_{0}}$

denote the Sobolev spaces. The following criterion for the order of approximation turns out to be easy to verify for splines.

Theorem 5.

Let $\phi \in L^{2}(\mathbb{R}^{n})$ satisfy the following properties [23, Theorem 1.15]:

(i)

$1/\hat{\phi }$ is bounded on some neighborhood of the origin.

(ii)

Let $B_{\varepsilon }$ be some open ball centered at the origin and let E: = $B_{\varepsilon } + (2\pi \mathbb{Z}^{n}\setminus$ {0}). For some α > k + n∕2, all derivatives of $\hat{\phi }$ of order ≤α are in L ² (E).

(iii)

$D^{\gamma }\hat{\phi }(\omega ) = 0$ for all |γ| < k and all $\omega \in 2\pi \mathbb{Z}^{d}\setminus$ {0}.

Then $V _{0} = \overline{\mbox{ span}\;\{\phi (\bullet -k)\}_{k\in \mathbb{Z}^{n}}}$ provides an approximation order k:

For $f \in H^{k}(\mathbb{R}^{n})$ ,

$$$\displaystyle{\min \{\left \|f - s(\bullet /h)\right \|_{L^{2}},s \in V _{0}\} \leq \mbox{ const}.\;h^{k}\left \|f\right \|_{ H^{k}}\quad \mbox{ for}\;\mbox{ all}\;h > 0.}$$” src=”/wp-content/uploads/2016/04/A183156_2_En_28_Chapter_Equy.gif”></DIV></DIV></DIV></DIV></DIV></DIV><br /> <DIV id=Sec9 class=$

Wavelets

For the step from a coarser approximation space V _jto a finer one V _j+1, information has to be added. It is contained in the wavelet space or detail space W _j, which is the orthonormal complement of V _jin V _j+1:

$\displaystyle{V _{j+1} = V _{j} \oplus W_{j}.}$

It follows that $V _{j+m} = V _{j} \oplus \bigoplus _{l=0}^{k-1}W_{j+l}$ , and hence

$\displaystyle{ L^{2}(\mathbb{R}^{n}) =\bigoplus _{ j\in \mathbb{Z}}W_{j} }$

(5)

can be decomposed in a direct sum of mutually orthogonal detail spaces. Moreover, the detail spaces W _jinherit the scaling property from Definition 1(iv) for the approximation spaces V _j. For all $j \in \mathbb{Z}$ ,

$\displaystyle{f \in W_{j} \Leftrightarrow f(A^{-j}\bullet ) \in W_{ 0}.}$

The question now is whether there is also a simple basis generated by the shifts of one or few functions, the wavelets. The following definition is motivated from Eq. (5).

Definition 6.

Let A be a dilation matrix, and let {ψ _l} $_{l=1,\ldots,q},q \in \mathbb{N}$ , be a set of functions in $L^{2}(\mathbb{R}^{n})$ , such that the family

$\displaystyle{\{\vert \det A\vert ^{j/2}\psi _{ l}(A^{j}\bullet - k)\vert \ l = 1,\ldots,q,\;j \in \; \mathbb{Z},\;k \in \; \mathbb{Z}^{n}\}}$

forms an orthonormal basis of $L^{2}(\mathbb{R}^{n})$ . Then {ψ _l}_{l = 1, …, q}is called a wavelet set associated with A.

What qualitative properties do the wavelets have? The approximation spaces V _jare generated by the scaling function, which operates as a low-pass filter. This can be seen from Theorem 3(iii) $\hat{\phi }(0)\neq 0$ and resp. from Theorem 5(i): $1/\hat{\phi }$ is bounded in some neighborhood of the origin. Therefore, the added details and thus the wavelets have to carry the high-frequency information. In addition, the wavelets ψ in W ₀ are elements of V ₁ and therefore have the form

$\displaystyle{ \psi (A^{-1}x) =\sum \nolimits _{ k\in \,\mathbb{Z}^{n}}a_{k}\phi (x - k) }$

(6)

in L ² norm, where $\{a_{k}\}_{k\in \,\mathbb{Z}^{n}}$ are the Fourier coefficients of a certain 2 $\pi \mathbb{Z}^{n}$ -periodic function.

Proposition 2.

Let $(V _{j})_{j\in \,\mathbb{Z}}$ be a multiresolution analysis of $L^{2}(\mathbb{R}^{n})$ with respect to the dilation matrix A and with scaling function ϕ. Then for a function $f \in L^{2}(\mathbb{R}^{n})$ the following are equivalent: f ∈ V ₁ id and only if

$\displaystyle{\hat{f}(A^{T}\omega ) = m_{ f}(\omega )\hat{\phi }(\omega )\;\mbox{ almost}\;\mbox{ everywhere}.}$

Here, $m_{f} \in L^{2}([0,2\pi ]^{n})$ and

$\displaystyle{\left \|m_{f}\right \|_{L^{2}([0,2\pi ]^{n})}^{2} = \frac{1} {\vert \det A\vert }\left \|f\right \|_{L^{2}(\mathbb{R}^{n})}^{2}.}$

For a proof, see, e.g., [21, 74]. Note that for a wavelet ψ as in Eq. (6), there holds

$\displaystyle{m_{\psi }(\omega ) = \frac{1} {\vert \det A\vert }\sum \nolimits _{k\in \mathbb{Z}^{n}}a_{k}e^{i\langle \omega,k\rangle }.}$

How many wavelets, i.e., generators of W ₀, are needed to span the space? The parameter q in Definition 6 is yet unspecified. In fact, q depends on the scaling matrix. A leaves the lattice $\mathbb{Z}^{n}$ invariant, A $\mathbb{Z}^{n} \subset \mathbb{Z}^{n}$ . The number of cosets is $\vert {\mathrm{det}}A\vert =\vert \mathbb{Z}^{n}/A\mathbb{Z}^{n}\vert$ (see [74, Proposition 5.5]). It turns out that $q =\vert \mathrm{ det}A\vert - 1$ wavelets are needed to generate the space W ₀. To motivate this, for a start, let f ∈ V ₁ be an arbitrary function. Denote $\gamma _{0},\ldots,\gamma _{q}$ representatives of the q + 1 cosets of $A\mathbb{Z}^{n}$ in $\mathbb{Z}^{n}$ . Then each coset can be written as $\gamma _{m} + A\mathbb{Z}^{n}$ , m = 0,…,q. The function f has the representation

$\displaystyle{ \frac{1} {\vert \det A\vert ^{1/2}}f(A^{-1}x) =\sum \nolimits _{ k\in \mathbb{Z}^{n}}c_{k}(f)\phi (x - k), }$

(7)

or in Fourier domain

$\displaystyle{ \hat{f}(A^{T}\omega ) = \frac{1} {\vert \det A\vert ^{1/2}}c_{f}(\omega )\hat{\phi }(\omega ), }$

(8)

in L ² sense and with an appropriate 2 $\pi \mathbb{Z}^{n}$ -periodic function c _f (ω) with Fourier coefficients $(c_{k}(f))_{k\in \mathbb{Z}^{n}}$ . Then $c_{f}(\omega )$ can be decomposed with respect to the cosets:

$\displaystyle\begin{array}{rcl} c_{f}(\omega )& =& \sum \nolimits _{k\in \mathbb{Z}^{n}}c_{k}(f)e^{i\langle \omega,k\rangle } =\sum \nolimits _{ m=0}^{q}\sum \nolimits _{ k\in \gamma _{m}+A\mathbb{Z}^{n}}c_{k}(f)e^{i\langle \omega,k\rangle } {}\\ & =& \sum \nolimits _{m=0}^{q}e^{i\langle \omega,\gamma _{m}\rangle }\sum \nolimits _{k\in A\mathbb{Z}^{n}}c_{k+\gamma _{m}}(f)e^{i\langle \omega,k\rangle } =\sum \nolimits _{ m=0}^{q}c_{ f}^{m}(\omega ), {}\\ \end{array}$

where

$\displaystyle\begin{array}{rcl} c_{f}^{m}(\omega )& =& e^{i\langle \omega,\gamma _{m}\rangle }\sum \nolimits _{k\in A\mathbb{Z}^{n}}c_{k+\gamma _{m}}(f)e^{i\langle \omega,k\rangle } = e^{i\langle \omega,\gamma _{m}\rangle }\sum \nolimits _{k\in \mathbb{Z}^{n}}c_{Ak+\gamma _{m}}(f)e^{i\langle \omega,Ak\rangle } {}\\ & =& e^{i\langle \omega,\gamma _{m}\rangle }\sum \nolimits _{k\in \mathbb{Z}^{n}}c_{Ak+\gamma _{m}}(f)e^{i\langle A^{T}\omega,k\rangle } = e^{i\langle \omega,\gamma _{m}\rangle }\kappa _{f}^{m}(A^{T}\omega ). {}\\ & & {}\\ \end{array}$

This representation exists for all functions V ₁, in particular for ϕ and the wavelets. The following theorem indicates how the wavelets are constructed that generate the space W ₀, such that W ₀ ⊕ V ₀ = V ₁.

Theorem 6.

Let ϕ ∈ V ₀ be a scaling function and let $\psi _{1},\ldots,\psi _{q} \in V _{1}$ . Then the family $\{\phi (\bullet -k)\}_{k\in \mathbb{Z}^{n}}$ is an orthonormal system if and only if

$\displaystyle{ \sum \nolimits _{m=0}^{q}\left \vert \kappa _{\phi }^{m}(\omega )\right \vert ^{2} = 1\quad \mbox{ almost}\;\mbox{ everywhere}. }$

(9)

The system $\{\phi (\bullet -k)\}_{k\in \mathbb{Z}^{n}} \cup \bigcup _{m=1}^{q}\{\psi _{m}(\bullet -k)\}_{k\in \mathbb{Z}^{n}}$ is an orthonormal basis in V ₁ if and only if the so-called polyphase matrix

$\displaystyle{\left (\begin{array}{*{20}c} \kappa _{\phi }^{0}(\omega )&\kappa _{\psi _{1}}^{0}(\omega )&\cdots &\kappa _{\psi _{q}}^{0}(\omega )\\ \vdots & \vdots & \ddots & \vdots \\ \kappa _{\phi }^{q}(\omega )&\kappa _{\psi _{1}}^{q}(\omega )&\cdots &\kappa _{\psi _{q}}^{q}(\omega )\\ \end{array} \right )}$

is unitary for almost all $\omega \in \mathbb{R}^{n}$ .

The proof for a more general version of this theorem is given in [74, Sect. 5.2].

A summary and a condition for r-regular wavelets yields in the following theorem.

Theorem 7.

Consider a multiresolution analysis on $\mathbb{R}^{n}$ associated with a dilation matrix A.

(i)

Then there exists an associated wavelet set consisting of $q =\vert \mathrm{ det}A\vert - 1$ functions.

(ii)

If the multiresolution analysis is r-regular and in addition 2q + 1 > n, then there exists an associated wavelet set consisting of q functions, which all are r-regular.

The idea of the proof is that for an r-regular function ϕ on

Only gold members can continue reading. Log In or Register to continue