Harmonic Analysis of the space BV ^{∗}

Albert Cohen, Wolfgang Dahmen, Ingrid Daubechies and Ronald DeVore

January 22, 2001

Abstract

We establish new results on the space BV of functions with bounded variation. While it is well known that this space admits no unconditional basis, we show that it is “almost” characterized by wavelet expansions in the following sense: if a function f is in BV, its coefficient sequence in a BV normalized wavelet basis satisfies a class of weak-ℓ^{1} type estimates. These weak estimates can be employed to prove many interesting results. We use them to identify the interpolation spaces between BV and Sobolev or Besov spaces, and to derive new Gagliardo-Nirenberg-type inequalities.

AMS subject classification: 42C40, 46B70,26B35 , 42B25.

Key Words: Bounded variation, wavelet decompositions, weak ℓ_{1}, K-functionals, interpolation, Gagliardo-Nirenberg inequalities, Besov spaces.

1 Background and main results

Many classical function spaces - such as the Sobolev, Hölder or Besov classes - can be characterized by harmonic analysis methods through Fourier or wavelet bases, frames, Littlewood-Paley decompositions, approximation by spline functions, etc. Such characterizations are classically useful in various contexts such as operator theory or the theoretical and numerical analysis of PDEs.

More recently, several results in data compression and statistical estimation have shown that optimal algorithms for such applications can be derived from expansions into unconditional bases for the function space that models the object to be compressed or estimated (see [11] and [8]). By definition a sequence (e_{n})_{n≥0} in a Banach space X is an unconditional basis if and only if (i) It is a Schauder basis, i.e., for every x ∈ X there exists a unique sequence (x_{n})_{n≥0} such that lim_{N→+∞} ∥x − ∑_{n=0}^{N} x_{n}e_{n}∥_{X} = 0.

∗This work has been supported by the National Science Foundation Grants DMS-9872890 and DMS-9706753, by the Office of Naval Research Contract N0014-91-J1343, by Air Force for Scientific Research contract F 49620-98-1-0044, by the European Commission TMR Project “Wavelets and Multiscale Methods in Numerical Analysis and Simulation”, No. ERB FMRX CT98 018TA, and by DAAD PROCOPE “Multiscale Methods in Numerical Analysis”.

(ii) There exists a constant C such that for all finite sequences (x_{n})_{n=0}^{N} and (y_{n})_{n=0}^{N} such that |y_{n}| ≤ |x_{n}|, one has ∥ ∑_{n} y_{n}e_{n}∥_{X} ≤ C∥ ∑_{n} x_{n}e_{n}∥_{X}.

In other words, the space X can be characterized by the size properties of the coefficients describing its elements in terms of the basis (e_{n})_{n≥0}. This means that numerical operations, such as thresholding, attenuating, or rounding-off the coefficients, are stable in the X norm. The early development of wavelet bases (see [13]) is closely related to the question of existence of an unconditional basis for the Hardy space H_{1}. It is now well established that wavelet bases are unconditional bases for most classical function spaces that are known to possess one. On the other hand, certain spaces such as L_{1}, C_{0}, W^{1}(L_{1}) and BV are known to possess no unconditional basis of any type.

The space BV, consisting of functions with bounded variation, is of particular interest for applications to data compression and statistical estimation. It is often chosen as a model for piecewise smooth signals such as geometric images. Recall that, if Ω is an open set of ℝ^{d}, a function f ∈ L_{1}(Ω) has bounded variation if and only if its distributional gradient ∇f is a finite measure, i.e., if its total variation

|f|_{BV(Ω)} := sup{∫_{Ω} f div(g) ; g ∈ C_{c}^{1}(Ω, ℝ^{d}), ∥g∥_{∞} ≤ 1},  (1.1)

is finite. Here, for g = (g_{1}, …, g_{d}), ∥g∥_{∞} := ∥ (∑_{i=1}^{d} g_{i}^{2})^{1/2} ∥_{L_{∞}(Ω)}. The space of such functions is denoted as BV = BV(Ω). It is a Banach space when equipped with the norm

∥f∥_{BV(Ω)} := ∥f∥_{L_{1}(Ω)} + |f|_{BV(Ω)}.  (1.2)

If a function f ∈ BV(Ω) is in the smaller Sobolev space W^{1}(L_{1}(Ω)), we can apply integration by parts in (1.1) and obtain that

|f|_{BV(Ω)} := ∫_{Ω} |∇f|.  (1.3)

It was recently shown ([4]) that, although BV does not possess an unconditional basis, it is “almost” characterized by wavelet decompositions in terms of weak-type conditions imposed on wavelet coefficients. Using this information about BV, it is possible to derive optimal compression or estimation algorithms based on wavelet thresholding.

In order to describe this result, as well as the results of the present paper, we briefly discuss wavelet bases. We shall confine our discussion to the d-dimensional wavelet bases that are derived from a tensor product multiresolution analysis (see [7] or [13] for a detailed treatment) although this is not essential.

Consider first the case of orthogonal wavelet bases. Let ψ^{0} = φ be a univariate, compactly supported scaling function associated with the compactly supported, orthogonal univariate wavelet ψ^{1} = ψ. Let E′ := {0, 1}^{d} be the vertices of the unit cube and E denote the set of nonzero vertices. For each e ∈ E′, we define

ψ^{e}(x) = ψ^{e_{1}}(x_{1}) ⋯ ψ^{e_{d}}(x_{d}).  (1.4)

Let D denote the set of dyadic cubes in ℝ^{d} and let D_{j} denote those dyadic cubes that have side length 2^{−j}. For any dyadic cube I = 2^{−j}(k + [0, 1]^{d}) in D_{j}, and any e ∈ E′, we define the wavelet

ψ_{I}^{e}(x) := 2^{j(d−1)}ψ^{e}(2^{j}x − k),  (1.5)

which is a wavelet scaled relative to I. Note that we have normalized the wavelets ψ_{I}^{e} in BV(ℝ^{d}) and not, as is more customary, in L_{2}(ℝ^{d}). (For d = 2, the two normalizations coincide.) It follows that

C_{1} ≤ |ψ_{I}^{e}|_{BV} ≤ C_{2},  (1.6)

where the constants C_{1} and C_{2} depend only on the BV(ℝ) norms of the univariate functions φ and ψ. Note also that we can replace the seminorm | · |_{BV} in (1.6) by the norm ∥ · ∥_{BV} as long as the size of the cubes I remains bounded. The functions

ψ_{I}^{e}, I ∈ D, e ∈ E,  (1.7)

form a complete orthogonal system in L_{2}(ℝ^{d}).

There is a similar construction of biorthogonal wavelet bases, see e.g. [7]. We start with a pair of one-dimensional compactly supported scaling functions ψ^{0} := φ and ψ̃^{0} = φ̃ which are in duality:

∫_{ℝ} φ(t)φ̃(t − k) dt = δ(k), k ∈ ℤ,  (1.8)

with δ the Kronecker delta, and their corresponding univariate wavelets ψ^{1} := ψ and ψ̃^{1} := ψ̃. We define the functions ψ_{I}^{e} as in (1.5) and ψ̃_{I}^{e} similarly except that the factor 2^{j} is used in place of 2^{j(d−1)}. The collection of functions {ψ_{I}^{e}}_{I∈D,e∈E} (when renormalized so that (1.6) holds with | · |_{BV} replaced by the L_{2} norm) forms a Riesz basis for L_{2}(ℝ^{d}) and (a correspondingly renormalized version of) {ψ̃_{I}^{e}}_{I∈D,e∈E} is its dual basis. The orthogonal wavelet bases given above are special cases. Even in the orthogonal case we shall keep the notation ψ̃_{I}^{e} to mark the difference in normalization.

Given a tempered distribution f on ℝ^{d}, we define its wavelet coefficients by

f_{I}^{e} := ⟨f, ψ̃_{I}^{e}⟩  (1.9)

whenever this inner product is defined ( for example, if ψ̃_{I}^{e} is in C^{r} this will be the case for all tempered distributions of order < r). The wavelet decomposition of f is then formally defined as

f = ∑_{e∈E} ∑_{I∈D} f_{I}^{e}ψ_{I}^{e}, .  (1.10)

We can simplify notation by introducing the vectors ψ_{I} = (ψ_{I}^{e})_{e∈E} and f_{I} = (f_{I}^{e})_{e∈E}^{T} so that we have

f = ∑_{I∈D} f_{I}ψ_{I}.  (1.11)

We shall also consider the “non-homogeneous version” of this wavelet basis, which is obtained by taking only the scales j ≥ 0 and by including the index e = (0, ⋯, 0) when j = 0, i.e., a coarse “layer” of scaling functions. Denoting by D_{+} := ∪_{j≥0}D_{j} the set of dyadic cubes with scale j ≥ 0, we write this decomposition as

f = ∑_{I∈D_{+}} F_{I}Ψ_{I},  (1.12)

where the F_{I} and Ψ_{I} coincide with f_{I} and ψ_{I} if I ∈ D_{j}, j > 0, while we incorporate the index e = (0, ⋯, 0) when j = 0. Regardless of which wavelet basis we choose, the subscript I represents the spatial localization of the wavelets ψ_{I} and ψ̃_{I} (I is contained in their support), and its volume |I| = 2^{−jd} indicates their scale (the size of their support is proportional with |I|, with a proportionality constant independent of the scale). Note that for the Haar system, i.e., when φ = φ̃ = χ_{]0,1[} and ψ = ψ̃ = χ_{]0,1/2[} − χ_{]1/2,1[}, the supports of ψ_{I} and ψ̃_{I} coincide exactly with I.

We can now formulate the following result which was first proved in the case of the Haar system [4] and later extended to more general compactly supported wavelets [5]. In this theorem, and later, we use | · | to denote the Euclidean norm in ℝ^{l}. A pivotal role is played by the space wℓ^{1}(D) (weak ℓ_{1}). It consists of those sequences (a_{I})_{I∈D} for which

∥(a_{I})∥_{wℓ^{1}} := sup_{ϵ>0} [ϵ #{I ∈ D : |a_{I}| > ϵ}]  (1.13)

is finite.

Theorem 1.1 For all f ∈ BV(ℝ^{d}), the coefficient sequence (f_{I})_{I∈D} belongs to the space wℓ^{1}(D). More precisely, there exists a constant C > 0 such that for all f ∈ BV(ℝ^{d}) and ϵ > 0

#{I ∈ D : |f_{I}| > ϵ} ≤ C|f|_{BV(ℝ^{d})}ϵ^{−1}.  (1.14)

Similarly, for the non-homogeneous basis indexed by D_{+}, we have

#{I ∈ D_{+} : |F_{I}| > ϵ} ≤ C∥f∥_{BV(ℝ^{d})}ϵ^{−1}.  (1.15)

On the other hand, from the BV normalization of the wavelets (see (1.6)), we see that whenever (F_{I})_{I∈D_{+}} ∈ ℓ_{1}(D_{+}) then f := ∑_{I∈D_{+}} F_{I}Ψ_{I} belongs to BV and satisfies

∥f∥_{BV(ℝ^{d})} ≤ C∥(F_{I})∥_{ℓ_{1}(D_{+})}.  (1.16)

Therefore, we have almost characterized BV(ℝ^{d}) in the following sense. Let bv(D_{+}) denote the discrete space of wavelet coefficient sequences of BV functions with

∥(F_{I})_{I∈D_{+}}∥_{bv} := ∥f∥_{BV(ℝ^{d})}.  (1.17)

Then, we have the continuous embeddings

ℓ_{1}(D_{+}) ⊂ bv(D_{+}) ⊂ wℓ_{1}(D_{+}).  (1.18)

This result is sufficient to ensure the optimality of estimation and compression algorithms in the sense of [11] (see [4]).

Theorem 1.1 also gives a direct easy access to some fine analysis results, such as the following improved Poincaré inequality in dimension d = 2:

∥f∥_{L_{2}(ℝ^{2})}^{2} ≤ C∥f∥_{B_{∞}^{−1}(L_{∞}(ℝ^{2}))}∥f∥_{BV(ℝ^{2})},  (1.19)

where B_{∞}^{−1}(L_{∞}(ℝ^{2})) is the Besov space. The classical Poincaré inequality in this case would involve the L_{∞} norm instead of the Besov norm on the right side of (1.19). The importance of (1.19) is that it scales correctly for both dilation and modulation (i.e. multiplication by a character e^{iω·x}) whereas the original Poincaré inequality scales correctly only for dilation. In this sense, one could say that (1.19) is the “correct” Poincaré inequality.

With Theorem 1.1 in hand, inequality (1.19) can be derived from two facts indicating a pattern of argument that will be encountered later again. First one observes the inequality

∥(F_{I})∥_{ℓ_{2}}^{2} ≤ ∥(F_{I})∥_{ℓ_{∞}}∥(F_{I})∥_{wℓ_{1}}.  (1.20)

The second ingredient is that the L_{2} and B_{∞}^{−1}(L_{∞}(ℝ^{2})) norms of a function f are respectively equivalent to the ℓ_{2} and ℓ_{∞} norm of the sequence (F_{I})_{I∈D_{+}}. These are special cases of norm equivalences that will be described later in more detail. The proof of (1.19) also uses that for d = 2 the BV- and L_{2}-normalizations of the wavelets coincide. Note that there exists no other proof of (1.19) up to now.

The inequalities (1.19) and (1.20) can be viewed as special cases of interpolation using the real method of Lions-Peetre (see e.g. [1] for an introduction). Given a pair of linear spaces (X, Y) continuously embedded in some Hausdorff space X, the K-functional for this pair is given by

K(f, t; X, Y) := inf_{g∈Y,f−g∈X} ∥f − g∥_{X} + t∥g∥_{Y} , t > 0,  (1.21)

where ∥ · ∥_{X} and ∥ · ∥_{Y} are quasi-semi-norms for these spaces. For each 0 < θ < 1, 0 < q ≤ ∞, the intermediate space (X, Y)_{θ,q} consists of all elements of X + Y for which

∥f∥_{(X,Y)_{θ,q}} := (∫_{0}^{∞}[t^{−θ}K(f, t)]^{q} \frac{dt}{t})^{1/q}, 0 < q < ∞,  (1.22)

is finite (with the usual change to a sup when q = ∞). The space (X, Y)_{θ,q} is called an interpolation space for this pair. It is an important question in analysis to characterize the interpolation spaces for a given pair (X, Y). Such characterizations are known for many (but not all) pairs of classical spaces.

In particular, the intermediate spaces for any pair (ℓ_{p}, ℓ_{q}) of sequence spaces are known to be Lorentz spaces. Also, the same conclusion holds if the spaces ℓ_{p} and ℓ_{q} are replaced by their weak counterparts. As a special case, the “framing” of bv between ℓ_{1} and wℓ_{1} gives

ℓ_{2} = (ℓ_{∞}, ℓ_{1})_{1/2,2} ⊂ (ℓ_{∞}, bv)_{1/2,2} ⊂ (ℓ_{∞}, wℓ_{1})_{1/2,2} = ℓ_{2}.  (1.23)

From this and the characterization of L_{2} and the Besov space by wavelet coefficients, we derive

L_{2} = (B_{∞,∞}^{−1}, BV)_{1/2,2}.  (1.24)

This method of determining interpolation spaces for a pair of smoothness spaces by identifying them with sequence spaces, via a boundedly invertible linear mapping, is called the method of retracts. In the case of (1.24), this result (given in [4]) was new.

Given any pair (X, Y), one always has the interpolation inequality

∥f||_{(X,Y)_{θ,q}} ≤ ∥f∥_{X}^{1−θ}∥f∥_{Y}^{θ}  (1.25)

(see [1], p. 49). Thus, given (1.24), (1.19) and (1.20) in turn follow from this general principle (although (1.20) can be proved directly in a simple way as well).

Despite the above success, Theorem 1.1 is not sufficient to answer other fine questions in analysis. In fact, the present paper was motivated by questions raised by Yves Meyer concerning the correct form of Gagliardo-Nirenberg-type inequalities. Improving these inequalities in a similar way to (1.19) is equivalent to establishing new results on interpolation between BV and other Sobolev and Besov spaces. The difficulty in accomplishing this is that general Sobolev and Besov spaces are described by applying weighted ℓ_{p}(w) norms to wavelet coefficient sequences. The weights w take the form |I|^{s} where we denote as before by |I| := vol(I) the volume of I. Theorem 1.1 is no longer tailored to this context, since the interpolation spaces between such a weighted ℓ_{p} space and wℓ_{1} no longer yields the desired sequence space. Fortunately, there is a possible way around this which was first utilized in [10]. The key is to incorporate weights both in renormalizing the coefficients and in the weak ℓ_{1} space. To describe this, we introduce the following sequence spaces.

Definition 1.2 Let γ ∈ ℝ. For 0 < p < ∞, the space ℓ_{p}^{γ}(D) consists of those sequences (c_{I})_{I∈D} such that (|I|^{−γ}c_{I})_{I∈D} ∈ ℓ_{p}(D, |I|^{γ}), i.e.,

∥(c_{I})_{I∈D}∥_{ℓ_{p}^{γ}(D)}^{p} := (∑_{I∈D} |I|^{(1−p)γ}|c_{I}|^{p})^{1/p} < ∞.  (1.26)

The space wℓ_{p}^{γ}(D) consists of those sequences (c_{I})_{I∈D} such that (|I|^{−γ}c_{I})_{I∈D} ∈ wℓ_{p}(D, |I|^{γ}), i.e.,

∥(c_{I})∥_{wℓ_{p}^{γ}(D)} := sup_{ϵ>0} ϵ^{p} ∑_{|c_{I}|>ϵ|I|^{γ}} |I|^{γ} < ∞.  (1.27)

For p = ∞, the space ℓ_{∞}^{γ}(D) consists of those sequences (c_{I})_{I∈D} such that (|I|^{−γ}c_{I})_{I∈D} ∈ ℓ_{∞}(D), i.e. |c_{I}| ≤ C|I|^{γ}. The spaces ℓ_{p}^{γ}(D_{+}) and wℓ_{p}^{γ}(D_{+}) are defined analogously.

Note that when γ = 0 this corresponds to the classical ℓ_{p} and wℓ_{p} spaces. Note also that ℓ_{1}^{γ} coincides with ℓ_{1} for all γ, while wℓ_{1}^{γ} differs from wℓ_{1}. In fact there is no natural ordering of the spaces wℓ_{1}^{γ} as γ varies.

Introducing the spaces wℓ_{p}^{γ} helps us answer some questions concerning interpolation of smoothness spaces. In the present context of BV, it is easy to reduce the questions of Meyer to the following:

For which values of γ do we have the embedding of bv into wℓ_{1}^{γ}(D) or equivalently the weak-type estimate

∑_{|f_{I}|>ϵ|I|^{γ}} |I|^{γ} ≤ C|f|_{BV(ℝ^{d})}ϵ^{−1}?  (1.28)

The main result of this paper is to give a precise answer to this question in the following theorem.

Theorem 1.3 Inequality (1.28) holds if and only if γ > 1 or γ < 1 − 1/d. The same conclusion holds if in (1.28) we replace (f_{I})_{I∈D} by (F_{I})_{I∈D_{+}} and |f|_{BV(ℝ^{d})} by ∥f∥_{BV(ℝ^{d})}.

Although Theorem 1.3 includes Theorem 1.1 as a particular case (γ = 0), the spirit of our proof is quite different from [4].

The proof of Theorem 1.3 is given in the following sections. We use the remainder of the present section to formulate and prove applications of Theorem 1.3 to interpolation and Gagliardo-Nirenberg-type inequalities. We first discuss interpolation between BV and the classical Besov-Sobolev spaces.

The Besov spaces B_{p}^{s}(L_{p}(ℝ^{d})) are typically defined using Littlewood-Paley decompositions or moduli of smoothness. However, they have an equivalent formulation in terms of wavelet decompositions (see [13] or [2]) that we shall use here for their definition. Let the univariate scaling function φ and its associated wavelet ψ be in C^{r} and similarly let φ̃ and ψ̃ be in Cr̃. Then, for each −r̃ < s < r, we define the Besov space B_{p}^{s}(L_{p}(ℝ^{d})), 1 < p ≤ ∞, as the set of all tempered distributions f such that

∥f∥_{B_{p}^{s}(L_{p}(ℝ^{d}))} := ∥(|F_{I}|)∥_{ℓ_{p}^{γ}(D_{+})}, γ := 1 + (s − 1)p^{∗}/d  (1.29)

is finite, where p^{∗} denotes the conjugate index to p.

This definition is in agreement with the characterization of Besov spaces by wavelet decomposition but it looks a little strange because we have used the ℓ_{p}^{γ} norms. The usual definition uses the L_{p} normalized wavelets Ψ_{I,p} = |I|^{\frac{1}{p^{∗}} − \frac{1}{d}} Ψ_{I} and their corresponding coefficients F_{I,p}. Then it takes the form

∥f∥_{B_{p}^{s}(L_{p}(ℝ^{d}))} = ∥(|I|^{−s/d}|F_{I,p}|)∥_{ℓ_{p}(D_{+})}  (1.30)

which is identical with (1.29) because F_{I,p} = |I|^{\frac{1}{d} − \frac{1}{p^{∗}}} F_{I}.

There is a similar wavelet description of the homogeneous Besov spaces Ḃ_{p}^{s}(L_{p}(ℝ^{d})) which were originally defined using Littlewood-Paley decompositions (see [13]). One can define the space B_{p}^{s}(L_{p}(ℝ^{d})) as the set of all tempered distributions f such that

∥f∥_{Ḃ_{p}^{s}(L_{p}(ℝ^{d}))} := ∥(|f_{I}|)∥_{ℓ_{p}^{γ}(D)}, γ := 1 + (s − 1)p^{∗}/d  (1.31)

is finite.

We shall use the well known fact that for any γ ∈ ℝ and 1 < p ≤ ∞, we have (see e.g. Theorem 5.3.1, p.113 in [1])

ℓ_{q}^{γ} = (ℓ_{p}^{γ}, ℓ_{1}^{γ})_{θ,q} = (ℓ_{p}^{γ}, wℓ_{1}^{γ})_{θ,q},  (1.32)

whenever 0 < θ < 1 and

\frac{1}{q} = \frac{1 − θ}{p} + θ.  (1.33)

We should note that γ is the same for all the spaces in (1.32). Since the appropriate value of γ is fixed by the Besov space that we wish to pair with BV, we have no flexibility in its choice and therefore cannot just simply apply Theorem 1.1 which corresponds to γ = 0.

Clearly from (1.32) and (1.25) it follows that we

∥(a_{I})∥_{ℓ_{q}^{γ}} ≤ C∥(a_{I})∥_{ℓ_{p}^{γ}}^{1−θ}∥(a_{I})∥_{wℓ_{1}^{γ}}^{θ}.  (1.34)

Theorem 1.4 Assume that γ > 1 or γ < 1−1/d, and let (s, p) satisfy (s−1)p^{∗}/d = γ −1 for some 1 < p ≤ ∞. Then, for any 0 < θ < 1, we have

(B_{p}^{s}(L_{p}(ℝ^{d})), BV(ℝ^{d}))_{θ,q} = B_{q}^{t}(L_{q}(ℝ^{d}))  (1.35)

with equivalent norms and with

\frac{1}{q} = \frac{1 − θ}{p} + θ, t = (1 − θ)s + θ.  (1.36)

Similarly, we have

(Ḃ_{p}^{s}(L_{p}(ℝ^{d})), ḂV(ℝ^{d}))_{θ,q} = Ḃ_{q}^{t}(L_{q}(ℝ^{d}))  (1.37)

with the same restrictions on p, q, t. Here ḂV means that in the definition of the Kfunctional (1.21) we use the seminorm | · |_{BV} rather than ∥ · ∥_{BV}.

Proof: Consider the wavelet transform which linearly maps f into (F_{I})_{I∈D_{+}}. In view of (1.29), it is an isometry between B_{p}^{s}(L_{p}(ℝ^{d})) and ℓ_{p}^{γ}(D_{+}). We also know from (1.18) that the image bv(D_{+}) of BV(ℝ^{d}) is framed by ℓ_{1}^{γ}(D_{+}) and wℓ_{1}^{γ}(D_{+}) . Hence, using (1.32), we deduce that a distribution f is in (B_{p}^{s}(L_{p}(ℝ^{d})), BV(ℝ^{d}))_{θ,q} if and only if (F_{I})_{I∈D_{+}} ∈ ℓ_{q}^{γ}(D_{+}) with equivalent norms. Now observe that for q and t as in (1.36) one has (s − 1)p^{∗} = (t − 1)q^{∗}. Thus one also has γ = 1 + (t − 1)q^{∗}/d and invoking the definition of Besov spaces (1.29), the proof is completed. In the homogeneous case, we use the mapping of f into (f_{I})_{I∈D} to arrive at (1.37). □

Combining Theorem 1.4 with (1.25) we immediately obtain the following Gagliardo-Nirenberg-type inequalities.

Theorem 1.5 Under the same assumptions and using the same notation as in Theorem 1.4 we have

∥f∥_{B_{q}^{t}(L_{q}(ℝ^{d}))} ≤ C∥f∥_{B_{p}^{s}(L_{p}(ℝ^{d}))}^{1−θ}∥f∥_{BV(ℝ^{d})}^{θ}.  (1.38)

and

∥f∥_{Ḃ_{q}^{t}(L_{q}(ℝ^{d}))} ≤ C∥f∥_{Ḃ_{p}^{s}(L_{p}(ℝ^{d}))}^{1−θ}|f|_{BV(ℝ^{d})}^{θ}.  (1.39)

In particular, for the Sobolev space H^{s}(ℝ^{d}) = W^{s}(L_{2}(ℝ^{d})), we have

∥f∥_{H^{s}(ℝ^{d})}^{2} ≤ C∥f∥_{B_{∞}^{2s−1}(L_{∞}(ℝ^{d}))}∥f∥_{BV(ℝ^{d})},  (1.40)

provided s < 1/2 or s > 1. For s = 0, this establishes (1.19) in any dimension.

The remainder of this paper will be devoted to the proof of Theorem 1.3. We begin in Section 2 by gathering some known results about functions in BV. In Section 3 we prove a main technical result for the case γ < 0 or γ > 1. The case 0 ≤ γ < 1 − \frac{1}{d} is handled in Section 4. Section 5 links this technical result with wavelet expansions and completes the proof of Theorem 1.3. We conclude this section with indicating some implications concerning restricted nonlinear approximation. Finally, Section 6 illustrates that the restriction on γ is sharp by providing counter-examples for 1 − \frac{1}{d} ≤ γ ≤ 1.

In all our arguments, and unless stated otherwise, C denotes a generic constant, the value of which may vary even within the same proof.

2 Some properties of BV functions

For a detailed treatment of BV functions including the proofs of the following fundamental results, we refer the reader to [14] or [12].

Although we shall not use it in the sequel, we first recall the alternate (and equivalent) definition of BV by finite differences: if Ω is an open set of ℝ^{d}, f ∈ L_{1}(Ω) has bounded variation if and only if the quantity

sup_{|h|≤1} \frac{∥f − f(· + h)∥_{L_{1}(Ω_{h})}}{|h|} ,  (2.1)

is finite where Ω_{h} := {x ∈ Ω : x + th ∈ Ω for t ∈ [0, 1]}. Moreover for a fixed Ω, this quantity is equivalent to the total variation |f|_{BV(Ω)}. We also recall that the space BV(Ω) is (non-compactly) embedded in L_{d^{∗}}(Ω) with d^{∗} = \frac{d}{d−1} and that we have the embedding inequality (see [14], p. 81)

∥f∥_{L_{d^{∗}}(Ω)} ≤ C(Ω)∥f∥_{BV(Ω)}.  (2.2)

We shall use the possibility of approximating the functions of BV(Ω) by smooth functions in the following sense (see e.g. [12], p.172 or [14], p.225).

Theorem 2.1 Let f ∈ BV(Ω). Then there exists a sequence {f_{k}}_{k≥0} in BV(Ω) ∩ C^{∞}(Ω) such that

lim_{k→+∞} ∥f − f_{k}∥_{L_{1}(Ω)} = 0 and lim_{k→+∞} |f_{k}|_{BV(Ω)} = |f|_{BV(Ω)}.  (2.3)

This result will allow us to reduce the proof of our weak-type estimates to smooth functions for which we have |f|_{BV(Ω)} = ∫_{Ω} |∇f|.

Characteristic functions of sets are particular instances of BV functions which will play an important role in our analysis. If E is a bounded open set with smooth boundary, then it is easy to check from the definition that χ_{E} ∈ BV(Ω) and that

|χ_{E}|_{BV(Ω)} = H^{d−1}(∂E ∩ Ω),  (2.4)

where here and later H^{s} denotes the s-dimensional Hausdorff measure. The above equality is not true for more general open sets with finite perimeter but no Lipschitz boundary (take e.g. E := {(x, y) |x| < 1, 0 < |y| < 1}), for which we have only the inequality

|χ_{E}|_{BV(Ω)} ≤ H^{d−1}(∂E ∩ Ω).  (2.5)

The importance of characteristic functions in the description of BV is emphasized by the co-area formula which has the following classical form for sufficiently smooth functions. If f ∈ BV(Ω) ∩ C^{1}(Ω), then one has

∫_{Ω} |∇f| = ∫_{ℝ} H^{d−1}(Ω ∩ f^{−1}({t}))dt,  (2.6)

(see [12], p.112 or [14], p.76 ). To extend this relation to general BV functions one introduces the level sets E_{t} = E_{t}(f) defined by E_{t} = {x ∈ Ω : f(x) ≥ t}. The above formula then takes the following form (see [12], p.185):

Theorem 2.2 For f ∈ BV(Ω) one has

|f|_{BV(Ω)} = ∫_{ℝ} |χ_{E_{t}}|_{BV(Ω)}dt.  (2.7)

Such level sets might not have a C^{1} boundary for almost every t and therefore one cannot substitute H^{d−1}(∂E_{t} ∩ Ω) in place of |χ_{E_{t}}|_{BV}. The co-area formula (2.7) reveals that BV admits an atomic decomposition in terms of characteristic functions since we have

f(x) = lim_{z→−∞} z + ∫_{z}^{+∞}χ_{E_{t}}(x)dt.  (2.8)

Such a decomposition can be particularly useful when proving properties of the type Φ(f) ≤ C|f|_{BV} where Φ is a convex functional, since it reduces the proof to the case where f is a single atom χ_{E}.

We shall also need a version of the isoperimetric inequality which we prove here by applying the embedding of BV into L^{d^{∗}} to characteristic functions.

Theorem 2.3 Let Q be an open cube of ℝ^{d} and let E be a domain with a smooth boundary. Define E_{Q} := E ∩ Q and its complement Ẽ_{Q} := Q \ E_{Q}. Then there exists a constant C independent of E and of Q such that

min{|E_{Q}|, |Ẽ_{Q}|} ≤ C[H^{d−1}(∂E ∩ Q)]^{d^{∗}}.  (2.9)

Proof: Let E_{Q}^{∗} denote the set of minimal measure among E_{Q} and Ẽ_{Q} and define

a_{Q}(f) := |Q|^{−1} ∫_{Q} f,

We clearly have |χ_{E} − a_{Q}(χ_{E})| ≥ 1/2 on E_{Q}^{∗} and therefore

∫_{Q} |χ_{E} − a_{Q}(χ_{E})|^{d^{∗}} ≥ 2^{−d^{∗}} min{|E_{Q}|, |Ẽ_{Q}|}.  (2.10)

In view of the formula (2.4), (2.9) follows as soon as we can estimate the left hand side of (2.10) by |χ_{E}|_{BV(Ω)}^{d^{∗}}. This in turn is a consequence of the following Poincaré inequality for general BV functions

∥f − a_{Q}(f)∥_{L_{d^{∗}}(Q)} ≤ C|f|_{BV(Q)}.  (2.11)

This could be derived directly but we will use here an argument that will be needed later anyway. To this end, note that

∥f −a_{Q}(f)∥_{L_{1}(Q)} = |Q|^{−1} ∫_{Q} | ∫_{Q} (f(x)−f(y))dy|dx ≤ |Q|^{−1} ∫_{Q×Q} |f(x)−f(y)|dxdy, (2.12)

and assume first that f ∈ W^{1}(L_{1}(Ω)). For each x = (x_{1}, ⋯, x_{d}) and y = (y_{1}, ⋯, y_{d}) we can define the segments

S_{i}(x, y) := Q ∩ {(x_{1}, ⋯, x_{i−1}, t, y_{i+1}, ⋯, y_{d}) ; t ∈ ℝ}, i = 1, ⋯, d.

With such a definition, we can connect x and y by a path S(x, y) ⊂ ∪_{i}S_{i}(x, y) so that

|f(x) − f(y)| ≤ ∑_{i=1}^{d} ∫_{S_{i}(x,y)} |\frac{∂f}{∂x_{i}} | .

Integrating with respect to x and y we can estimate the right hand side of (2.12) by

|Q|^{−1} ∑_{i=1}^{d} ∫_{Q×Q} ∫_{S_{i}(x,y)} |\frac{∂f}{∂x_{i}} | dx dy ≤ |Q|^{1/d} ∑_{i=1}^{d} ∫_{Q} |\frac{∂f}{∂x_{i}} | ≤ \sqrt{d}|Q|^{1/d} ∫_{I} |∇f|.

Now (1.3) and Theorem 2.1 imply that for any f ∈ BV(Q)

∥f − a_{Q}(f)∥_{L_{1}(Q)} ≤ |Q|^{−1} ∫_{Q×Q} |f(x) − f(y)|dxdy ≤ \sqrt{d}|Q|^{1/d}|f|_{BV(Q)}.  (2.13)

In particular, for the unit d-cube □ the estimate ∥f − a_{□}(f)∥_{BV(□)} ≤ (1 + \sqrt{d})|f|_{BV(□)} follows. The embedding (2.2) of BV(□) into L_{d^{∗}}(□) yields ∥f −a_{Q}(f)∥_{L_{d^{∗}}(□)} ≤ C(□)∥f − a_{Q}(f)∥_{BV(□)} and thus ∥f − a_{□}(f)∥_{L_{d^{∗}}(□)} ≤ C(□)|f|_{BV(□)}. One easily checks that this latter estimate remains invariant under rescaling which confirms (2.11) and completes the proof.

In the sequel we shall assume Ω = ℝ^{d}, and the space BV will always refer to BV(ℝ^{d}). Let g be a function in L_{∞} supported on ]0, 1[^{d} and such that ∫ g = 0. For I := 2^{−j}(]0, 1[^{d}+k) a dyadic cube in D, we define

g_{I} := 2^{j}g(2^{j} · −k).  (2.14)

For I ∈ D, we introduce four quantities which measure in some sense the oscillation of a function f on I. The first one is the size of the inner product with g_{I}, i.e.

c_{I} := c_{I}(f) := |⟨f, g_{I}⟩|.  (2.15)

The second one is the renormalized error of approximation by constants

r_{I} := r_{I}(f) := |I|^{−1/d}∥f − a_{I}(f)∥_{L_{1}(I)}.  (2.16)

The third one is the renormalized averaged modulus of continuity

w_{I} := w_{I}(f) := |I|^{−1−1/d} ∫_{I×I} |f(x) − f(y)|dx dy.  (2.17)

The above three quantities are well defined whenever f ∈ L_{1}(I). When f ∈ W^{1}(L_{1}(I)), we define the fourth one as the variation of f on I

v_{I} := v_{I}(f) := ∫_{I} |∇f| ;  (2.18)

for general BV functions, we set v_{I}(f) := |f|_{BV(I)}.

Lemma 2.4 We have for all f ∈ L_{1}(I)

c_{I}(f) ≤ ∥g∥_{L_{∞}(ℝ^{d})}r_{I}(f),  (2.19)

and

r_{I}(f) ≤ w_{I}(f).  (2.20)

For all f ∈ BV(I) we have

w_{I}(f) ≤ \sqrt{d}v_{I}(f).  (2.21)

Proof: Observing that g_{I} is orthogonal to constants, we obtain

c_{I}(f) = |⟨f, g_{I}⟩| = |⟨f − a_{I}(f), g_{I}⟩|
≤ ∥f − a_{I}(f)∥_{L_{1}(I)}∥g_{I}∥_{L_{∞}} = ∥g∥_{L_{∞}}|I|^{−1/d}∥f − a_{I}(f)∥_{L_{1}(I)},

which is (2.19). The second inequality (2.20) follows from (2.12). Finally (2.21) immediately follows from (2.13).

This list of inequalities will be used to prove the following result.

Theorem 2.5 Let f ∈ BV(ℝ^{d}). Then (c_{I}(f))_{I∈D} ∈ wℓ_{1}^{γ}(D) for all γ < 1 − 1/d or γ > 1. More precisely, there exists a constant C depending only on γ such that for all f ∈ BV (ℝ^{d}) and ϵ > 0 we have

∑_{I∈D; c_{I}(f)>ϵ|I|^{γ}} |I|^{γ} ≤ C|f|_{BV(ℝ^{d})}ϵ^{−1}.  (2.22)

The proof of this result is the object of the next two sections. This theorem will then be used in §5 to prove Theorem 1.3. For the proof of Theorem 2.5, we shall restrict ourselves to f ∈ BV(ℝ^{d})∩C^{∞}(ℝ^{d}). The result for a general f ∈ BV(ℝ^{d}) is then proved by using the approximation sequence (f_{k})_{k≥0} of Theorem 2.1 and noting that ⟨f_{k}, g_{I}⟩ tends to ⟨f, g_{I}⟩ for all I. If follows that if (2.22) holds for all the f_{k}, then for each finite subset

Λ_{ϵ}^{∗} ⊂ Λ_{ϵ} := {I ∈ D : |⟨f, g_{I}⟩| > ϵ|I|^{γ}},  (2.23)

we have the property

∑_{I∈Λ_{ϵ}^{∗}} |I|^{γ} ≤ C|f_{k}|_{BV(ℝ^{d})}ϵ^{−1},  (2.24)

provided k is sufficiently large. Letting k go to infinity, we conclude that (2.22) also holds for f.

3 The case γ < 0 or γ > 1

We begin with the cases γ < 0 or γ > 1 which have simple proofs. In these cases, it is sufficient to use the estimate c_{I}(f) ≤ Cv_{I}(f) of Lemma 2.4 with C = \sqrt{d}∥g∥_{L^{∞}}.

Theorem 3.1 Assume that γ > 1 or γ < 0. Then f ∈ BV(ℝ^{d}) ∩ C^{∞}(ℝ^{d}) implies that (v_{I}(f)) ∈ wℓ_{1}^{γ}(D). More precisely, there exists C = C(γ) such that for all such f and each ϵ > 0,

∑_{v_{I}(f)>ϵ|I|^{γ}} |I|^{γ} ≤ Cϵ^{−1} ∫_{ℝ^{d}} |∇f|.  (3.1)

Proof: For f ∈ BV(ℝ^{d}) ∩ C^{∞}(ℝ^{d}) and ϵ > 0, we want to estimate ∑_{I∈Λ_{ϵ}} |I|^{γ} where

Λ_{ϵ} := Λ_{ϵ}(f) := {I ∈ D : v_{I}(f) > ϵ|I|^{γ}}.  (3.2)

We first treat the case γ > 1. We define Λ_{ϵ}^{max} as the subset of maximal cubes of Λ_{ϵ}, i.e. those I ∈ Λ_{ϵ} such that for all J ∈ Λ_{ϵ}, I ⊆ J implies I = J.

Since v_{I}(f) ≤ |f|_{BV} and since γ > 0, there exists a constant A > 0 depending of f and ϵ such that for |I| ≥ A, we always have v_{I}(f) ≤ ϵ|I|^{γ}, i.e. I ∉ Λ_{ϵ}. It follows that any cube J ∈ Λ_{ϵ} is always contained in some maximal cube I ∈ Λ_{ϵ}^{max}. Consequently, we have the estimate

∑_{I∈Λ_{ϵ}} |I|^{γ} ≤ ∑_{I∈Λ_{ϵ}^{max}} ∑_{J⊆I} |J|^{γ} = ∑_{I∈Λ_{ϵ}^{max}} ∑_{j≥0} ∑_{J⊆I,|J|=2^{−jd}|I|} |J|^{γ}
= ∑_{I∈Λ_{ϵ}^{max}} |I|^{γ} ∑_{j≥0} 2^{(1−γ)dj} ≤ C ∑_{I∈Λ_{ϵ}^{max}} |I|^{γ} ≤ Cϵ^{−1} ∑_{I∈Λ_{ϵ}^{max}} v_{I}(f).

Since the maximal cubes of Λ_{ϵ}^{max} are necessarily pairwise disjoint we conclude that ∑_{I∈Λ_{ϵ}^{max}} v_{I}(f) ≤ ∫_{ℝ^{d}} |∇f| which proves (3.1).

In the case γ < 0, we define Λ_{ϵ}^{min} as the subset of minimal cubes of Λ_{ϵ}, i.e., those I ∈ Λ_{ϵ} such that for all J ∈ Λ_{ϵ}, J ⊆ I implies I = J. Since v_{I}(f) = ∫_{I} |∇f| ≤ ∥∇f∥_{L_{∞}(J)}|I| for all I ⊆ J, and since γ < 0, for any fixed dyadic cube J there exists a > 0 depending of f and ϵ such that if I ⊂ J and |I| ≤ a, we have v_{I}(f) ≤ ϵ|I|^{γ}, i.e., I ∉ Λ_{ϵ}. It follows that any J ∈ Λ_{ϵ} contains only a finite number of I ∈ Λ_{ϵ}, and in turn always contains a minimal cube I ∈ Λ_{ϵ}^{min}. Using also the fact that each I ∈ Λ_{ϵ}^{min} is contained in at most one dyadic cube J ∈ D_{j} for any j, we have the estimate

∑_{I∈Λ_{ϵ}} |I|^{γ} ≤ ∑_{I∈Λ_{ϵ}^{min}} ∑_{J⊇I} |J|^{γ} = ∑_{I∈Λ_{ϵ}^{min}} |I|^{γ} ∑_{j≥0} 2^{γdj}
≤ C ∑_{I∈Λ_{ϵ}^{min}} |I|^{γ} ≤ Cϵ^{−1} ∑_{I∈Λ_{ϵ}^{min}} v_{I}(f).

We conclude the proof in a similar manner as above, noting that the minimal cubes of Λ_{ϵ}^{min} are necessarily pairwise disjoint.

In view of the remarks at the end of §2, Theorem 3.1 implies Theorem 2.5 in the cases γ < 0 or γ > 1.

4 The case 0 ≤ γ < 1 − 1/d

In this case, the estimate c_{I}(f) ≤ Cv_{I}(f) is not sufficient to prove Theorem 2.5 because the sequence (v_{I}(f)) does not satisfy the weak-type estimate (3.1) when 0 ≤ γ ≤ 1. For instance, take γ = 0 and consider a non trivial smooth function f with compact support in ]0, 1[^{d}; observe that there exists an infinite number of dyadic cubes I containing ]0, 1[^{d} for which we have v_{I}(f) = C > 0.

Instead we shall use the finer estimate c_{I}(f) ≤ Cw_{I}(f), with C = ∥g∥_{L^{∞}}, combined with the following result.

Theorem 4.1 Let γ < 1 − 1/d. Then f ∈ BV(ℝ^{d}) ∩ C^{∞}(ℝ^{d}) implies that (w_{I}(f))_{I∈D} ∈ wℓ_{1}^{γ}. More precisely, there exists a constant C = C(γ) such that for all such f and each ϵ > 0,

∑_{w_{I}(f)>ϵ|I|^{γ}} |I|^{γ} ≤ Cϵ^{−1} ∫_{ℝ^{d}} |∇f|.  (4.1)

The proof of this result will involve some intermediate lemmas. Define the set

Λ_{ϵ} := Λ_{ϵ}(f) := {I ∈ D : w_{I}(f) > ϵ|I|^{γ}}.  (4.2)

Our goal is to show that

ϵ ∑_{I∈Λ_{ϵ}} |I|^{γ} ≤ C|f|_{BV(ℝ^{d})}.  (4.3)

We first fix some α such that γ < α < 1 − 1/d and establish a distinction between two types of cubes in Λ_{ϵ}.

Definition 4.2 We say a cube I ∈ Λ_{ϵ} is good if for each collection P ⊂ Λ_{ϵ} of pairwise disjoint cubes strictly contained in I, we have

∑_{J∈P} |J|^{α} ≤ |I|^{α},

or if I is minimal in Λ_{ϵ}, i.e., there is no J ∈ Λ_{ϵ} strictly contained in I. If I ∈ Λ_{ϵ} is not good we say it is bad. We denote the set of good cubes in Λ_{ϵ} by G and the set of bad cubes by B.

Clearly G and B depend on f, ϵ, γ and α. Our next lemma shows that it is sufficient to prove (4.3) with G in place of Λ_{ϵ}.

Lemma 4.3 We have

∑_{I∈B} |I|^{γ} ≤ C ∑_{I∈G} |I|^{γ},  (4.4)

where the constant C > 0 depends only on α and γ.

Proof: Since w_{J}(f) ≤ C∥∇f∥_{L_{∞}(I)}|J| for all J ⊆ I and since γ < 1, there exists a constant a > 0 such that if J ⊂ I and |J| ≤ a, we always have w_{J}(f) ≤ ϵ|J|^{γ}, i.e., J ∉ Λ_{ϵ}. It follows that any I ∈ Λ_{ϵ} contains only a finite number of J ∈ Λ_{ϵ}.

For I ∈ B, we denote by G(I) the set of all cubes J ⊂ I such that J ∈ G. Clearly this set is also finite. We shall first prove that

|I|^{α} ≤ ∑_{J∈G(I)} |J|^{α}.  (4.5)

¿From the definition of bad cubes, there is a set P(I) ⊂ Λ_{ϵ} of disjoint cubes contained in I such that

|I|^{α} ≤ ∑_{J∈P(I)} |J|^{α} ≤ ∑_{J∈P(I)∩G} |J|^{α} + ∑_{J∈P(I)∩B} |J|^{α} = Σ_{1} + Σ_{2}.

The terms in Σ_{1} are not processed further and become part of the right side of (4.5). The terms in Σ_{2} are processed further. Namely, for each J appearing in ∑_{2} there is a set P(J) ⊂ Λ_{ϵ} such that

|J|^{α} ≤ ∑_{K∈P(J)} |K|^{α} ≤ ∑_{K∈P(J)∩G} |K|^{α} + ∑_{K∈P(J)∩B} |K|^{α}.

Again, the terms in the first sum are not processed further and become part of the right side of (4.5), remarking that P(J) ∩ G is necessarily disjoint from P(I) ∩ G. The terms in the second sum are processed further. Continuing in this way, we arrive at (4.5) in a finite number of steps since G(I) is finite, and since the minimal cubes of Λ_{ϵ} are by definition contained in G.

It follows from (4.5) that if I ∈ B, then

|I|^{γ} ≤ |I|^{γ−α} ∑_{J∈G(I)} |J|^{α} = ∑_{J∈G(I)} |J|^{γ}2^{−δd(I,J)},

where δ := (α − γ)d > 0 and d(I, J) is the number of levels between J and I, i.e.

d(I, J) := \frac{| log(|I|/|J|)|}{d log 2}.  (4.6)

Therefore, the left side of (4.4) does not exceed

∑_{I∈B} ∑_{J∈G(I)} |J|^{γ}2^{−δd(I,J)} ≤ ∑_{J∈G} |J|^{γ} ∑_{I∈B,I⊃J} 2^{−δd(I,J)}.

For J ∈ G and k > 0, there is at most one I ⊃ J with d(I, J) = k, and therefore

∑_{I∈B,I⊃J} 2^{−δd(I,J)} ≤ ∑_{k=1}^{∞} 2^{−kδ} = C.

This proves the lemma.

It follows from Lemma 4.3 that we need to estimate only ∑_{I∈G} |I|^{γ} in order to prove Theorem 4.1. We shall actually prove that the subsequence (w_{I}(f))_{I∈G} satisfies a strong ℓ_{1} property. For this purpose, we introduce the following definition.

Definition 4.4 A subset R ⊂ D is called α-sparse if and only if for all I ∈ R and any set P ⊂ R of disjoint dyadic cubes contained in I, we have

∑_{J∈P} |J|^{α} ≤ |I|^{α}.  (4.7)

Clearly G is an example of an α-sparse set.

With this definition we have the following theorem.

Theorem 4.5 There exists a constant C such that for any α-sparse set R, we have

∑_{I∈R} w_{I}(f) ≤ C|f|_{BV(ℝ^{d})}.  (4.8)

Proof: Since we want to prove a strong ℓ^{1} estimate, we can use the co-area formula to reduce the proof to the case where f is of the type

f = χ_{E},  (4.9)

where E is a set with smooth boundary of finite d − 1-dimensional measure H^{d−1}(∂E). Indeed, assume for a moment that (4.8) holds for such characteristic functions. If f ∈ BV(ℝ^{d}) ∩ C^{∞}(ℝ^{d}), then, for almost every t ∈ ℝ, the level sets E_{t} = {x ∈ Ω : f(x) ≥ t} have a smooth boundary and thus satisfy

∑_{I∈R} w_{I}(χ_{E_{t}}) ≤ C|χ_{E_{t}}|_{BV(ℝ^{d})}.  (4.10)

For all I, (2.8) yields

w_{I}(f) ≤ ∫_{−∞}^{+∞}w_{I}(χ_{E_{t}})dt.  (4.11)

Combining these inequalities with (2.7), we conclude that for all finite subsets Λ ⊂ R we have

∑_{I∈Λ} w_{I}(f) ≤ C|f|_{BV(ℝ^{d})},  (4.12)

and therefore (4.8) also holds for f.

Also note that |E_{t}| < ∞ if t > 0 and |ℝ^{d} \ E_{t}| < ∞ if t < 0 (since f ∈ L^{1}). Thus, it suffices to establish (4.8) for f = χ_{E}, where E is a set such that either |E| < ∞ or |ℝ^{d} \ E| < ∞, which we will assume for the rest of the proof. For I ∈ R, we define by E_{I} := I ∩ E and its complement Ẽ_{I} = I \ E_{I}. ¿From its definition, we see that w_{I} satisfies the estimate

w_{I}(f) ≤ |I|^{−1−1/d}|I| min{|E_{I}|, |Ẽ_{I}|} = |I|^{1−1/d} min{|E_{I}|, |Ẽ_{I}|}/|I|.  (4.13)

Clearly,

∑_{I∈R} w_{I}(f) = ∑_{I∈R^{∗}} w_{I}(f),  (4.14)

where R^{∗} := {I ∈ R : min{|E_{I}|, |Ẽ_{I}|} > 0} is the set of cubes whose interior intersects the boundary ∂E. For each k > 0, denote by R_{k} the set of cubes in R^{∗} such that

2^{−k−1} < min{|E_{I}|, |Ẽ_{I}|}/|I| ≤ 2^{−k}.  (4.15)

The sets R_{k} are pairwise disjoint and R^{∗} = ∪_{k>0}R_{k}. We thus have

∑_{I∈R} w_{I}(f) = ∑_{k>0} ∑_{I∈R_{k}} w_{I}(f).  (4.16)

We denote by R_{k,0} the maximal cubes of R_{k}, i.e., the set of those I ∈ R_{k} such that there exists no J ∈ R_{k} strictly containing I. Note that since |E| < ∞ or |ℝ^{d} \ E| < ∞, there exists A > 0 such that |I| ≥ A implies

min{|E_{I}|, |Ẽ_{I}|}/|I| ≤ min{|E|, |ℝ^{d} \ E|}/|I| ≤ 2^{−k−1},

i.e. I ∉ R_{k}. Therefore, any in R_{k} is contained in some maximal cube of R_{k,0}. If I is in R_{k,0} and J ∈ R_{k} is contained in I, we define the generation of J as the number of different cubes K ≠ I in R_{k} such that J ⊆ K ⊂ I. In particular, all cubes in R_{k,0} have generation 0. We denote by R_{k,j} the collection of cubes in R_{k} of generation j. Note that the cubes in R_{k,j} are pairwise disjoint, and that R_{k} = ∪_{j≥0}R_{k,j}, so that we have

∑_{I∈R} w_{I}(f) = ∑_{k>0} ∑_{j≥0} ∑_{I∈R_{k,j}} w_{I}(f).  (4.17)

For a fixed k > 0, we can write in view of (4.15) and (4.13)

∑_{j≥0} ∑_{I∈R_{k,j}} w_{I}(f) ≤ 2^{−k} ∑_{j≥0} ∑_{I∈R_{k,j}} |I|^{1−1/d}.  (4.18)

We next define η = 1 − 1/d − α > 0 and remark that for j ≥ 0 each J ∈ R_{k,j+1} must have a parent in R_{k,j}. From the definition of α-sparse sets and the fact that the R_{k,j}, j ≥ 0, are sets of disjoint cubes, we infer that

∑_{I∈R_{k,j−1}} |I|^{1−1/d} = ∑_{I∈R_{k,j−1}} |I|^{η}|I|^{α} ≥ ∑_{I∈R_{k,j−1}} |I|^{η} ∑_{J∈R_{k,j},J⊂I} |J|^{α}
= ∑_{I∈R_{k,j−1}} ∑_{J∈R_{k,j},J⊂I}(|I|/|J|)^{η}|J|^{1−1/d} ≥ 2^{dη} ∑_{J∈R_{k,j}} |J|^{1−1/d},

where the first inequality used the definition (4.7) of α-sparse. Therefore, we obtain by induction that

∑_{I∈R_{k,j}} |I|^{1−1/d} ≤ 2^{−dηj} ∑_{I∈R_{k,0}} |I|^{1−1/d},  (4.19)

so that the summation over j, for fixed k, can be bounded by

∑_{j≥0} ∑_{I∈R_{k,j}} w_{I}(f) ≤ C2^{−k} ∑_{I∈R_{k,0}} |I|^{1−1/d}.  (4.20)

Now if I ∈ R_{k,0}, we see from (4.15) that |I| ≤ 2^{k+1} min{|E_{I}|, |Ẽ_{I}|} and therefore

∑_{I∈R_{k,0}} |I|^{1−1/d} ≤ 2^{(k+1)(1−1/d)} ∑_{I∈R_{k,0}} (min{|E_{I}|, |Ẽ_{I}|})^{1−1/d} .  (4.21)

¿From the isoperimetric inequality of Theorem 2.3 we obtain

(min{|E_{I}|, |Ẽ_{I}|})^{1−1/d} ≤ CH^{d−1}(∂E ∩ I).  (4.22)

Since the maximal cubes of R_{k,0} are pairwise disjoint, it follows from (4.21) and (4.22) that

∑_{I∈R_{k,0}} |I|^{1−1/d} ≤ C2^{k(1−1/d)}H^{d−1}(∂E).  (4.23)

Combining this estimate with (4.20) and (4.18), we obtain

∑_{j≥0} ∑_{I∈R_{k,j}} w_{I}(f) ≤ C2^{−k/d}H^{d−1}(∂E).

Summing over k > 0 according to (4.17), we finally arrive at the estimate

∑_{I∈R} w_{I}(f) ≤ CH^{d−1}(∂E) = C|χ_{E}|_{BV(ℝ^{d})},  (4.24)

where the last equality is (2.4). This concludes the proof of the theorem.

We now apply Theorem 4.5 to R = G. Since ℓ_{1} = ℓ_{1}^{γ} ⊂ wℓ_{1}^{γ}, the theorem implies the weak estimate ∑_{I∈G} |I|^{γ} ≤ C|f|_{BV(ℝ^{d})}ϵ^{−1}. From Lemma 4.3 we see that the proof of Theorem 4.1 is now complete. Combined with the results of §3, this also completes the proof of Theorem 2.5.

5 Application to wavelet decompositions

The results of the two previous sections prove Theorem 2.5. We cannot simply replace the coefficients c_{I}(f) by the wavelet coefficients f_{I} in this theorem, because, in contrast to the functions g_{I}, the compactly supported dual wavelets ψ̃_{I} generally have a support strictly larger than I, so that |f_{I}| ≤ Cw_{I}(f) need not be true. In order to circumvent this problem we use a technique proposed by Meyer, already applied in [5].

Theorem 5.1 Let f ∈ BV(ℝ^{d}). Then (f_{I})_{I∈D} ∈ wℓ_{1}^{γ}(D) for all γ < 1 − 1/d or γ > 1. More precisely, there exists a constant C only depending on γ such that for all f ∈ BV(ℝ^{d}) and ϵ > 0 we have

∑_{|f_{I}|>ϵ|I|^{γ}} ≤ C|f|_{BV(ℝ^{d})}ϵ^{−1}.  (5.1)

Proof: We first remark that up to a shift of spatial indices, we can always assume that the generators ψ̃^{e} of the dual wavelets are supported in ]0, p[^{d} where p is a sufficiently large prime integer. We fix any e ∈ E and define g := ψ̃^{e}(p·), which is now supported in ]0, 1[^{d}. For an arbitrary but fixed r ∈ P := {0, 1, ⋯, p − 1}^{d}, we define f̃_{r}(x) := p^{d−1}f(px + r). Theorem 2.5 implies that for γ < 1 − 1/d or γ > 1, we have the weak-type estimate

∑_{c_{I}^{r}(f)>ϵ|I|^{γ}} |I|^{γ} ≤ C|f̃_{r}|_{BV(ℝ^{d})}ϵ^{−1} = C|f|_{BV(ℝ^{d})}ϵ^{−1},  (5.2)

with c_{I}^{r}(f) := |⟨f̃_{r}, g_{I}⟩|. Now for I := 2^{−j}(]0, 1[^{d}+k), we have

⟨f̃_{r}, g_{I}⟩ = 2^{j} ∫_{ℝ^{d}} f̃_{r}(x)g(2^{j}x − k)dx = 2^{j} ∫_{ℝ^{d}} p^{d−1}f(px + r)g(2^{j}x − k)dx

= p^{−1}2^{j} ∫_{ℝ^{d}} f(x)ψ̃^{e}(2^{j}x − l)dx = p^{−1}f_{J}^{e},

where l := 2^{j}r + pk and J = 2^{−j}(]0, 1[^{d}+l).

We next observe that for j ∈ ℕ, the mapping

(k, r) ↦ 2^{j}r + pk  (5.3)

is a bijection from ℤ^{d} × P onto ℤ^{d}, due to the fact that x ↦ 2^{j}x is a bijection from (ℤ/pℤ)^{d} onto itself. In other words, each coefficient f_{I}^{e} appears as one of the c_{I}^{r}(f), r ∈ P. Since the sets P and E are finite, it follows from these observations that

∑_{|f_{I}|>ϵ|I|^{γ},I∈D_{+}} |I|^{γ} ≤ C|f|_{BV(ℝ^{d})}ϵ^{−1}.  (5.4)

We can remove the restriction that I ∈ D_{+} in (5.4) as follows. We apply this estimate to f_{q} := 2^{q(1−1/d)}f(2^{q}·), q ∈ ℕ, and observe that, by a change of variable,

∑_{|(f_{q})Ĩ|>ϵ̃|Ĩ|^{γ},Ĩ∈D_{+}} |Ĩ|^{γ} ≤ C|f_{q}|_{BV(ℝ^{d})}ϵ̃^{−1},

becomes

∑_{|f_{I}|>ϵ|I|^{γ},|I|≤2^{dq}} |I|^{γ} ≤ C|f|_{BV(ℝ^{d})}ϵ^{−1},

where |I| = 2^{qd}|Ĩ| and ϵ̃ = ϵ2^{q(1−d)(1−1/d)}; C is still the same constant, independent of q and ϵ. By letting q go to +∞, we arrive at (5.1).

A similar result can be derived for the non-homogeneous basis associated with the decomposition (1.12).

Theorem 5.2 Let f ∈ BV(ℝ^{d}). Then (F_{I})_{I∈D_{+}} ∈ wℓ_{1}^{γ}(D_{+}) for all γ < 1 − 1/d or γ > 1. More precisely, there exists a constant C depending only on γ such that for all f ∈ BV(ℝ^{d}) and ϵ > 0 we have

∑_{|F_{I}|>ϵ|I|^{γ}} |I|^{γ} ≤ C∥f∥_{BV(ℝ^{d})}ϵ^{−1}.  (5.5)

Proof: By Theorem 5.1, we already have the weak type estimate

∑_{|F_{I}|>ϵ|I|^{γ},|I|<1} |I|^{γ} ≤ C∥f∥_{BV} ϵ^{−1},  (5.6)

since F_{I} = f_{I} if |I| < 1. For |I| = 1, we have a strong estimate

∑_{I∈D_{0}} |F_{I}| ≤ C ∑_{I∈D_{0}} ∫_{supp(ψ̃_{I})} |f| ≤ CA^{d}∥f∥_{L_{1}(ℝ^{d})},  (5.7)

where A is such that supp(ψ̃^{e}) ⊂ [0, A]^{d} for all e ∈ E′. Combining these estimates, we obtain (5.5).

The above results can easily be adapted to most constructions of wavelets defined on simple bounded domains such as a cube (see e.g. [2] or [6] for examples of such constructions).

Let us finally mention that the weak type estimates of Theorem 5.1 and Theorem 5.2 have equivalent formulations in terms of the approximation performance of thresholding procedures studied in [3]. For 0 < r ≤ ∞, consider the L_{r}-thresholding operator T_{ϵ}^{r} defined by

T_{ϵ}^{r}f := ∑_{∥f_{I}ψ_{I}∥_{Lr} >ϵ} f_{I}ψ_{I}  (5.8)

The results of [3] show that for 0 < p < ∞, the rate of decay of ∥f − T_{ϵ}^{r}f∥_{H_{p}}, as ϵ goes to zero, is determined by weighted weak-type estimates on the renormalized coefficient sequence (∥f_{I}ψ_{I}∥_{L_{r}})_{I∈D}. Here H_{p} denotes the Hardy space which coincides with L_{p} when p > 1. More precisely, we have by Theorem 7.1 of [3] that for μ < p,

∥f − T_{ϵ}^{r}f∥_{H_{p}} < C^{μ/p}ϵ^{1−μ/p},  (5.9)

if and only if the sequence (∥f_{I}ψ_{I}∥_{L_{r}})_{I∈D} belongs to the space wℓ_{μ}(D, |I|^{γ}) with γ := 1 − p/r; the smallest C satisfying (5.9) is then equivalent to ∥(∥f_{I}ψ_{I}∥_{L_{r}})_{I∈D}∥_{wℓ_{μ}(D,|I|^{γ})}. Note that when p = r, i.e. when we use the same metric for thresholding as for measuring the approximation error, we find the standard wℓ_{μ} spaces. However, there are situations in which one prefers to use different metrics for thresholding and measuring the approximation error, such as in statistical estimation, where one may be interested in estimating a noisy function in some arbitrary L_{p} norm, but where the structure of the white noise imposes the L_{2} metric for thresholding. For this particular situation, the case γ < 1−1/d in Theorem 5.1, combined with (5.9) implies the following result:

Theorem 5.3 Let f ∈ BV(ℝ^{d}). Then for 0 < r < ∞ and p = 1 + r/d, we have the thresholding estimate

∥f − T_{ϵ}^{r}f∥_{L_{p}} ≤ C|f|_{BV (ℝ^{d})}ϵ^{1−1/p}.  (5.10)

6 Counter-examples

The purpose of this last section is to prove that Theorem 5.1 and Theorem 5.2 are no longer true for the range 1−1/d ≤ γ ≤ 1. We shall exhibit counter-examples in the case where the wavelets are given by the Haar system, i.e. φ = φ̃ := χ_{]0,1[} and ψ = ψ̃ := χ_{]0,1/2[} −χ_{]1/2,1[}. We first consider the one-dimensional setting, corresponding to the range 0 ≤ γ ≤ 1. If I is a dyadic interval, then the BV-normalized wavelet coefficient f_{I} of a function f is given by

f_{I} = ⟨f, ψ̃_{I}⟩ = \frac{1}{2}(a_{I_{l}}(f) − a_{I_{r}}(f)),  (6.1)

where a_{I_{l}}(f) and a_{I_{r}}(f) are respectively the averages of f on I_{l} and I_{r}, the left and right half-intervals of I. The counter examples that we shall build are functions supported on ]0, 1[ and we shall consider their wavelet coefficients only for |I| ≤ 1. We shall treat separately the cases γ = 0, γ = 1 and 0 < γ < 1.

In the case γ = 1, we consider the function

f(x) = xχ_{]0,1[}(x),

which is clearly in BV(ℝ). If I ⊂]0, 1[, a straightforward computation shows that

f_{I} = −|I|/4.

Therefore, taking ϵ = 1/5, we obtain that

∑_{|f_{I}|>ϵ|I|} |I| ≥ ∑_{I⊂]0,1[} |I| = +∞,

which shows that the weak estimate does not hold when γ = 1.

In the case γ = 0 we consider the function

f = χ_{[0,1/3]},

which is clearly in BV(ℝ). For each j ≥ 0, there exist one dyadic interval I_{j} containing the jump point 1/3 and such that |I_{j}| = 2^{−j}. This jump point is always located at either the 1/3 or 2/3 position of I_{j}, since 1/3 = ∑_{j=1}^{∞} 2^{−2j}. It follows that

f_{I_{j}} = 1/3,

for all j ≥ 0. Therefore taking ϵ = 1/4, we obtain that

#{I : |f_{I}| > ϵ} = ∞,

which shows that the weak estimate does not hold when γ = 0.

We now consider the case 0 < γ < 1. Here, we set α := 1/γ > 1 and we define the sequence (j_{k})_{k≥0} of integers by

2^{−j_{k}−1} < 2^{−αk} ≤ 2^{−j_{k}}.  (6.2)

Note that j_{0} = 0 and that the sequence j_{k} is strictly increasing because α > 1. More precisely, we can write

j_{k+1} = j_{k} + m_{k},

with m_{k} > 0 for all k and m_{k} > 1 for infinitely many k.

We now construct a family of piecewise constant functions (f_{n})_{n>0} as follows. For each n > 0, the distributional derivative of f_{n} is a sum of Dirac masses:

f′_{n} = 2^{−n}[∑_{m=0}^{2^{n}−1} δ_{x_{m}^{n}}] − δ_{1},

where the 2^{n} jump points x_{m}^{n} ∈]0, 1[ will be specified in a moment. Since we subtract δ_{1}, these functions are supported on [0, 1]. Clearly |f_{n}|_{BV(ℝ)} = 2 and ∥f_{n}∥_{BV(ℝ)} ≤ 3, independently of n.

If I is a dyadic interval, the wavelet coefficient c_{I} of f_{n} is given by

c_{I} := ⟨f′_{n}, h_{I}⟩ = 2^{−n} ∑_{m s.t. x_{m}^{n}∈I} h_{I}(x_{m}^{n}),  (6.3)

where h_{I} is the primitive function of ψ̃_{I}, i.e., the hat function h(x) = (1 − |x|)_{+} rescaled to I.

We have not yet specified where to position the points x_{m}^{n} in ]0, 1[. We wish to place them so that the right sum in (6.3) is large for many choices of I. For each k = 0, ⋯, n, we shall inductively construct 2^{k} pairwise disjoint dyadic intervals I_{k,l}, l = 0, ⋯, 2^{k} − 1 of size |I_{k,l}| = 2^{−j_{k}}, and position the points x_{m}^{n} so that

S_{k,l} := {x_{m}^{n}}_{m=2^{n−k}l}^{2^{n−k}(l+1)−1} ⊂ I_{k,l}.  (6.4)

We start the construction with I_{0,0} =]0, 1[, and for k = 1, ⋯, n − 1 the construction is continued using the following iteration: for a given I_{k,l}, we define I_{k+1,2l} and I_{k+1,2l+1} as the two adjacent dyadic intervals of size 2^{−j_{k+1}} which respectively admit the center of I_{k,l} as their right and left endpoints. Iterating this construction, it suffices to choose each point x_{m}^{n} in the corresponding interval I_{n,m}. In the case where m_{k} > 1, we thus notice that all the points in S_{k,l} are concentrated in a central region of I_{k,l} on which h_{I_{k,l}}(x) ≥ 1/2, so that according to (6.3) and (6.2) we then have

c_{I_{k,l}} ≥ 2^{−n−1}#(S_{k,l}) = 2^{−k−1} ≥ 2^{−1−γ}|I_{k,l}|^{γ}.

Therefore, if we fix ϵ = 1/4 < 2^{−1−γ}, we see that for k < n such that m_{k} > 1, we have

∑_{c_{I}≥ϵ|I|^{γ},|I|=2^{−j_{k}}} |I|^{γ} = 2^{k}2^{−γj_{k}} ≥ 1,

and thus

∑_{c_{I}≥ϵ|I|^{γ}} |I|^{γ} ≥ #{k s.t. k < n and m_{k} > 1} = K(n).

Since lim_{n→+∞} K(n) = +∞, this shows that the weak estimate does not hold for 0 < γ < 1.

We shall now generalize the above counterexamples to the multidimensional case for 1 − 1/d ≤ γ ≤ 1 by using the following observations. If f is a one-dimensional BV(ℝ) function supported in [0, 1], then the multidimensional function

F (x_{1}, ⋯, x_{d}) := f(x_{1})χ_{[0,1]^{d}}(x_{1}, …, x_{d})

is in BV (ℝ^{d}) with ∥F ∥_{BV(ℝ^{d})} ≤ C(d)∥f∥_{BV(ℝ)}. Moreover if

I = I_{1} × ⋯ × I_{d}

is a dyadic cube contained in ]0, 1[^{d}, and if e = (1, 0, ⋯, 0), we have

ψ̃_{I}^{e}(x_{1}, ⋯, x_{d}) = ψ̃_{I_{1}}(x_{1})χ_{I_{2}×···×I_{d}}(x_{2}, ⋯, x_{d}).

and therefore the wavelet coefficients c_{I}^{e}(F) of F satisfy

c_{I}^{e}(F) = ⟨F, ψ̃_{I}^{e}⟩ = |I|^{1−1/d}⟨f, ψ̃_{I_{1}}⟩ = |I|^{1−1/d}c_{I_{1}}(f).

It follows that

∑_{|c_{I}^{e}(F)|≥ϵ|I|^{γ}} |I|^{γ} = ∑_{I_{1} such that |c_{I_{1}}(f)| ≥ ϵ|I|^{γ+1/d−1}}  ∑_{(I_{2}, ⋯, I_{d}) such that I = I_{1} × ⋯ × I_{d}} |I|^{γ}

= ∑_{I_{1} s.t. |c_{I_{1}}(f)|≥ϵ|I_{1}|γ̃} |I_{1}|γ̃,

with γ = 1 − 1/d + γ̃/d. Applying these observations to the above one-dimensional counter-examples for 0 ≤ γ̃ ≤ 1, we thus obtain our multidimensional counter-examples for 1 − 1/d ≤ γ ≤ 1.

Acknowledgments: Large parts of the work for this paper were done during visits of various subsets of the authors to the Laboratoire d’Analyse Numérique at the Université Pierre et Marie Curie and to the Industrial Mathematics Institute at the University of South Carolina. We are grateful to these institutions for their hospitality and support. In addition, I.D. would also like to thank the Institute for Advanced Study in Princeton, where she spent a sabbatical semester while working on this project.

References

[1] Bergh, J. and J. Löfström, Interpolation spaces, Springer Verlag, 1976.

[2] Cohen, A., Wavelet methods in numerical analysis, in the Handbook of Numerical Analysis, vol. VII, P.-G. Ciarlet et J.-L. Lions eds., Elsevier, Amsterdam, 2000.

[3] Cohen, A., R. DeVore and R. Hochmuth, Restricted Nonlinear Approximation, Constructive Approximation 16, 85-113, 2000.

[4] Cohen, A., R. DeVore, P. Petrushev and H. Xu, Non linear approximation and the space BV (ℝ^{2}), Amer. J. Math. 121, 587-628, 1999.

[5] Cohen, A., Y. Meyer and F. Oru, Improved Sobolev inequalities, proceedings séminaires X-EDP, Ecole Polytechnique, Palaiseau, 1998.

[6] Dahmen, W., Wavelet and multiscale methods for operator equations, Acta Numerica 6, Cambridge University Press, 1997, 55–228.

[7] Daubechies, I., Ten Lectures on Wavelets, SIAM, 1992.

[8] Donoho, D., M. Vetterli, M., R. DeVore, and I. Daubechies, Harmonic analysis and signal processing, IEEE Trans. Inf. Theory 44 (1998), 2435–2476.

[9] DeVore, R., Nonlinear Approximation, Acta Numerica 7, Cambridge University Press, 1998, 51–150.

[10] DeVore, R. and G. Petrova The averaging lemma, Jour. Amer. Math. Soc., to appear.

[11] Donoho, D., Unconditional bases are optimal for data compression and statistical estimation, Appl. Comp. Harm. Anal. 1(1993), 100–105.

[12] Evans, L. and R. Gariepy, Measure theory and fine properties of functions, CRC Press, New York, 1992.

[13] Meyer, Y., Ondelettes et Opérateurs, Hermann, Paris, 1990.

[14] Ziemer, W., Weakly differentiable functions, Springer Verlag, New York, 1989.

Albert Cohen Laboratoire d’Analyse Numérique Université Pierre et Marie Curie 4 Place Jussieu, 75252 Paris cedex 05 France

e–mail: cohen@ann.jussieu.fr
WWW: http://www.ann.jussieu.fr/∼cohen/

Tel: 33-1-44277195, Fax: 33-1-44277200 Wolfgang Dahmen Institut für Geometrie und Praktische Mathematik RWTH Aachen Templergraben 55 52056 Aachen Germany

e–mail: dahmen@igpm.rwth-aachen.de
WWW: http://www.igpm.rwth-aachen.de/∼dahmen/

Tel: 49-241-803950, Fax: 49-241-8888-317

Ingrid Daubechies Department of Mathematics and Program in Applied and Computational Mathematics Princeton University Fine Hall, Washington Road Princeton, NJ 08544-1000 U.S.A.

e–mail: ingrid@math.princeton.edu
WWW: http://www.math.princeton.edu/∼icd/

Tel.: 609-258-2262, Fax: 609-258-1735

Ronald DeVore Department of Mathematics University of South Carolina Columbia, SC 29208 U.S.A.

e–mail: devore@math.sc.edu
WWW: http://www.math.sc.edu/∼devore/

Tel: 803-777-26323, Fax: 803-777-6527