On the almost everywhere convergence of wavelet summation methods

Terence Tao

Abstract

Let ψ be a rapidly decreasing one-dimensional wavelet. We show that the wavelet expansion of any Lp function converges pointwise almost everywhere under the wavelet projection, hard sampling, and soft sampling summation methods, for 1 < p < ∞. In fact, the partial sums are uniformly dominated by the Hardy-Littlewood maximal function.

0. Introduction

In this note we will discuss the almost everywhere convergence of various summation methods for wavelet expansions. We shall not aim for maximal generality; instead, we will restrict our attention to the expansion of an L^{p} function f in one dimension, for 1 < p < ∞, generated by a 0-regular orthogonal wavelet ψ. By this we mean that ψ has integral 0, is bounded and rapidly decreasing, and that the set of functions {ψ_{j,k}} = {2^{j/2}ψ(2^{j} · −k)} for j, k ∈ Z, form an orthonormal basis for L^{2}(R). The wavelet expansion of f is given by f ∼ ∑_{j,k} a_{j,k}ψ_{j,k}, where a_{j,k} = ⟨f, ψ_{j,k}⟩. In [4] it is shown that this series converges unconditionally in L^{p} norm to f; however, the pointwise behaviour of this series is more dependent on the summation method used and is less well understood. The summation methods that are used in applications almost always rely on one of the following three partial summation operators:

the wavelet projections  P_{J}f = ∑_{j<J;k} a_{j,k}ψ_{j,k};
the hard sampling operators  T_{λ}f = ∑_{|a_{j,k}|>λ} a_{j,k}ψ_{j,k};
the soft sampling operators  T̃_{λ}f = ∑_{|a_{j,k}|>λ} sgn(a_{j,k})(|a_{j,k}| − λ)ψ_{j,k}.

Note that the sum in P_{J}f converges absolutely since ψ is rapidly decreasing and a_{j,k} = O(2^{−j/2}2^{j/p}∥f∥_{p}), by Hölder’s inequality. We shall prove the absolute convergence of the other two sums in the next section (though for p ≥ 2 one always has a finite number of terms).

Theorem 1. If f ∈ L^{p}(R) for some 1 < p < ∞, then for almost every x one has

lim_{J→∞} P_{J}f(x) = lim_{λ→0} T_{λ}f(x) = lim_{λ→0} T̃_{λ}f(x) = f(x).

The almost everywhere convergence of the wavelet projection operators was already shown (under more general hypotheses) in [3]. The non-linear hard and soft sampling methods are used frequently in applications 1991 Mathematics Subject Classification. Primary 42C15; Secondary 40A30.

Keywords: hard sampling, soft sampling, almost-everywhere convergence.

(see [1],[2]) but this seems to be the first pointwise convergence result for these methods. In contrast, we have learned recently that T.W. Körner has found a counterexample to the pointwise convergence of the hard sampling operator for the Fourier series expansion. We also note that if one assumes some minimal regularity (e.g. right-continuity) for ψ, then one can get the pointwise convergence of the operators of Theorem 1 on the entire Lebesgue set of f (c.f. [3]).

Finally, we show that there are (somewhat artificial) wavelet summation methods which need not converge pointwise, at least for wavelets with little regularity.

Theorem 2. Suppose that ψ is the Haar wavelet χ_{[0,1/2)} − χ_{[1/2,1)}. Fix α > 0, 1 < p < ∞ and consider the operator T_{λ}^{α} defined on L^{p}(R) for λ > 0 by

T_{λ}^{α}f = ∑_{|a_{j,k}|≥α^{j}λ} a_{j,k}ψ_{j,k}

(a) If α ≠ 2^{−1/2}, then for all f ∈ L^{p}, one has lim_{λ→0} T_{λ}^{α}f(x) = f(x) at every Lebesgue point x of f.

(b) If α = 2^{−1/2}, then there exists an f ∈ L^{p} for which lim sup_{λ→0} |T_{λ}^{α}f(x)| = ∞ for all x ∈ R.

The series defining T_{λ}^{α}f need not converge absolutely; if this is the case, we shall define the value of the series to be the pointwise limit (where it exists) of its formal wavelet projections, so

T_{λ}^{α}f(x) = lim_{J→∞} ∑ ; \begin{aligned}|a_{j,k}| & ≥ α^{j}λ \\ j & < J \end{aligned} a_{j,k}ψ_{j,k}(x).

The operator T_{λ}^{α} can be thought of as a variant of the hard thresholding operator T_{λ}, but with a weighted threshold that depends on the resolution level. The reason that convergence fails when α = 2^{−1/2} can be sketched as follows. For this value of α one is effectively applying a threshold to the “heights” of the summands a_{j,k}ψ_{j,k} rather than to the co-efficients a_{j,k}. By “fine-tuning” the magnitudes of terms with comparable heights, one can effectively sum such terms in an arbitrary order, and (with a suitable choice of ordering) this allows one to get large non-cancellatory contributions to the partial sums T_{λ}f(x) for each x (the exact values of λ for which non-cancellation occurs depends on x). The ability to get significant non-cancellation seems to be due to the lack of regularity (both smoothness and moment conditions) of the Haar wavelet; it may be possible that better convergence results can be obtained for more regular wavelets.

The work in this paper originated from a question posed by Elias Stein. The author also thanks Anna Gilbert for her proofreading, the loan of several books and articles, and for many valuable discussions.

1. Proof of Theorem 1.

In the following the symbol C will denote various constants that depend only on ψ. In order to make the notion of a Lebesgue point well defined, we shall not adopt the practice of identifying functions which agree almost everywhere. Recall that a point x ∈ R is a Lebesgue point of f if \frac{1}{2r} ∫_{−r}^{r} |f(x + t) − f(x)| dt converges to 0 as r tends to 0; it is a classical theorem of Lebesgue that, for any locally integrable function f, almost every element of R is a Lebesgue point of f. Closely related to the concept of Lebesgue point is the Hardy-Littlewood maximal operator M; this sublinear operator is defined by

Mf(x) = sup_{r>0} \frac{1}{2r} ∫_{−r}^{r} |f(x + t)| dt.

Many expressions, especially ones involving approximations to the identity, can be controlled in magnitude by the maximal function. In particular, if ϕ(x) is a function such that |ϕ(x)| ≤ C_{N}A(1 + \frac{|x−x_{0}|}{r})^{−N} for all N > 0 and some fixed A,r,x_{0}, then

| ∫_{R} f(x)ϕ(x) dx| ≤ CArMf(x_{0}).

Another such estimate is the simple inequality |f(x)| ≤ Mf(x) ≤ ∥f∥_{∞}, which holds whenever x is a Lebesgue point of f. Proofs of these statements can be found in [5].

Let f be an arbitrary function in L^{p}(R). We first show that to prove Theorem 1, it suffices to show the pointwise estimates

sup_{J} |P_{J}f(x)|, sup_{λ} |T_{λ}f(x)|, sup_{λ} |T̃_{λ}f(x)| ≤ CMf(x)  (1)

for almost every x. If our operators were linear, the implication would follow from standard arguments (see [5]), but only the P_{J} are linear and so the argument requires a little care. We shall show the argument for the T̃_{λ} only, as it is the most non-linear of the three; the proof for the other two operators is analogous (and can be simplified slightly). Assume now that (1) holds for some fixed f and x. Since we only require convergence almost everywhere, we may assume that x is a Lebesgue point of f and of every ψ_{j,k}. Choose any ε > 0. By the usual method of convolving f with a smooth approximation to the identity, and using the fact that x is a Lebesgue point of f, and that f is in an L^{p} class for some finite p, one can find a g in C_{0}^{∞}(R) for which |M(f −g)(x)| ≤ Cε. In turn, one can approximate g uniformly almost everywhere by a finite linear combination h of wavelets (for this fact, see [4]). Thus one can find such an h for which |f(x) − h(x)| ≤ |M(f − h)(x)| ≤ Cε. To conclude the argument, one observes that T̃_{λ}f(x) = h(x) + T̃_{λ}(f − h)(x) + O_{h}(λ) as λ → 0. To see this, note that the wavelet co-efficients of T̃_{λ}f and h + T̃_{λ}(f − h) differ by O(λ) when the wavelet occurs in the expansion of h, and are identical otherwise. Thus |T̃_{λ}f(x) − f(x)| = O(ε) for sufficiently small λ, so lim_{λ→0} T̃_{λ}f(x) = f(x), as desired.

We now show that (1) holds for the P_{J}. We note that this estimate was first proven in [3] under weaker decay hypotheses on ψ and f; we shall give an alternative proof below. The argument relies on two observations. The first is the crude estimate

|ψ_{j,k}(x)\overline{ψ_{j,k}(y)}| ≤ C_{N}2^{−j}(1 + 2^{j}|x − y|)^{−N}(1 + |2^{j}x − k|)^{−N}  (2)

for all N > 0; this is a simple consequence of the rapid decrease of ψ and the easy inequality 1 + 2^{j}|x − y| ≤ (1 + |2^{j}x − k|)(1 + |2^{j}y − k|). The second is the fact that

∑_{j,k} ψ_{j,k}(x)\overline{ψ_{j,k}(y)} = 0

for almost every x, y ∈ R. Note that this sum converges absolutely for x ≠ y by (2). The identity follows from the fact that the {ψ_{j,k}}_{j,k∈Z} form an orthonormal basis for L^{2}(R), so that the above summation converges in a distributional sense to δ(x − y). Since the series converges both distributionally and absolutely almost everywhere, the two limits must agree almost everywhere, hence the claim.

As a consequence of these two observations, we see that the kernel defined almost everywhere by

K(x, y) = ∑_{j<0;k} ψ_{j,k}(x)\overline{ψ_{j,k}(y)} = − ∑_{j≥0;k} ψ_{j,k}(x)\overline{ψ_{j,k}(y)}

converges absolutely and is bounded and rapidly decreasing away from the diagonal. However, we have

P_{J}f(x) = ∑_{j<J;k} ψ_{j,k}(x) ∫_{R} \overline{ψ_{j,k}(y)}f(y) dy

= ∫_{R} ∑_{j<J;k} ψ_{j,k}(x)\overline{ψ_{j,k}(y)}f(y) dy

= ∫_{R} 2^{J}K(2^{−J}x, 2^{−J}y)f(y) dy

from Fubini’s theorem; the conditions for Fubini’s theorem follow from (2), the fact that f is in an L^{p} class for some p > 1, and Hölder’s inequality. Since K(2^{−J}x, 2^{−J}y), as a function of y, is rapidly decreasing away from x, the desired estimate (1) now follows from the maximal function estimates mentioned at the start of this section.

We now show that (1) holds for the T_{λ}. Fix f ∈ L^{p}(R), λ ∈ R, and x ∈ R. Since we may assume that Mf(x) is nonzero, we can choose a J for which λ ∼ 2^{−J/2}Mf(x); one can think of J as the finest scale for which significant terms in the summation for T_{λ}f(x) can appear. We will show that |T_{λ}f(x) − P_{J}f(x)| ≤ CMf(x), which will imply (1) from our results for the P_{J}. We shall first need some simple estimates. For each j, k ∈ Z, let D(j, k) be the integer part of 2 + |2^{j}x − k|. Note that for each j and for each integer d ≥ 2 there are at most two k for which D(j, k) = d. From the rapid decrease of ψ and the usual estimates on approximations to the identity, we have that, for all N > 0,

\begin{aligned}|ψ_{j,k}(x)| & ≤ C_{N}2^{j/2}D(j, k)^{−N} and \\ |a_{j,k}| & ≤ C2^{−j/2}D(j, k)Mf(x); thus \\ |a_{j,k}ψ_{j,k}(x)| & ≤ C_{N}D(j, k)^{−N}Mf(x). \end{aligned}

Note that the second estimate implies that |a_{j,k}| is greater than λ only if j < J + C log D(j, k).

The estimate for |T_{λ}f(x) − P_{J}f(x)| is now straightforward. Indeed, we have

|T_{λ}f(x) − P_{J}f(x)| = | ∑_{|a_{j,k}|>λ} a_{j,k}ψ_{j,k}(x) − ∑_{j<J;k} a_{j,k}ψ_{j,k}(x)|

≤ | ∑_{|a_{j,k}|≤λ;j<J} a_{j,k}ψ_{j,k}(x)| + | ∑_{|a_{j,k}|>λ;J≤j} a_{j,k}ψ_{j,k}(x)|

≤ ∑_{j<J;k} λ|ψ_{j,k}(x)| + ∑_{J≤j<J+C log D(j,k)} |a_{j,k}ψ_{j,k}(x)|

≤ ∑_{d=2}^{∞} ∑_{j<J} C_{N}λ2^{j/2}d^{−N} + ∑_{d=2}^{∞} ∑_{J≤j<J+C log d} C_{N}d^{−N}Mf(x)

≤ Cλ2^{J/2} + ∑_{d=2}^{∞} CMf(x)d^{−N} log d

≤ CMf(x) + CMf(x),

as desired. Note that this argument also shows that the sum defining T_{λ}f(x) is absolutely convergent, since we know the sum for P_{J}f(x) is.

The proof of (1) for T̃_{λ} is almost identical to that for T_{λ}, although one must use the estimate

∑_{|a_{j,k}|>λ;j<J} sgn(a_{j,k})(|a_{j,k}| − λ)ψ_{j,k}(x) = ∑_{j<J;k} a_{j,k}ψ_{j,k}(x) + O( ∑_{j<J;k} λ|ψ_{j,k}(x)|)

in the above argument; we omit the details. Thus (1) holds for all three operators under consideration, and the theorem is proved. □

We remark that these results can be extended easily to higher dimensions, to bi-orthogonal wavelets, and to decompositions involving more than one “mother wavelet”. The decay conditions on ψ can also be relaxed; for instance, one can get the pointwise convergence result for the P_{J} alone if one merely assumes that ψ has an integrable radial majorant. The proofs of these assertions are simple applications of the ideas developed in [3].

2. Proof of Theorem 2.

The proof of (a) is an easy generalization of the corresponding argument for the T_{λ} in the proof of Theorem 1, although if α < 2^{−1/2} one has to use I − P_{J} instead of P_{J} as the approximating operator. (Here J is chosen so that α^{J}λ ∼ 2^{−J/2}Mf(x)). We omit the details. Instead of using the argument in the previous section to bound P_{J}, one can compute P_{J}f explicitly to achieve estimate (1) for all x ∈ R, which will ensure pointwise convergence at every Lebesgue point, and not just almost everywhere. Alternatively, one can use the methods in [3].

Now suppose that α = 2^{−1/2}. We shall construct, for each integer N ≥ 1, a function f_{N} = ∑_{j,k} a_{j,k}^{N}ψ_{j,k} on [0, 1) for which:

(i) All but a finite number of the a_{j,k}^{N} are 0 and those that are not zero satisfy 1 < 2^{j/2}a_{j,k}^{N} < 2;

(ii) ∥f_{N}∥_{p} ≤ C_{p}N^{1/2} for every 1 < p < ∞;

(iii) sup_{λ} |T_{λ}^{α}f_{N}(x)| > N/3 for every x ∈ [0, 1).

Once we do this, one can see that, if one chooses an increasing sequence of natural numbers M_{i} whose successive differences are sufficiently large, the function

F (x) = ∑_{i=1}^{∞} 2^{−i} ∑_{k=0}^{2^{M_{i}} −1} f_{3^{i}}(2^{M_{i}}x − k)

will be in L^{p}([0, 1)) for every 1 < p < ∞, but is such that lim sup_{λ} |T_{λ}^{α}F (x)| = ∞ for every x ∈ [0, 1). The function f(x) = ∑_{n=−∞}^{∞} 2^{−|n|}F (x − n) thus satisfies all the required conditions in (b).

We shall define f_{N} explicitly:

f_{N}(x) = ∑_{j=0}^{N−1} ∑_{k=0}^{2^{j}−1}(1 + 2^{−j}(k + \frac{1}{2}))ψ(2^{j}x − k).

The reason for this particular choice of co-efficients is that each T_{λ}^{α}f_{N} will consist only of the terms a_{j,k}^{N}ψ_{j,k} corresponding to wavelets whose “centers” are to the right of λ − 1. At x = λ − 1, the nature of the Haar wavelet will cause this sum to be large and positive.

We now show that f_{N} has the properties (i-iii) stated above. The verification of (i) is immediate, and (ii) follows quickly from Khinchin’s inequality (see [4]). To prove (iii), fix an x ∈ [0, 1) and observe that all but N of the factors ψ(2^{j}x − k) in the sum defining f_{N}(x) are zero, and the remainder are either +1 or −1. Furthermore, this factor is nonnegative if 1 + 2^{−j}(k + \frac{1}{2}) > 1 + x and nonpositive otherwise. Thus, by inspection of the definition of T_{λ}^{α} for λ = 1 + x and λ = 2, we have

\begin{aligned}T_{1+x}^{α}f(x) & = ∑_{ψ(2^{j}x−k)=+1}(1 + 2^{−j}(k + \frac{1}{2})), and \\ T_{1+x}^{α}f(x) − T_{2}^{α}f(x) & = ∑_{ψ(2^{j}x−k)=−1}(1 + 2^{−j}(k + \frac{1}{2})); so \\ 2T_{1+x}^{α}f(x) − T_{2}^{α}f(x) & = ∑_{ψ(2^{j}x−k)≠0}(1 + 2^{−j}(k + \frac{1}{2})) > N, \end{aligned}

which implies (iii). This proves the theorem. □

References

[1] A. Averbuch, G. Beylkin, R. Coifman, M. Israeli, Fast Adaptive Algorithm for the Elliptic equations with periodic boundary conditions, preprint.

[2] D.L. Donoho, I.M. Johnstone, Ideal spatial adaptation by wavelet shrinkage, Biometrika 81 (1994), 425-455.

[3] S. Kelly, M.A. Kon, and L.A. Raphael, Local convergence for wavelet expansions, J. Funct. Anal. 126 (1994), 102-138.

[4] Y. Meyer, “Ondelettes”, Hermann, Paris, 1990.

[5] E. Stein, “Singular Integrals and Differentiability Properties of Functions”, Princeton University Press, 1970.

Department of Mathematics Princeton University Princeton, NJ 08544 tao@math.princeton.edu