Abstract. Given a complete separable σ-finite measure space (X, Σ, μ) and nested partitions of X, we construct unbalanced Haar-like wavelets on X that form an unconditional basis for L_{p}(X, Σ, μ) where 1 < p < ∞. Our construction and proofs build upon ideas of Burkholder and Mitrea. We show that if (X, Σ, μ) is not purely atomic, then the unconditional basis constant of our basis is (max(p, q) − 1). We derive a fast algorithm to compute the coefficients.

A NEW CLASS OF UNBALANCED HAAR WAVELETS THAT FORM AN UNCONDITIONAL BASIS FOR L_{p} ON GENERAL MEASURE SPACES

MARIA GIRARDI AND WIM SWELDENS

1. Introduction

Our goal is, given a measure space (X, Σ, μ) and nested partitions of X, to construct unbalanced Haar-like wavelets on X that form an unconditional basis for L_{p} ≡ L_{p}(X, Σ, μ) where 1 < p < ∞.

Wavelets are traditionally defined on Euclidean spaces. They usually are the translates and dilates of one particular function and are orthogonal or biorthogonal with respect to the Lebesgue measure.

However, we work on a general measure space, which need not even have a vector space structure, so translation and dilation becomes void. Although our wavelets are not the translates and dilates of one function, they still enjoy the desirable properties of traditional wavelets, such as a multiresolution structure and an associated fast transform algorithm. Our setting allows for non-translation invariant measures and covers general nested partitions of arbitrary subsets of Euclidean spaces. Thus our wavelets are particularly useful in practical applications.

Our construction is inspired by and generalizes the construction [1, 14] of Mitrea wavelets on dyadic cubes in R^{n}. This was the first construction of Haar-like wavelets in case of nontranslation invariant measures on R^{n} for n > 1.

To show that wavelets form an unconditional basis of L_{p}, one often uses Calderón-Zygmund theory and an interpolation result of Marcinkiewicz. We follow a different approach; we show that the wavelets essentially are a martingale difference sequence and thus are able to use Burkholder’s celebrated inequality [4, 5, 6] to show that they form an unconditional basic sequence. This approach gives the best unconditional basis constant. We also show that in some cases the wavelets form a monotone basis.

1991 Mathematics Subject Classification. 42C15, 60G46.

Key words and phrases. unconditional basis, wavelet, martingale, Haar functions.

The first author is partially supported by NSF DMS-9306460.

The second author is partially supported by NSF EPSCoR Grant EHR 9108772 and DARPA Grant AFOSR F49620-93-1-0083. He is also Senior Research Assistant of the National Fund of Scientific Research Belgium (NFWO).

One aim of this paper is to illustrate how techniques from martingale and Banach space theory can be used in wavelet theory.

The paper is organized as follows. In Section 2 we set some notation and recall some classical results. In Section 3 we introduce the notion of a forest, which we use as an indexing set. We use the forest to define partitions in Section 4. Section 5 contains the construction of the wavelets while Section 6 contains the proof that they form an unconditional basis. We discuss the dual basis and a characterization in Section 7. The next two sections contain more practical results. Sections 8 shows the connection with multiresolution analysis and the fast wavelet transform, while Section 9 discusses the setting inside a Euclidean space.

2. Notation and Terminology and Basics

Recall that a countable family {ψ_{γ}}_{γ∈G} is an unconditional basis for L_{p} if for each f ∈ L_{p} there is a unique family {c_{γ}}_{γ∈G} of real numbers so that ∑ c_{γ}ψ_{γ} converges unconditionally to f in L_{p}-norm. This is the case if and only if the following two conditions hold:

(C1) clos span{ψ_{γ} | γ ∈ G} = L_{p}

(C2) a constant K exists so that for all finite subsets Γ ⊂ G

∥∑_{γ∈Γ} ϵ_{γ} c_{γ} ψ_{γ} ∥_{p} ⩽ K ∥∑_{γ∈Γ} c_{γ} ψ_{γ} ∥_{p} ,

for all choices of c_{γ} ∈ R and ϵ_{γ} = ±1.

The smallest K for which condition (C2) holds, denoted K_{p}({ψ_{γ}}), is the unconditional basis constant of {ψ_{γ}}.

Clearly, any Banach space with a countable basis is separable. If 1 < p < ∞, then a separable L_{p}(μ) space has an unconditional basis [17, 8]. Pełczyński [18] showed that, for any finite nonpurely atomic measure μ, the space L_{1}(μ) does not even embed into a Banach space with an unconditional basis. Thus we restrict our attention to separable L_{p} spaces with 1 < p < ∞. In this setting, we know L_{p}(X, Σ, μ) up to an isometric isomorphism. Recall that two Banach spaces E and F are isometrically isomorphic if there is an invertible bounded linear operator T : E → F so that ∥T ∥ = 1 = ∥T^{−1}∥. A separable L_{p}(X, Σ, μ) is isometrically isomorphic to precisely one of the following spaces, where L_{p}(m) is the L_{p} space on the Lebesgue measure space on [0, 1]: ℓ_{p}, ℓ_{p}^{n}, L_{p}(m), L_{p}(m) ⊕_{p} ℓ_{p}, L_{p}(m) ⊕_{p} ℓ_{p}^{n} for some n ∈ N (cf. [22, Proposition III.A.1]). The isometric isomorphism basically follows from mapping (X, Σ, μ) into a combination of the Lebesgue measure space on [0, 1] and the counting measure space on N. For practical reasons, we prefer to constructively build our wavelets directly on X instead of calling upon this mapping.

Throughout this paper, (X, Σ, μ) is a fixed complete measure space with μ taking values in the non-negative extended real numbers. Let Σ^{+} be the collection of all sets in Σ with strictly positive, but finite, μ-measure; let Σ̃ be any sub-σ-field of Σ such that the μ-completion of (X, Σ̃) is (X, Σ). The support of a function f : X → R is the set supp f ≡ {x ∈ X | f(x) ≠ 0}. For an arbitrary set S, let P(S) be the power set of S and #S be the cardinality of S. For K ⊂ P(S), let σ(K) be the smallest σ-algebra containing K. For a function f on S, we follow the common practice of also denoting by f the natural extension of the original f to P(S). Throughout this paper, 1 < p < ∞ is a fixed number with conjugate exponent q where 1/p + 1/q = 1. Let p^{∗} = max (p, q). The dual space L_{p}^{∗} of L_{p}(X, Σ, μ) is isometrically isomorphic to L_{q}(X, Σ, μ), where g ∈ L_{q}(X, Σ, μ) is identified with x_{g}^{∗} ∈ L_{p}^{∗} by

x_{g}^{∗}(f) = ⟨ f, g ⟩ = ∫_{X} f g dμ .

We say that f ∈ L_{p} is orthogonal to g ∈ L_{q} if ⟨ f, g ⟩ = 0.

3. Trees and Forests

We formulate the notation of a forest, which is a useful indexing set. A forest (F, g, p, C, <) consists of a countable set F, which has a (possibly empty) subset R of root elements, along with a generation function g : F → Z, a parent function p : F \ R → F, a children function C : F → P(F), and an age partial ordering < on F, all of which satisfy the following properties:

(F1) C(α) = {β ∈ F | p(β) = α},

(F2) 0 ⩽ #C(α) < ∞ for each α ∈ F ,

(F3) if β ∈ C(α) then g(β) = 1 + g(α) ,

(F4) the ordering < linearly orders C(α) for each α ∈ F .

(F5) if g(α) < g(β) and p^{n}(α) = p^{m}(β) for some n, m ⩾ 0, then β < α,

where the power functions p^{n} of the parent function p are defined by p^{0} being the identity function and p^{n}(α) = p(p^{n−1}(α)). If confusion is unlikely, we denote a forest (F, g, p, C, <) by just F. The given partial ordering extends to a linear ordering of the whole forest with (F4) and (F5) still holding: it is only needed to extend the ordering as so to linearly order each k^{th}-generation F_{k} of F where

F_{k} = {α ∈ F | g(α) = k} .

Thus, henceforth, forests satisfy the additional property

(F6) the ordering < linearly orders the the whole forest .

One thinks of a parent element α ∈ F_{k} on the k^{th}-generation of F as spawning the children elements β with β ∈ C(α) ⊂ F_{k+1}. Root elements are denoted by ρ and have no parent. A forest F that satisfies the additional property

(T1) if α, β ∈ F, then there are n, m ⩾ 0 so that p^{n}(α) = p^{m}(β) is called a tree. A tree has at most one root element; a rooted tree has exactly one root.

A leaf is an element that has no children. Let L be the set of leaves in F. On occasions it is convenient to think of a leaf as repeating itself in the later generations, for this consider

F_{k}^{∗} = F_{k} ⋃ [ ⋃_{j<k} L ∩ F_{j} ] .

Let

C_{l}(α) = \begin{cases}C(α) & if α ∉ L \\ \{α\} & if α ∈ L . \end{cases}

Define the power functions C^{n} (resp. C_{l}^{n}(α)) of the function C (resp. C_{l}(α)) analogous to the power functions p^{n}. Note that for n ∈ N,

C_{l}^{n}(α) = C^{n}(α) ⋃ ⋃_{j=0}^{n−1} [ C^{j}(α) ∩ L ] .

A countable union of disjoint trees is a forest. Conversely, any forest (F, g, p, C, <) can be expressed as a countable union of disjoint trees. To see this, consider the equivalence relation ∼ on F given by α ∼ β if and only if (T1) holds. This relation induces a partition of F

F = ⋃_{κ∈K} F(κ) (1)

into disjoint equivalence classes F(κ) where the indexing set K is the induced quotient space. Each F(κ) is a tree.

The concept of a forest, which is fairly technical, is introduced to help simplify the construction of wavelets from nested partitionings of X. Later we will reduce the general forest setting to three canonical cases of trees.

4. Partitions

We call a collection {X_{α} | α ∈ F} from Σ^{+} a nested partitioning for X, with respect to the forest F, if it satisfies the following partition properties:

(P1) X_{α_{1}} ∩ X_{α_{2}} = ∅ if g(α_{1}) = g(α_{2}) and α_{1} ≠ α_{2} , (P2) X_{α} ∩ X_{ρ} = ∅ if ρ ∈ R and p^{n}(α) ≠ ρ for each n ⩾ 0 , (P3) if X_{α} is not a leaf, then it can be written as the disjoint union

X_{α} = ⋃_{β∈C(α)} X_{β} ,

(P4) X = ∪{X_{α} | α ∈ F},

(P5) σ({X_{α} | α ∈ F}) = Σ̃ . The partitioning (1) of the forest into trees provides a partition of X. For each κ ∈ K, let

X(κ) = ⋃_{α∈F(κ)} X_{α} .

From the first three partition properties it follows that if κ_{1} ≠ κ_{2} then X(κ_{1}) and X(κ_{2}) are disjoint. Thus X can be written as the disjoint union

X = ⋃_{κ∈K} X(κ) . (2)

For each κ ∈ K, the subcollection {X_{α} | α ∈ F(κ)} is a nested partitioning for X(κ) with respect to the tree F(κ). The partitions

π_{k}(κ) = {X_{α} | α ∈ F_{k}^{∗} ∩ F(κ)}

of X(κ) are nested for k ∈ g(F(κ)). We will use the subcollection {X_{α} | α ∈ F(κ)} to build wavelets on X(κ). Our wavelets Ξ will then be the union of the wavelets on each X(κ). Thus, for the time being, we will work with trees instead of forests. There are three types of nested partitionings of X with respect to a tree T :

- Type I: R ≠ ∅ and thus μ(X) < ∞,

- Type II: μ(X) < ∞ and R = ∅,

- Type III: μ(X) = ∞ and thus R = ∅. Each type is handled slightly different. But before passing to the construction of the wavelets, we clarify the above notations with the following examples.

Example 1. Let (X, Σ, μ) be the Lebesgue measure space on X = [0, 1). Consider the Type I tree (T , g, p, <) where

(1) T = {(n, k) | n = 0, 1, … and 1 ⩽ k ⩽ 2^{n}},

(2) ρ = (0, 1),

(3) g((n, k)) = n,

(4) C((n, k)) = {(n + 1, 2k − 1), (n + 1, 2k)},

(5) (n + 1, 2k − 1) < (n + 1, 2k). Let X_{(n,k)} = [ 2^{−n} (k − 1) , 2^{−n} (k) ).

Example 2. Let (X, Σ, μ) be the Lebesgue measure space on X = R. Modify the tree from Example 1 by taking n ∈ Z and k ∈ Z and let X_{(n,k)} be formally as in Example 1. In these two examples, each X_{(n,k)} has two children. This example is of Type III.

Example 3. Let (X, Σ, μ) be a weighted counting measure on X = N with 0 < μ(n) < ∞ for each n ∈ N. Modify the tree from Example 1 by taking integers n ⩽ 0 and k ∈ N. Let X_{(n,k)} = X ∩ ( 2^{−n} (k − 1) , 2^{−n} (k)]. Each X_{(0,k)} = {k} is a leaf. This example is of Type II if μ(X) < ∞ and of Type III if μ(X) = ∞.

Example 4 (Logarithmic tree). Let M = {1, 2, …, m} for some m ∈ N. The tree T_{log} on M is uniquely determined by the following properties.

(1) It has l generations (0, ⋯, l − 1) where 2^{l−2} < m ⩽ 2^{l−1}.

(2) Each element of T_{log} is a set of consecutive integers from M.

(3) It has one root element ρ = M and g(ρ) = 0.

(4) The (l − 1) generation consists of the leaves {{1}, {2}, … {m}}.

(5) Each element of T_{log} with cardinality greater than 1 has two children and the cardinality

of the youngest child is equal to or one less than the cardinality of the older child. This tree will be used in the general wavelet construction. The name logarithmic comes from the fact that the number of generations behaves as the logarithm of #M.

Example 5 (Linear tree). Let M be as in the previous example. The tree T_{lin} on M is uniquely determined by the following properties.

(1) It has m generations (0, ⋯, m − 1).

(2) Each element of T_{lin} is a set of consecutive integers of M.

(3) It has one root element ρ = M and g(ρ) = 0.

(4) The (m − 1) generation consists of the leaves {{1}, {2}, … {m}}.

(5) Each element of T_{lin} with cardinality greater than 1 has two children and the cardinality

of the youngest child is 1. This example will also be used in the general wavelet construction. It is called linear since the number of generations is proportional to the number of elements of M.

The previous two trees may be viewed as nested partitionings themselves.

Example 6. Let (X = M, Σ, μ) be a weighted counting measure on M = {1, 2, …, m} with 0 < μ(n) < ∞ for each n ∈ M. Each of the previous two examples gives a nested partitioning {M_{α} | α ∈ M} of M by letting M_{α} = α.

Example 7. Let (X, Σ, μ) be the Lebesgue measure space on X = R^{n} for some n ∈ N. Let {X_{α}} be the dyadic cubes in X. Each X_{α} has 2^{n} children. This example is of Type III.

[figure]

Figure 1. Subdividing a triangle.

Figure 2. Partitioning a sphere.

Example 8. Let X be the sphere S^{2} in R^{3}, endowed with the surface area measure. Consider the icosahedron Π centered at the origin along with the corresponding map

P : Π → S^{2}  where  P (v) = v/ ∥v∥_{R^{3}} .

We use P to push a partition of Π out to a partition of S^{2}. The 0^{th}-generation partition consists of just X_{ρ} = S^{2}. Next obtain nested partitions of Π by recursively subdividing each triangular side. Figure 1 depicts a typical subdivision of a triangle. The image under P of these nested partitions of Π are nested partitions of S^{2}, where each set of a partition is a spherical triangle. Figure 2 shows the icosahedron (left), the icosahedron after 3 subdivisions (middle), and the result after applying P to the middle polyhedron (right). The latter is the fourth generation of the partitions on the sphere. This example is used in [19] as a starting point.

One can now consider a countable collection of disjoint measure spaces, each of which has a nested partitioning with respect to a forest. It is possible to unite their forests into a new forest. Then the union of their nested partitionings forms a nested partitioning for the disjoint sum of the measure spaces (with respect to the new forest). In this fashion, it is possible to combine the above examples.

Any measure space that has a nested partitioning is necessarily complete, separable, and σ-finite.

Fact 9. Each complete, separable, σ-finite measure space has a nested partitioning.

To see this, note that a complete separable σ-finite measure space may be viewed as a disjoint sum of complete separable measure spaces, with one space being purely atomic and the other spaces being purely non-atomic and of finite measure. As in Examples 3 and 6, one can build a nested partitioning on the purely atomic space. On each of the purely non-atomic spaces of finite measure, using Example 1 and a theorem of Carathéodory (cf. [22, I.B.1]), one can build a nested partitioning (with care, separability guarantees (P5)). Then, as noted above, these partitionings combine to give a nested partitioning for the entire space.

5. Construction of wavelets

Plant a tree T . Let {X_{α} | α ∈ T } be a nested partitioning for X with respect to T . We are now ready to build on X our wavelets, which have as their basic building blocks the scaling functions {φ_{α}}_{α∈T} where

φ_{α} = μ(X_{α})^{−1/p} 1_{X_{α}} .

The wavelets will be indexed by a set G. The set G consists of a set G^{∗} along with possibly one other element. When helpful, we will try to be consistent in the notation by denoting a parent by α, a child by β, and an element of G by γ.

First we concentrate on G^{∗}. Each wavelet indexed by a γ ∈ G^{∗} will be of the form

ψ_{γ} = n_{γ} (\frac{1_{P_{γ}}}{μ(P_{γ})} − \frac{1_{N_{γ}}}{μ(N_{γ})}) , (3)

for some sets P_{γ} and N_{γ} in Σ̃ with n_{γ} chosen as to normalize ψ_{γ} in L_{p}, thus,

n_{γ} = (μ(P_{γ})^{1−p} + μ(N_{γ})^{1−p})^{−1/p} .

This resembles the definition of a Haar wavelet, but as μ(P_{γ}) can differ from μ(N_{γ}), we refer to it as an unbalanced Haar wavelet. It is constructed to have zero mean.

The set G^{∗} has the form

G^{∗} = ⋃_{α∈T} G(α) ,

where the set G(α) contains max(0, m−1) elements (m = #C(α)) and is constructed as follows. The basic idea is to use G(α) to index those unbalanced Haar wavelets that will be supported on X_{α} and constant on X_{β} where β ∈ C(α). To do this, we build a mini-tree amongst the children. Enumerate the children of α as β_{i} with i ∈ M = {1, 2, ⋯, m} and β_{i} < β_{i+1}. Next consider a tree T_{M} that is either T_{lin} or T_{log}. Let

G(α) = {(α, ζ) ∈ {α} × T_{M} | #C(ζ) = 2} .

Note that each element of T_{M} has at most two children.

− + 0  − + 0  − +

Figure 3. Mitrea wavelets (linear construction).

The element γ = (α, ζ) ∈ G(α) generates a wavelet ψ_{γ} as in (3) with

P_{γ} = ⋃_{i∈ζ_{1}} X_{β_{i}}, and N_{γ} = ⋃_{i∈ζ_{2}} X_{β_{i}} ,

where ζ_{1} and ζ_{2} are the two children of ζ.

The remainder of G depends on the particular type of splitting.

- For Type I, let

G = G^{∗} ∪ {ρ} and ψ_{ρ} = φ_{ρ} ≡ μ(X)^{−1/p} 1_{X} .

For later use, let P_{ρ} = X and N_{ρ} = ∅.

- For Type II, let

G = G^{∗} ∪ {ν} and ψ_{ν} = μ(X)^{−1/p} 1_{X} ,

where ν ∉ G^{∗}. For later use, let P_{ν} = X and N_{ν} = ∅.

- For Type III, let G = G^{∗}. Finally, take

Ψ = {ψ_{γ} | γ ∈ G} . (4)

We define the following partial ordering on G. Any element in G^{∗} is less than an element in G \ G^{∗}. Next consider two elements in G^{∗}, say γ_{1} = (α_{1}, ζ_{1}) and γ_{2} = (α_{2}, ζ_{2}). Now γ_{1} < γ_{2} if either α_{1} < α_{2}, or α_{1} = α_{2} and ζ_{1} < ζ_{2}. Also define the generation function on G^{∗} as g((α, ζ)) = g(α).

Depending on the choices T_{lin} or T_{log} for T_{M} we refer to the respective construction as linear or logarithmic. They will have the same theoretical properties; the advantage of the logarithmic construction is that the support size of the wavelets is smaller and that the wavelets are have more symmetry. In the setting of the examples in the previous section, the above construction leads to well-known wavelets.

- For Example 1 (resp. 2), Ψ is the Haar system on [0, 1) (resp. R).

- For Example 3 (resp. 6), Ψ is a Haar-like unconditional basis for ℓ_{p} (resp. ℓ_{p}^{m}).

- For Example 7 the linear construction leads to the Mitrea wavelets [1, 14]. The Mitrea wavelets are the first example of higher dimensional compactly supported Haar-like wavelets in the case of non-translation invariant measures. The basic idea, as depicted

− + 0  0 − +  − +

Figure 4. Logarithmic construction.

in Figure 3 for the two dimensional case, is simple but extremely clever. Our linear construction is inspired by the Mitrea wavelets. The setting of the Mitrea wavelets is actually more general than presented here as the measure can be Clifford-algebra-valued.

- Again for Example 7, Figure 4 depicts the logarithmic construction in case n = 2. Concluding, the basic idea behind constructing the unbalanced Haar wavelets in the case that the number of children is greater than two is to build a mini-tree amongst the children as to reduce it to the case of two children.

6. Properties of wavelets

Clearly Ψ is normalized. Note that for each γ ∈ G^{∗},

∫_{X} ψ_{γ} dμ = 0 . (5)

If γ and γ′ are in G, then

∫_{X} ψ_{γ} ψ_{γ′} dμ = 0 , (6)

for if ψ_{γ} and ψ_{γ′} are not disjointly supported and γ < γ′, then ψ_{γ′} is constant on the support of ψ_{γ}. If α ∈ T , then

(7) span{φ_{β} | β ∈ C_{l}(α)} = span{φ_{α}, ψ_{γ} | γ ∈ G(α)} ,

and furthermore this extends over several generations for if i ∈ N, then

(8) span{φ_{β} | β ∈ C_{l}^{i}(α)} = span {φ_{α}, ψ_{γ} | γ ∈ ∪_{j=0}^{i−1}G(C^{j}(α))} .

To see this, note that set containment in one direction (⊇) is clear; furthermore, in the righthand side (by (5) and (6)) and the left-hand side, the indicated functions that span the space (of dimension #C_{l}^{i}(α)) can be viewed as an orthogonal basis.

Since

L_{p} = clos span{1_{A} | A ∈ Σ^{+}} ,

and {X_{α} | α ∈ T } ∪ ∅ is a semi-ring that generates Σ̃, it follows that (cf. [3, Theorem 11.4])

(9) L_{p} = clos span Φ where

Φ = {φ_{α} | α ∈ T } .

Note that L_{p} is separable since T is countable. Lemma 10.

clos span Ψ = L_{p}.

Proof. Fix an indicator function 1_{X_{δ}} with δ ∈ T . By (9), it suffices to show that

(10) 1_{X_{δ}} ∈ clos span Ψ .

If δ = ρ, then (10) clearly holds; thus, assume that δ ≠ ρ.

Consider α ∈ T of the form α = p^{i}(δ) for some i > 0, along with the corresponding function

f_{i} = 1_{X_{δ}} − \frac{μ(X_{δ})}{μ(X_{α})}1_{X_{α}} .

Towards showing that f_{i} is in span Ψ, consider (8) with the same α and i as in this proof. Clearly, f_{i} is in the set on the left-hand side and so it is also in the set on the right-hand side. Since f_{i} and ψ_{γ} have a vanishing integral (for γ ∈ G^{∗}) while φ_{α} does not, f_{i} does not have a component along φ_{α}. Thus

f_{i} ∈ span {ψ_{γ} | γ ∈ ∪_{j=0}^{i−1} G(C^{j}(α))} ⊂ span Ψ .

Towards (10), consider the three types of nested partitionings separately.

- For Type I, p^{i}(δ) = ρ for some finite i and 1_{X_{ρ}} ∈ span Ψ.

- For Type II, the function 1_{X_{p^{i}(δ)}} tends to 1_{X} in L_{p}-norm as i → ∞ and 1_{X} ∈ span Ψ.

- For Type III,

∥f_{i} − 1_{X_{δ}}∥_{p} = μ(X_{δ}) μ(X_{p^{i}(δ)})^{−1/q} ,

and μ(X_{p^{i}(δ)}) tend to infinity as i → ∞. So for each of the three types, (10) holds.

Thus Ψ satisfies (C1). Toward (C2), recall that a constant K_{p} exists so that for the usual Haar functions {h_{k}}_{k=1}^{∞} on [0, 1),

∥∑_{k=1}^{n} ϵ_{k} c_{k} h_{k}∥_{p} ⩽ K_{p} ∥∑_{k=1}^{n} c_{k} h_{k}∥_{p} ,

for all n ∈ N, sequences {c_{k}}_{k=1}^{n} in R, and ϵ_{k} = ±1. This inequality (in an equivalent formulation) is due to R.E.A.C. Paley [17]; the above formulation was noted by Marcinkiewicz [12]. Using martingale theory, Burkholder [5] generalized Paley’s inequality to hold for martingale difference sequences (such as the Haar functions) on [0, 1). Since the wavelets Ψ can essentially be viewed as a martingale difference sequence, we will call upon Burkholder’s generalization. We first recall some basic definitions.

Fix X_{0} ∈ Σ^{+} and a sub-σ-field Σ_{0} of Σ that is generated by a partition π = {E_{1}, …, E_{n}} of X_{0} (thus X \ X_{0} is an atom of Σ_{0}). Consider g ∈ L_{1}(X, Σ, μ) with supp g ⊂ X_{0}. Then the conditional expectation E(g | Σ_{0}) of g with respect to Σ_{0} is

E(g | Σ_{0}) = ∑_{i=1}^{n} \frac{∫_{E_{i}} g dμ}{μ(E_{i})} 1_{E_{i}} ,

observing the convention that 0/0 is 0. A simple martingale, with respect to a non-decreasing sequence {Σ_{i}}_{i=1}^{n} of sub-σ-fields of Σ, is a finite sequence {f_{i}}_{i=1}^{n} of simple functions with finite support that satisfy that f_{i} is Σ_{i}-measurable for 1 ⩽ i ⩽ n and that E(f_{i+1} | Σ_{i}) = f_{i} for 1 ⩽ i < n. Its corresponding martingale difference sequence {d_{i}}_{i=1}^{n} is given by d_{i} = f_{i} − f_{i−1} where f_{0} is just the null function, thus f_{k} = ∑_{i=1}^{k} d_{i}.

Our setting calls for the following version of Burkholder’s celebrated inequality.

Theorem 11 (Burkholder). If {f_{i}}_{i=1}^{n} is a simple martingale with respect to a non-decreasing sequence {Σ_{i}}_{i=1}^{n} of sub-σ-fields of Σ, then its corresponding martingale difference sequence {d_{i}}_{i=1}^{n} satisfies

∥∑_{i=1}^{n} ϵ_{i} c_{i} d_{i}∥_{p} ⩽ (p^{∗} − 1) ∥∑_{i=1}^{n} c_{i} d_{i}∥_{p} , (11)

for all n ∈ N and all choices of c_{i} ∈ R and ϵ_{i} = ±1.

See [5, 6, 7] for the proof.

If L_{p}(m) isometrically embeds into L_{p}(X, Σ, μ), then any basis for L_{p}(X, Σ, μ) has, for each ϵ > 0, a blocked basis that is (1 + ϵ)-equivalent to the usual Haar basis ([15, 16] and [10]). Burkholder [4] showed that the unconditional basis constant of the usual Haar basis is p^{∗} − 1. Olevskiĭ showed that the unconditional basis constant of any unconditional basis is greater than or equal to that of the Haar system. ¿From these facts follow the below known fact.

Theorem 12. If (X, Σ, μ) is not purely atomic, then the unconditional basis constant for any unconditional basis for L_{p}(X, Σ, μ) is at least (p^{∗} − 1).

The following lemma is needed to apply Theorem 11 to finite subsets of Ψ.

Lemma 13. Fix a finite subset {γ_{i}}_{i=1}^{n} from G that satisfies γ_{1} > γ_{2} > … > γ_{n}. Let X_{0} ∈ Σ^{+} be such that sup ψ_{γ_{i}} ⊂ X_{0} for each i. Consider the corresponding partitions

π_{i} = {P_{γ_{i}} , N_{γ_{i}} , X_{0} \ (P_{γ_{i}} ∪ N_{γ_{i}})}

of X_{0} and let Σ_{i} = σ ({π_{j} | 1 ⩽ j ⩽ i}). Then (1) ψ_{γ_{i}} is Σ_{i}-measurable for i = 1, …, n

(2) E(ψ_{γ_{i+1}} | Σ_{i}) = 0 for i = 1, …, n − 1.

Proof. Since ψ_{γ_{i}} is constant on each of the sets P_{γ_{i}}, N_{γ_{i}}, and X_{0} \(P_{γ_{i}} ∪N_{γ_{i}}), it is Σ_{i}-measurable. Fix 1 ⩽ i < n and consider E(ψ_{γ_{i+1}} | Σ_{i}). An atom A ⊂ X_{0} of Σ_{i} has the form

A = ⋂_{k=1}^{m} F_{k}

where

F_{k} ∈ ⋃_{j=1}^{i}{P_{γ_{j}} , N_{γ_{j}} , X_{0} \ (P_{γ_{j}} ∪ N_{γ_{j}})}

and γ_{i+1} < γ_{j} for j = 1, …, i. If γ_{i+1} < γ ∈ G, then P_{γ} (and likewise for N_{γ} and for X_{0}\(P_{γ}∪N_{γ})) is either disjoint from or contains the support of ψ_{γ_{i+1}}. Furthermore, ∫_{X} ψ_{γ_{i+1}} dμ is zero. Thus E(ψ_{γ_{i+1}} | Σ_{i}) = 0, as needed.

Now plant a whole forest F. Let {X_{α} | α ∈ F} be a nested partitioning for X with respect to F. Keeping with the notation from Section 4, write X as the disjoint union of X(κ)’s. For each κ ∈ K, the subcollection {X_{α} | α ∈ F(κ)} is a nested partitioning for X(κ) with respect to the tree F(κ); thus, there are wavelets Ψ(κ) as in (4) on X(κ). Let

Ξ = ⋃_{κ∈K} Ψ(κ) .

We are now able to state the main result of this paper.

Corollary 14. The wavelets Ξ forms a normalized unconditional basis for L_{p}(X, Σ, μ), with K_{p}(Ξ) ⩽ (p^{∗} − 1). If L_{p} is not purely atomic, then K_{p}(Ξ) = (p^{∗} − 1).

Proof. In light of Lemma 10 and Theorem 12, it suffices to show that (C2) holds with K = p^{∗} −1 for the set Ξ. Since X is the disjoint union of the X(κ)’s, for any f ∈ L_{p}

∥f∥_{p}^{p} = ∑_{κ∈K} ∥f 1_{X(κ)}∥_{p}^{p} .

Furthermore, for each κ ∈ K and γ ∈ G

ψ_{γ} 1_{X(κ)} = \begin{cases}ψ_{γ} & if γ ∈ F(κ) \\ 0 & if γ ∉ F(κ) . \end{cases}

Thus it suffices to show that (C2) holds with K = p^{∗} − 1 for each set Ψ(κ). Thus we assume, without loss of generality, that F is a tree and denote Ξ by just Ψ.

Keeping with previous notation, fix a finite collection Γ ⊂ G and order Γ = {γ_{i}}_{i=1}^{n} so that γ_{1} > γ_{2} > … > γ_{n}. Let {π_{i}}_{i=1}^{n} and {Σ_{i}}_{i=1}^{n} be as in the statement of Lemma 13. By Theorem 11, it suffices to show that the sequence {f_{i}}_{i=1}^{n} given by

f_{i} = ∑_{j=1}^{i} ψ_{γ_{j}}

is a simple martingale with respect to {Σ_{i}}_{i=1}^{n}.

Lemma 13 gives that each f_{i} is Σ_{i}-measurable. If i < n, then by Lemma 13 and the linearity of the conditional expectation operator

E(f_{i+1} | Σ_{i}) − E(f_{i} | Σ_{i}) = E(f_{i+1} − f_{i} | Σ_{i}) = E(ψ_{γ_{i+1}} | Σ_{i}) = 0 .

Since f_{i} is Σ_{i}-measurable, f_{i} = E(f_{i} | Σ_{i}). Thus E(f_{i+1} | Σ_{i}) = f_{i}, as needed.

Since Ξ is an unconditional basis for L_{p}, each ordering {ψ_{γ_{i}}}_{i=1}^{∞} of Ξ forms a basis for L_{p}. Given an ordering {γ_{i}}, the basis constant M_{p}({ψ_{γ_{i}}}) is the smallest number M for which

∥∑_{i=1}^{n} c_{i} ψ_{γ_{i}} ∥_{p} ⩽ M ∥∑_{i=1}^{m} c_{i} ψ_{γ_{i}} ∥_{p}

holds for all n, m ∈ N with n < m and all choices of c_{i} ∈ R. Clearly, 1 ⩽ M_{p}({ψ_{γ_{i}}}) ⩽ K_{p}(Ξ). In fact, if P_{p}({Ξ}) is the supremum of M_{p}({ψ_{γ_{i}}}) over all possible orderings of Ξ, then P_{p}({Ξ}) ⩽ K_{p}({Ξ}) ⩽ 2P_{p}({Ξ}). If M_{p}({ψ_{γ_{i}}}) = 1, then {ψ_{γ_{i}}} is a monotone basis.

A rooted tree can be enumerate {γ_{i}}_{i} so that γ_{i} > γ_{i+1}.

Corollary 15. The wavelets Ψ = {ψ_{γ_{i}}} associated with a rooted tree form a monotone basis for L_{p} when ordered so that γ_{i} > γ_{i+1}.

Proof. Fix n ∈ N and a sequence {c_{i}}_{i=1}^{n+1} from R. By Corollary 14, it suffices to show that

∥∑_{i=1}^{n} c_{i} ψ_{γ_{i}} ∥_{p} ⩽ ∥∑_{i=1}^{n+1} c_{i} ψ_{γ_{i}} ∥_{p} .

Consider the sub-σ-field Σ_{n} = σ ({π_{j} | 1 ⩽ j ⩽ n}) as in the statement of Lemma 13 with X_{0} = X. It follows from Lemma 13 that ∑_{i=1}^{n} c_{i} ψ_{γ_{i}} is Σ_{n}-measurable and that E(ψ_{γ_{n+1}} | Σ_{n}) = 0. Thus

∑_{i=1}^{n} c_{i} ψ_{γ_{i}} = E (∑_{i=1}^{n} c_{i} ψ_{γ_{i}} | Σ_{n})

= E (∑_{i=1}^{n} c_{i} ψ_{γ_{i}} | Σ_{n}) + c_{n+1}E (ψ_{γ_{n+1}} | Σ_{n})

= E (∑_{i=1}^{n+1} c_{i} ψ_{γ_{i}} | Σ_{n}) .

The result now follows from the fact that conditional expectation is a contraction on L_{p}.

7. Dual basis and characterization

Consider the coordinate functionals {ψ̃_{γ} | γ ∈ G} of the unconditional basis Ξ, which are (uniquely) determined by the condition ⟨ ψ_{γ′}, ψ̃_{γ} ⟩ = δ_{γγ′}. Since L_{p} is reflexive, {ψ̃_{γ} | γ ∈ G} forms an unconditional basis for the dual space L_{q}(X, Σ, μ) . Thus, if f ∈ L_{p} and g ∈ L_{q}, then

f = ∑_{γ∈G} ⟨ f, ψ̃_{γ} ⟩ ψ_{γ} and g = ∑_{γ∈G} ⟨ ψ_{γ}, g ⟩ ψ̃_{γ} , (12)

where the convergence is unconditional.

It follows from (6) that ψ̃_{γ} is a multiple of ψ_{γ}. Straightforward calculations give that if γ ∈ G^{∗} then

ψ̃_{γ} = ñ_{γ} (\frac{1_{P_{γ}}}{μ(P_{γ})} − \frac{1_{N_{γ}}}{μ(N_{γ})}) ,

where

ñ_{γ} = [n_{γ}(μ(P_{γ})^{−1} + μ(N_{γ})^{−1})]^{−1} ,

and if ρ ∈ G then

ψ̃_{ρ} = μ(X)^{−1/q} 1_{X} ,

while if ν ∈ G then

ψ̃_{ν} = μ(X)^{−1/q} 1_{X} .

It follows from Corollary 14 that 1 ⩽ ∥ψ̃_{γ} ∥_{q} ⩽ 2(p^{∗} − 1) for each γ ∈ G. If γ ∈ G \ G^{∗}, then

∥ψ̃_{γ} ∥_{q} = 1. For a fixed γ ∈ G^{∗},

∥ψ̃_{γ} ∥_{q} = ñ_{γ} (μ(P_{γ})^{1−q} + μ(N_{γ})^{1−q})^{1/q} ,

which need not be one. We examine this a little closer. Let

r = μ(P_{γ})/μ(N_{γ}) and N(p, r) = ∥ψ̃_{γ} ∥_{q} .

Then

N(p, r) = (1 + r^{1−p})^{1/p} (1 + r^{1−q})^{1/q} (1 + r^{−1})^{−1}.

The following properties of N(p, r) hold for 1 < p < ∞ and 0 < r < ∞:

(1) N(p, r) = N(q, r),

(2) N(p, r) = N(p, 1/r),

(3) N(p, 1) = N(2, r) = 1,

(4) 1 ⩽ N(p, r) ⩽ 2,

(5) for any fixed p, lim_{r→∞} N(p, r) = 1,

(6) for any fixed r, lim_{p→∞} N(p, r) = 2 (1 + r^{−1})^{−1}.

These easily can be verified. The uniform bound in (4) follows from bounding each factor which yields 2^{1/p} 2^{1/q} 1. Thus the norm of the coordinate functional is always less than 2, while the last property shows that it can be arbitrarily close to 2. If p = 2 or if μ(P_{γ}) = μ(N_{γ}) for each γ ∈ G^{∗}, then the dual basis is normalized.

Following the reasoning in [13, Chapter 6], we now derive a criterion, connected with the absolute value of the coefficients c_{γ}, to determine whether a formal series ∑ c_{γ} ψ_{γ} belongs to L_{p}. Towards this, we consider the Cantor group Δ ≡ {−1, 1}^{G} of all sequences ϵ (indexed by G) of ±1, along with its coordinate functionals e_{γ} : Δ → {−1, 1} determined by ϵ = {e_{γ}(ϵ)}_{γ∈G}, and its product (i.e. Bernoulli probability) measure ζ.

For each ϵ in Δ, let T_{ϵ} : L_{p} → L_{p} be the continuous (by (C2)) linear operator determined by

T_{ϵ} ψ_{γ} = e_{γ}(ϵ) ψ_{γ} .

Consider a function f ∈ L_{p} of the form

f = ∑_{γ∈Γ} c_{γ} ψ_{γ} (13)

for some finite subset Γ of G. So if ϵ ∈ Δ and x ∈ X then

(T_{ϵ}f)(x) = ∑_{γ∈Γ} e_{γ}(ϵ) c_{γ} ψ_{γ}(x) .

It follows from (C2) that

K_{p}^{−p} ∥f∥_{p}^{p} ⩽ ∥T_{ϵ} f∥_{p}^{p} ⩽ K_{p}^{p} ∥f∥_{p}^{p} (14)

where K_{p} is the unconditional basis constant of Ξ.

Since T_{ϵ}f(x) is product (μ × ζ)-measurable, Tonelli’s Theorem gives that

∫_{Δ} ∥T_{ϵ}f∥_{p}^{p} dζ(ϵ) = ∫_{X} ∫_{Δ} |∑_{γ∈Γ} e_{γ}(ϵ) c_{γ} ψ_{γ}(x)|^{p} dζ(ϵ) dμ(x) . (15)

Khinchin’s inequality (cf. [23]) gives strictly positive constants c_{p} and C_{p} so that

c_{p} ∥{a_{γ}}∥_{ℓ_{2}} ⩽ (∫_{Δ} |∑_{γ∈Γ} a_{γ} e_{γ}(ϵ)|^{p} dζ(ϵ))^{1/p} ⩽ C_{p} ∥{a_{γ}}∥_{ℓ_{2}} (16)

for each sequence {a_{γ}}_{γ∈Γ} of real numbers. Combining (16) and (15) yields

c_{p}^{p} ∫_{X} |(Af)(x)|^{p} dμ(x) ⩽ ∫_{Δ} ∥T_{ϵ}f∥_{p}^{p} dζ(ϵ) ⩽ C_{p}^{p} ∫_{X} |(Af)(x)|^{p} dμ(x) (17) where

(A f)(x) = (∑_{γ∈Γ} |c_{γ}|^{2} |ψ_{γ}(x)|^{2})^{1/2} . (18)

Next, integrate inequality (14) over Δ, note that ζ(Δ) = 1, and use (17) to see that

c_{p} K_{p}^{−1} ∥A f∥_{p} ⩽ ∥f∥_{p} ⩽ K_{p} C_{p} ∥A f∥_{p} . (19)

Consider any ordering {ψ_{γ_{i}}}_{i=1}^{∞} of Ξ and a function f ∈ L_{p}. The functions

f_{n} = ∑_{i=1}^{n} c_{γ_{i}} ψ_{γ_{i}} where c_{γ_{i}} = ⟨ f, ψ̃_{γ_{i}} ⟩

are of the form in (13) and thus satisfy (19). Furthermore, {f_{n}} converges in L_{p}-norm to f and {(Af_{n})} is a μ-a.e. increasing sequence of non-negative L_{p}-functions. Thus the (non-linear) mapping A in (18) extends to a mapping from L_{p} to L_{p}. Now follows the below characterization.

Theorem 16. If 1 < p < ∞, then

∑_{γ∈G} c_{γ} ψ_{γ} ∈ L_{p}  ⟺  (∑_{γ∈G} |c_{γ}|^{2} |ψ_{γ}(x)|^{2})^{1/2} ∈ L_{p} .

8. Multiresolution analysis

Wavelets are closely related to the concept of multiresolution analysis [9, 11, 13]. Traditionally wavelets are the translates and dilates of one particular function. Since we work with arbitrary partitions and non-translation invariant measures, our wavelets cannot be the translates and dilates of one function. In fact, they are a special case of so-called “second generation wavelets”. The basic idea of second generation wavelets is to give up the translation and dilation structure of wavelets, but to keep their desirable properties such as multiresolution analysis and fast transform algorithms. In this section we show how the unbalanced Haar wavelets fit into this concept. The fast wavelet transform will give us an algorithm to compute the coefficients in the expansions (12).

We define two new sets as

S(γ) = C_{l}(α) if γ ∈ G(α) and S^{∗}(β) = G(α) if β ∈ C_{l}(α) .

Now consider (7). The basis {φ_{β} | β ∈ C_{l}(α)} has dual basis

{φ̃_{β} | β ∈ C_{l}(α)} ,

where φ̃_{β} is a multiple of φ_{β} and \left∥{ \atop φ_{β}}\right∥_{q} = 1, while the other basis \{φ_{α}, ψ_{γ} | γ ∈ G(α)\} has dual basis

{φ̃_{α}, ψ̃_{γ} | γ ∈ G(α)} ,

where ψ̃_{γ} is as in Section 7. The basis functions in the above two bases are related as follows: (R1) for α ∈ F and γ ∈ G^{∗},

φ_{α} = ∑_{β∈C_{l}(α)} h_{α,β} φ_{β} and ψ_{γ} = ∑_{β∈S(γ)} g_{γ,β} φ_{β}

where

h_{α,β} = ⟨ φ_{α}, φ̃_{β} ⟩ and g_{γ,β} = ⟨ ψ_{γ}, φ̃_{β} ⟩

(R2) for β ≠ ρ,

φ_{β} = h̃_{p(β),β} φ_{p(β)} + ∑_{γ∈S^{∗}(β)} g̃_{γ,β} ψ_{γ}

where

h̃_{α,β} = ⟨ φ_{β}, φ̃_{α} ⟩ and g̃_{γ,β} = ⟨ φ_{β}, ψ̃_{γ} ⟩ .

For k ∈ g(F), let G_{k} = {γ ∈ G^{∗} | g(γ) = k} and consider the subspaces V_{k} and W_{k} of L_{p}, where

V_{k} = clos span {φ_{β} | β ∈ F_{k}^{∗}} and W_{k} = clos span {ψ_{γ} | γ ∈ G_{k}} .

Note that the indicated functions not only span, but also provide an unconditional basis for, these subspaces. The dual basis for this basis of V_{k} is given by

{φ̃_{β} | β ∈ F_{k}^{∗}}

while the dual basis for this basis of W_{k} is given by

{ψ̃_{γ} | γ ∈ G_{k}} .

By viewing F_{k−1}^{∗} ∪ F_{k}^{∗} as a two-generation forest, it follows that V_{k} = V_{k−1} ⊕ W_{k−1} (20) and that V_{k} has another basis

{φ_{α} | α ∈ F_{k−1}^{∗}} ∪ {ψ_{γ} | γ ∈ G_{k−1}}

with dual basis

{φ̃_{α} | α ∈ F_{k−1}^{∗}} ∪ {ψ̃_{γ} | γ ∈ G_{k−1}} .

A function f ∈ V_{k} has a representation as

f = ∑_{β∈F_{k}^{∗}} a_{β} φ_{β} with a_{β} = ⟨ f, φ̃_{β} ⟩ (21)

as well as, by (20),

f = ∑_{α∈F_{k−1}^{∗}} a_{α} φ_{α} + ∑_{γ∈G_{k−1}} c_{γ} ψ_{γ} (22)

with

a_{α} = ⟨ f, φ̃_{α} ⟩ and c_{γ} = ⟨ f, ψ̃_{γ} ⟩ .

The relations between the different representations follow from simple linear algebra arguments. To simplify notation, assume that the forest has no leaves, indeed, just replace each F_{k} with F_{k}^{∗}. Combining (21) and (R2) and identifying coefficients results in

a_{α} = ∑_{β∈C(α)} h̃_{α,β} a_{β} and c_{γ} = ∑_{β∈S(γ)} g̃_{γ,β} a_{β} , (23)

where g(β) = k and g(α) = g(γ) = k − 1. Similarly, combining (22) and (R1) results in

a_{β} = h_{p(β),β} a_{p(β)} + ∑_{γ∈S^{∗}(β)} g_{γ,β} c_{γ} . (24)

Next consider a function f ∈ V_{n} with n fixed. Given the scaling function coefficients a_{β} with g(β) = n, we can recursively use (23) to calculate all wavelet coefficients c_{γ} on the older generations where g(γ) < n. Conversely, given the coefficients a_{α} with g(α) = m along with all the wavelet coefficients c_{γ} where m ⩽ g(γ) < n, we can recursively use (24) to find the coefficients a_{β} on the younger generation where g(β) = n.

These operations form the so-called “fast wavelet transform”. Since all summations in the transform are finite, it can easily be implemented on a computer. One only needs to build a forest data structure that satisfies all the forest properties of Section 3. This can be done nicely using an object-oriented programming language.

The way the algorithm is described, the number of operations for the calculation of the wavelet coefficients c_{γ} with γ ∈ G(α) is O(m^{2}). Actually, by using the hierarchy of T_{M}, one can reduce this to O(m). In Example 7 (dyadic cubes on R^{n}) we have m = 2^{n} and this difference can become important. We do not include the details of this algorithm as they are straightforward.

9. Euclidean spaces

One of the original motivations for the construction of the unbalanced Haar wavelets was their use in practical applications; thus, we take a closer look at the case where X is a subset of R^{n}.

Consider the topology induced by the Euclidean distance d on R^{n}. Let X be a Borel set of R^{n} and B(X) be the Borel subsets of X. Consider a σ-finite measure μ on B(X) and let (X, M(X), μ) be the μ-completion of (X, B(X), μ). A common practical example is a weighted measure μ where dμ = w dm for the Lebesgue measure m on X and a non-negative Lebesgue measurable function w; if w is a non-zero constant function, then M(X) are just the Lebesgue measurable subsets of X.

Assume that we start with (X, M(X), μ). Next we are given subsets {X_{α} | α ∈ F} of X that satisfy the partition properties from Section 4. Such subsets usually are determined by the application; numerical solvers for integral and differential equations often recursively subdivide an original domain X into the X_{α}’s, as illustrated in Example 8. Keeping with the previous notation, σ({X_{α} | α ∈ F}) = Σ̃ and the μ-completion of (X, Σ̃) is (X, Σ). We would like an easily verifiable condition on {X_{α} | α ∈ F} that would guarantee that Σ = M(X); for then, the corresponding wavelets form an unconditional basis for L_{p}(X, M(X), μ). Towards this, two useful measurement are the diameter of S ⊂ R^{n} given by

diam S = sup_{x, y∈S} d (x, y)

and the (μ-)essential diameter of S ∈ M(X) given by

ess diam S = inf {diam Y | Y ⊂ S , Y ∈ M(X) , μ(S \ Y) = 0} .

If X_{α} is in B(X) for each α ∈ F and if for each x ∈ X

inf_{\begin{matrix}α∈F \\ x∈X_{α} \end{matrix}} diam X_{α} = 0 , (25)

then Σ̃ = B(X) and so Σ = M(X). It is possible to relax condition (25).

Proposition 17. If X_{α} is in M(X) for each α ∈ F and if for each x ∈ X

(26)  inf_{\begin{matrix}α∈F \\ x∈X_{α} \end{matrix}} ess diam X_{α} = 0 ,

then Σ = M(X).

As customary, for y ∈ R^{n} and ϵ > 0, let

N_{ϵ}(y) = {x ∈ X | d(x, y) < ϵ} .

Proof. Since Σ̃ ⊂ M(X), it suffices to show that B(X) ⊂ Σ. Towards this, fix any δ and ϵ with 0 < δ < ϵ and y ∈ R^{n}. It suffices to find a set N_{δ} ∈ Σ so that N_{δ}(y) ⊂ N_{δ} ⊂ N_{ϵ}(y).

For each x ∈ N_{ϵ}(y), find decreasing sequences {X_{α_{n}(x)}}_{n} and {Y_{α_{n}(x)}}_{n} along with a sequence {y_{α_{n}(x)}}_{n} so that

(1) x ∈ X_{α_{n}(x)}

(2) y_{α_{n}(x)} ∈ Y_{α_{n}(x)} ⊂ X_{α_{n}(x)}

(3) μ (X_{α_{n}(x)} \ Y_{α_{n}(x)}) = 0

(4) lim_{n} diam Y_{α_{n}(x)} = 0

(5) lim_{n} y_{α_{n}(x)} = y_{0}(x) for some y_{0}(x) ∈ R^{n} . If d(y, y_{0}(x)) < ϵ, then pick α_{n}(x) so that

Y_{α_{n}(x)} ⊂ N_{ϵ}(y)

and if d(y, y_{0}(x)) ⩾ ϵ, then pick α_{n}(x) so that

Y_{α_{n}(x)} ⊂ [N_{δ}(y)]^{C} .

Since

N_{ϵ}(y) ⊂ ⋃_{x∈N_{ϵ}(y)} X_{α_{n}(x)}

there is a countable subset {x_{i} | i ∈ J} of N_{ϵ}(y) such that

N_{ϵ}(y) ⊂ ⋃_{i∈J} X_{i}

where X_{α_{n}(x_{i})} = X_{i}. Likewise, set Y_{α_{n}(x_{i})} = Y_{i}. Let J_{0} = {i ∈ J | d(y, y_{0}(x_{i})) < ϵ} and

N_{δ} = [ ⋃_{i∈J} (X_{i} \ Y_{i}) ∩ N_{δ} (y) ] ⋃ [ ⋃_{i∈J_{0}} Y_{i} ] .

Then N_{δ}(y) ⊂ N_{δ} ⊂ N_{ϵ}(y) and N_{δ} ∈ M(X). Thus N_{ϵ}(y) ∈ Σ, as needed.

The use of the unbalanced Haar wavelets in applications is still somehow limited. The reason is that they are non-smooth and that they have only one vanishing moment; i.e. the integral of a wavelet vanishes, but the integral of a wavelet multiplied with a non-constant polynomial need not vanish. Consequently, the convergence of the expansion (12) is slow for a smooth function f. In [21, 20] the “lifting scheme” is described, which given one initial multiresolution analysis, can allows you to build a second, more performant one, in the sense that the wavelets have more vanishing moments or more smoothness. The Haar wavelets constructed in this paper are a perfect example for such an initial multiresolution analysis.

Acknowledgements. The work presented here benefited from stimulating and inspiring discussions with Donald Burkholder, Stephen Dilworth, Björn Jawerth, James Roberts, and Peter Schröder.

References

1. L. Andersson, B. Jawerth, and M. Mitrea. The Cauchy singular integral operator and Clifford wavelets. In [2], pages 525–546.

2. J. Benedetto and M. Frazier, editors. Wavelets: Mathematics and Applications. CRC Press, Boca Raton, 1993.

3. P. Billingsley. Probability and Measure. Wiley Series in Probability and Mathematical Statistics. John Wiley and Sons, New York, 1986.

4. D. L. Burkholder. A nonlinear partial differential equation and the unconditional constant of the Haar system in L^{p}. Bull. Amer. Math. Soc. (N.S.), 7:591–595, 1982.

5. D. L. Burkholder. Boundary value problems and sharp inequalities for martingale transforms. Ann. Probab., 12:647–702, 1984.

6. D. L. Burkholder. An elementary proof of an inequality of R. E. A. C. Paley. Bull. London Math. Soc., 17:474–478, 1985.

7. D. L. Burkholder. Explorations in martingale theory and its applications. In Ecole d’Eté de Probabilités de Saint-Flour XIX — 1989, volume 1464 of Lecture Notes in Mathematics, pages 1–66. Springer-Verlag, Berlin, 1991.

8. D. L. Burkholder and R. F. Gundy. Extrapolation and interpolation of quasi-linear operators on martingales. Acta Math., 124:249–304, 1970.

9. I. Daubechies. Ten Lectures on Wavelets. CBMS-NSF Regional Conf. Series in Appl. Math., Vol. 61. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992.

10. J. Lindenstrauss and A. Pełczyński. Contributions to the theory of classical Banach spaces. J. Funct. Anal., 8:225–249, 1971.

11. S. G. Mallat. Multiresolution approximations and wavelet orthonormal bases of L_{2}. Trans. Amer. Math. Soc., 315(1):69–87, 1989.

12. J. Marcinkiewicz. Quelques théorèmes sur les séries orthogonales. Ann. Soc. Polon. Math., 16:84–96, 1937. (pages 307-318 of the Collected Papers).

13. Y. Meyer. Ondelettes et Opérateurs, I: Ondelettes, II: Opérateurs de Calderón-Zygmund, III: (with R. Coifman), Opérateurs multilinéaires. Hermann, Paris, 1990. English translation of first volume, Wavelets and Operators, is published by Cambridge University Press, 1993.

14. M. Mitrea. Singular integrals, Hardy spaces and Clifford wavelets. Number 1575 in Lecture Notes in Math. 1994.

15. A. M. Olevskiĭ. Fourier series and Lebesgue functions. Uspehi Mat. Nauk., 22:237–239, 1967. (Russian).

16. A. M. Olevskiĭ. Fourier series with respect to general orthogonal systems. Springer-Verlag, New York, 1975.

17. R. E. A. C. Paley. A remarkable series of orthogonal fuctions. Proc. London Math. Soc., 34:241–279, 1932.

18. A. Pełczyński. On the impossibility of imbedding the space L in certain Banach spaces. Colloq. Math., 8:199–203, 1961.

19. P. Schröder and W. Sweldens. Spherical wavelets: Efficiently representing functions on the sphere. Computer Graphics Proceedings, (SIGGRAPH 95), pages 161–172, 1995.

20. W. Sweldens. The lifting scheme: A construction of second generation wavelets. Technical Report 1995:6, Industrial Mathematics Initiative, Department of Mathematics, University of South Carolina, 1995^{∗}.

21. W. Sweldens. The lifting scheme: A custom-design construction of biorthogonal wavelets. Appl. Comput. Harmon. Anal., 3(2):186–200, 1996.

22. P. Wojtaszczyk. Banach spaces for analysts. Cambridge studies in advanced mathematics. Cambridge University Press, Cambridge, 1991.

23. A. Zygmund. Trigonometric Series. Cambridge University Press, London, 2nd edition, 1959.

Department of Mathematics, University of South Carolina, Columbia SC 29208 E-mail address: girardi@math.sc.edu

Department of Mathematics, University of South Carolina

Katholieke Universiteit Leuven, Belgium, Department of Computer Science

Current: Bell Laboratories, Lucent Technologies, 700 Mountain Avenue, Murray Hill NJ 07974

E-mail address: wim@bell-labs.com