On Multivariate Adaptive Approximation
Y. K. Hu
K. A. Kopotun Georgia Southern University
Vanderbilt University
X. M. Yu
Southwest Missouri State University
Abstract
Recently, A. Cohen, R. A. DeVore, P. Petrushev and H. Xu investigated nonlinear
approximation in the space BV (R2). They modied the classical adaptive algorithm to
solve related extremal problems. In this paper, we further study the modied adaptive
approximation and obtain results on some extremal problems related to the spaces
r (Rd) of functions of \Bounded Variation" and Besov spaces B (Rd).
V;p
1 Introduction
Nonlinear approximation has been investigated extensively in recent years. In the univariate
case, because of the simplicity of the real line topology, free knot spline approximation is
widely used in numerical computations. But in multivariate case, generating good free spline
approximants is a more complicated and dicult task and is still under research. However,
there is so-called Adaptive Approximation that works well in multidimensional spaces and
is practically easy to implement. Its main disadvantage is that it gives a slightly lower than
the best approximation order. Recently, A. Cohen, R. DeVore, P. Petrushev and H. Xu [7]
successfully introduced a splitting and merging method to modify adaptive approximation
and showed that their method produces near minimizers to the extremal problems related
to the space BV (R2). In this paper, we shall explore their method to show that this new
modied adaptive approximation generates near minimizers to some extremal problems in
r (Rd) of functions of \bounded variation" and Besov spaces B (Rd).
the spaces V;p
If X0 and X1 are quasi-normed spaces continuously embedded in a Hausdor space X ,
then the K -functional for all f 2 X0 + X1 is dened as
K (f; t; X0; X1) := f =inf
fkf0kX0 + tjf1jX1 g ;
f +f
0
1
where k kX0 is a (quasi)norm in X0 , and j jX1 is a (semi)norm or (semiquasi)norm in X1.
The extremal problem we are interested in is as follows. For a given f 2 X0 + X1 , and a
parameter t > 0, nd a function f1 2 X1 with f0 := f , f1 2 X0 which attains the inmum
Supported
by NSF Grant DMS 9705638
1
in the denition of K (f; t; X0; X1). Such a function f1 is called a minimizer. A function
g 2 X1 with f , g 2 X0 is called a near minimizer if
kf , gkX0 + tjgjX1 C f =inf
fkf0kX0 + tjf1jX1 g :
f0 +f1
The problem of nding a minimizer or a near minimizer is closely related to the characterization of K -functionals, interpolation spaces, and approximation spaces.
The interpolation space (X0; X1);q , 0 < < 1, 0 < q 1, consists of all functions
f 2 X0 + X1 such that jf j(X0 ;X1);q < 1, where
8Z 1 1=q
q dt
>
,
<
t K (f; t; X0; X1) t
; 0 < q < 1;
jf j(X0;X1);q := > 0 ,
:sup t K (f; t; X0; X1);
q = 1:
t>0
The approximation space Aq(X; fMn gn2N), > 0, 0 < q 1, consists of all f 2 X such
that
8 1
!1=q
>
X
1
>
< [nE (f; Mn)X ]q
n ; 0 < q < 1;
jf jAq (X;fMngn2 ) := > n=1
>
nE (f; Mn )X ;
q=1
:sup
n1
N
is nite. Here E (f; Mn)X = inf g2Mn kf ,gkX is the error for approximation from the manifold
Mn X , n 2 N. These Mn are usually required to satisfy the assumptions
(i) M0 = f0g;
(ii) M,n Mn+1 ;
(iii)SaMn = Mn for any a 6= 0;
(iv) Mn + Mn Mcn with c := c fMn g ;
(v) 1n=0 Mn is dense in X ;
(vi) Any f 2 X has a best approximation from each Mn .
The following result is due to DeVore and Popov [17], and shows that if the Jackson and
Bernstein inequalities are satised for the spaces X and Y (Y X ), then the approximation
spaces Aq(X; fMn gn2N) can be characterized as interpolation spaces between X and Y .
Theorem A. Suppose that for a pair of spaces X; Y we have
E (f; Mn )X := g2infMn kf , gkX Cn,jf jY ; f 2 Y (Jackson inequality)
and
jgjY CnkgkX ; g 2 Mn ; n 2 N (Bernstein inequality).
Then for 0 < < and 0 < q 1,
Aq(X; fMn gn2N) = (X; Y )=;q :
2
r or B . After reviewing the space B ,
In this paper, we deal with X = Lp and Y = V;p
we shall introduce in this section some notation for piecewise polynomial functions on dyadic
rings. These piecewise polynomial functions are used for Mn . In the next section, we dene
r and moduli of smoothness W , and discuss some of their basic properties.
the spaces V;p
r
In x3 we study the approximation on a ring, which is the key step to obtain a Jackson
inequality. After presenting briey the description of the modied adaptive algorithm in x4,
and discussing properties of multivariate free splines on ring partitions in x5, we establish the
r (in x6) and for B (in x7). In the last
Jackson inequality and Bernstein inequality for V;p
section, we provide a brief discussion of wavelet decompositions and related approximation
spaces.
If 0 < < r and 0 < p; q 1, then the Besov space Bq(Lp; ), Rd, is the set of all
functions f 2 Lp(
) such that
8Z 1 1=q
>
q dt
,
<
t ! (f; t; )p t
; 0 < q < 1;
jf jBq(Lp;
) := > 0 , r
:sup t !r (f; t; )p;
q=1
t>0
is nite. (Here, !r is the usual rth modulus of smoothness.) The quantity j jBq(Lp;
) is a
semi-(quasi)norm for Bq(Lp; ), and the (quasi)norm for Bq(Lp; ) is dened by
k kBq(Lp;
) := k kLp(
) + j jBq(Lp;
) :
Also, for > 0 and 0 < p 1, we dene
B (
) := B ;p(
) := B(L ; ) with 1= = =d + 1=p,
and B := B ([0; 1)d). DeVore and Popov [16] proved
Theorem B. If 0 < < , 0 < p < 1, and = (=d + 1=p),1 , then ,Lp; B =; = B .
Besov spaces have the following properties:
8 0
>
> ; p = p0 ;
<
0
Bq(Lp) Bq0 (Lp0 ) if > = 0; q < q0; p = p0;
: = 0; q = q0; p > p0:
It also follows from Theorem B that B B 0 if > 0.
Let D k (Rd), k 2 Z, denote the collection of all dyadic cubes in Rd of side length 2,k , i.e.,
D k (Rd) := [l12,k ; (l1 + 1)2,k ) [ld2,k ; (ld + 1)2,k ) j li 2 Z; 1 i d ;
and let D (Rd) be the collection of all dyadic cubes in Rd,
D (Rd) :=
[
D k (Rd):
k2Z
It will also be convenient to denote
D k (
) := I 2 D k (Rd) jI 3
and
D (
) :=
[
D k (
) = I 2 D (Rd) jI :
k2Z
We will say that R = I n J is a dyadic ring if I; J 2 D (Rd) (with J possibly empty) and
J ( I . The set of all dyadic rings will be denoted by
D (Rd) := R = I n J I , J 2 D (Rd), and J ( I ;
and
D (
) := R 2 D (Rd) jR :
Given a dyadic ring R = I n J we denote R := I and R := J . This notation turns out to
be rather convenient later in the paper. Also, we note that a dyadic ring R is a cube if and
only if R = R, and will say that dyadic cubes are degenerate dyadic rings.
It will also be convenient to denote the class of all (nite) partitions of 2 D (Rd) into
dyadic rings by r(
), i.e.,
r (
) := fRigi2 jj < 1; Ri 2 D (
); Ri \ Rj = ; if i 6= j , [i2 Ri = :
Also, let r,1 denote the set of all algebraic polynomials of total degree < r, and let n;r (
)
be the set of all piecewise polynomial functions S of order r on partitions in r (
)
consisting of not more than n dyadic rings, i.e.,
(1.1)
X
n;r (
) = S S (x) = pi(x)Ri (x); fRigi=1 2 r (
); n; pi 2 r,1 :
i=1
In all of the above, if is equal to [0; 1)d then it will be omitted. For example, D :=
D ([0; 1)d ), r := r ([0; 1)d), n;r := n;r ([0; 1)d ), etc.
2 Spaces of Functions of \Bounded Variation"
Given a cube I , let len(I ) denote its sidelength. For example, if I 2 D k , then len(I ) = 2,k .
Then, for any cube I , vol(I ) = len(I )d, where, as usual, vol(
) denotes the measure of . If
R is a dyadic ring (R 2 D), then we dene len(R) := len(R), and hence vol(R) vol(R) =
len(R )d. In fact, vol(R ) vol(R) (1 , 2,d ) vol(R ).
r denote the set of functions f 2
For f 2 Lp([0; 1)d), 0 < < p, and r 2 N, let V;p
d
Lp([0; 1) ) for which the \variation over rings"
jf jV;pr := sup
fRi gi2 2r
X
i2
!r (f; len(Ri); Ri)p
! 1
r = Lp . This is the reason for the restriction < p.
is nite. We note that, if p, then V;p
4
Also, for f 2 Lp([0; 1)d ), 0 < < p, := 1= , 1=p, and r 2 N, we dene a modulus
Wr (f; t);p := sup
sup
h
n
h
0<ht fRi gi=1 2r
n
X
i=1
!r (f; len(Ri); Ri)p
! 1
;
where the second sup is taken over all partitions of [0; 1)d consisting \of about 1=h rings":
rh := ffRigni=1 2 rjn [1=h] + 1g :
This modulus is a generalization of the univariate modulus (f; t);p of R. A. DeVore and
X. M. Yu [19]. It is also a modication and generalization of the univariate characteristic
s;p(n; f ) of Pekarskii [23].
Let Ef (R)p denote the rate of Lp-approximation of a function f dened in a region R
(which can be a cube, a ring, a rectangular solid in Rd, etc.) by polynomials of total degree
< r, i.e., Ef (R)p := E (f; r,1)Lp(R) = inf P 2r,1 kf , P kLp (R).
Remark. Because of the equivalence (see Lemma 1)
Ef (R)p !r (f; len(R); R)p
for any dyadic ring R, the moduli !r in the above denitions can be replaced by Ef (R)p.
For example,
Wr (f; t);p sup
sup h
0<ht fRigni=1 2rh
n
X
i=1
Ef (Ri)p
! 1
:
We now mention some of the important properties of the modulus Wr (f; t);p which are
used later in the paper. First of all, it immediately follows from the denition that Wr (f; t);p
is a nondecreasing function of t such that
Wr (f + g; t);p C (Wr (f; t);p + Wr (g; t);p)
and
Wr (f; Mt);p M 1=,1=pWr (f; t);p; M 1:
Also,
(2.1)
Wr (f; t);p C kf kLp for all f 2 Lp([0; 1)d ) :
Indeed, using Holder's inequality we have
Wr (f; t);p C sup
sup
h
n
0<ht fRigi=1 2rh
n
X
i=1
kf kLp(Ri)
C sup sup
h n1=,1=p
0<ht fRigni=1 2rh
C kf kLp :
5
n
X
i=1
!1=
kf kpLp(Ri)
!1=p
r ,
Also, for any g 2 V;p
Wr (g; t);p t jgjV;pr ;
(2.2)
since
Wr (g; t);p = sup
sup
h
n
0<ht fRi gi=1 2rh
t sup
n
=
fRigi=1 2r
t jgjV;pr :
X
n
i=1
n
X
i=1
!r (g; len(Ri); Ri)p
!r (g; len(Ri ); Ri)p
!1=
!1=
3 Approximation on a ring
We say that a rectangular solid is regular if the ratio of lengths of any two of its sides is
between 1=4 and 4. Let R be a dyadic ring. We shall show that R can be represented as a
union of regular dyadic rectangular solids, R = [i=1ri , = (R), such that
1. 1 2d;
2. one of the children of R (see x4 for the denition of a child) is contained in all those
ri which satisfy vol(ri) 12 vol(R ). We denote this child by r0 and call it \the root
of the union". All those ri containing it are called branches;
3. any ri (i = 1; : : : ; ) in the union is either a branch or is intersecting a branch rj with
vol(ri \ rj ) 1=2 vol(ri).
Lemma 1. Let R be a dyadic ring in Rd. Then there exists a representation of R as a
union of regular dyadic rectangular solids, R = [i=1 ri, such that the above three conditions
are satised. Moreover, for all 0 < p 1,
Ef (R)p C
X
i=1
p
p
!r (f; d vol(ri); ri)p C!r (f; d vol(R); R)p ;
where C is a constant which depends only on r, d and p and is independent of R.
Proof. Without loss of generality, we may assume that R = [0; 1)d and that R = [a1; a1 +
2,k ) [a2; a2 + 2,k ) [ad; ad + 2,k ) with ai 0 and ai + 2,k 1=2, i = 1; 2; ; d. By
rotating the coordinate axes if necessary, we may also assume that 0 a1 a2 ad.
Notice that for each i = 1; 2; ; d, we have either ai = 0 or ai 2,k .
Dene ri := [0; 1) [0; 1) [ai + 2,k ; 1) [0; 1) [0; 1) for i = 1; 2; ; d,
and rd+i := [0; ci;1) [0; ci;i,1) [0; ai) [ai+1; ai+1 + ci;i+1) [ad; ad + ci;d) for
i = 1; 2; ; d, where
ci;j :=
max ,2(a
j + 2,k ); ai
max(2,k+1 ; ai) ;
6
; j < i;
j > i:
Note that if ai = 0, then rd+ = ; for all = 1; : : : ; i. In particular, if k = 1, then
rd+i = ; for all i = 1; : : : ; d. Keeping that in mind, everywhere below we assume that k 2
(the case k = 1 can be treated similarly and, in fact, is much simpler).
d r is a desired expression of R. It is apparent
We are going to prove that the union [2i=1
i
that we have the rst two conditions satised with r0 = [1=2; 1) [1=2; 1) as its root
and ri, i = 1; 2; ; d, as its branches. From the denitions of ri and rd+i , we also see that
all of them are regular dyadic rectangular solids.
d ri . Let x = (x1; x2; ; xd ) 2 R. Then there exists at least
We now show that R = [2i=1
one i such that either ai + 2,k xi < 1, or 0 xi < ai and 0 xj < aj + 2,k for all j 6= i.
In the former case, we have x 2 ri. For the latter case, let i0 := maxfi j 0 xi < ai and 0 xj < aj + 2,k for all j 6= ig. By the denition of rd+i (i = 1; 2; ; d), we have x 2 rd+i0
because 0 xi0 < ai0 , aj xj < aj + 2,k for all j = i0 + 1; ; d and ci0;j aj + 2,k for
all j < i0. It is easy to see, on the other hand, that all ri (i = 1; 2; ; 2d) are subsets of R
(note that all ci;j for j < i do not exceed 1 by the assumption ai + 2,k 1=2 and all ci;j for
d ri .
j > i do not exceed 1=2). Therefore, we have R = [2i=1
It remains to show that for each nonempty rectangular solid rd+i , i = 1; : : : ; d, there
exists a branch rj with vol(rd+i \ rj ) 1=2 vol(Q
rd+i ). (ItQis easy to see that the solid rd+i,
i = 1; : : : ; d is not a branch since vol(rd+i ) = ai i,=11 ci; d=i+1 ci; ai < 1=2.)
Assume that rd+i 6= ;. From the denitions of rj and rd+i , we have vol(rd+i \ rj ) 1=2 vol(rd+i) if j 6= i. Indeed, we have rd+i \ rj = [0; ci;1) [0; ci;i,1) [0; ai) [ai+1; ai+1 +
ci;i+1) [aj + 2,k ; aj + ci;j ) [ad; ad + ci;d), if j > i; and rd+i \ rj = [0; ci;1) [aj + 2,k ; ci;j ) [0; ci;i,1) [0; ai) [ai+1; ai+1 + ci;i+1) [ad; ad + ci;d), if j < i.
Since ci;j 2,k+1 for j > i and ci;j 2(aj + 2,k ) for j < i, so vol(rd+i \ rj ) 1=2 vol(rd+i )
and then the third condition is satised.
Now let us estimate Ef (R)p using the above decomposition of R into ri. The case p = 1
is trivial, and so we assume that 0 < p < 1. Let Pri 2 r,1 denote a polynomial of best
Lp-approximation to f on ri, i.e., Ef (ri)p = kf , Pri kLp(ri).
Since we have
Ef (R)pp kf , Pr0 kpLp(R)
X
i=1
kf , Pr0 kpLp(ri);
if we can show for each i (i = 1; 2; ; ) that
kf , Pr0 kLp(ri) C
then
Ef (R)pp
C
C
X
i=1
X
i=1
X
j =1
Ef (rj )p;
Ef (ri)pp
!r (f; vol(ri)1=d; ri)pp :
7
The inequality Ef (ri)p C!r (f; vol(ri)1=d; ri)p (used in the last estimate) can easily be
obtained from the multidimensional Whitney theorem for a unit cube using the ane transformation T : ri ! [0; 1)d and taking into account that ri is a regular solid.
Now, if ri is a branch, then
kf , Pr0 kLp(ri) C kPr0 , Pri kLp(ri) + kf , Pri kLp(ri)
C kPr0 , Pri kLp(r0) + Ef (ri)p
C kf , Pr0 kLp(r0) + kf , Pri kLp(r0) + Ef (ri)p
C [Ef (r0)p + Ef (ri)p] CEf (ri)p;
because r0 ri and vol(r0) = 2,d 2,d vol(ri).
If ri is not a branch, by what proved, there exists a branch rj such that vol(ri \ rj ) 1=2 vol(ri). Then, we have
kf , Pr0 kLp(ri) C kPr0 , Pri kLp(ri) + kf , Pri kLp(ri)
C kPr0 , Pri kLp(ri\rj ) + Ef (ri)p
C kf , Pr0 kLp(ri\rj ) + kf ,Pri kLp(ri\rj ) + Ef (ri)p
C kf , Pr0 kLp(rj ) + Ef (ri)p C [Ef (rj )p + Ef (ri)p] :
The proof is now completed.
To emphasize that ri and correspond to a particular ring R we will use the notation
R
ri and R. Also, if R is a cube (degenerate ring) we denote R := 1 and r1R := R.
Corollary 2. Let R be a dyadic ring. Then, for 0 < < r and 0 < p < 1 , we have
Ef (R)p C
R
X
i=1
Ef (riR)p C
R
X
i=1
jf jB(riR) C jf jB(R) :
Corollary 2 immediately follows from Lemma 1 and the following Lemma C.
Lemma C (DeVore and Popov [16], see also [9]). Let 1= = =d+1=p, then Bp(L ) ,!
Lp, that is, for all f 2 Bp(L ), kf kLp C kf kBp(L ). In particular, kf kLp C kf kBq(L ) for
all 0 < q p. Moreover, for each I 2 D (Rd ) and f 2 B (I ),
Ef (I )p C jf jB(I ) ; 0 < < r :
4 Description of Algorithm
We will use the algorithm developed by Cohen, DeVore, Petrushev and Xu [7] to construct
r and B (see
piecewise polynomial functions satisfying Jackson inequalities in the spaces V;p
x6 and x7). For completeness, we describe the algorithm in this section. First, we recall
some denitions. Let I be a dyadic cube (I 2 D ). Then
If I 2 D k , then J is the parent of I if and only if J 2 D k,1 and I J .
8
J is a child of I if and only if I is the parent of J .
I and J are brothers if and only if they have the same parent.
J is a descendent of I if and only if J 2 D and J ( I .
J is an ancestor of I if and only if I is a descendent of J .
Let denote a nonnegative set function dened on the algebra A that consists of all
subsets of [0; 1)d formed by nite unions and intersections of rings from D and their complements. We assume that has the following properties:
(i) is subadditive: (R1)+(R2) (R1 [ R2) for R1, R2 2 A such that R1 \ R2 = ;;
(ii) (R) ! 0 uniformly as vol(R) ! 0.
The set function (R) usually depends on the error of approximation of f on R. For instance,
we can choose (R) to be Ef (R)pp.
Given a parameter " > 0, we dene " to be the set of cubes I 2 D such that (I ) > ",
and we call " a tree which means that whenever I 2 " and I 6= [0; 1)d, then its parent
also belongs to ". Note that " has nite cardinality because of the second condition on
. In " , we have three dierent types of cubes:
(i) The set F" of nal cubes consists the elements I 2 " with no child in " .
(ii) The set N" of branching cubes consists of the elements I 2 " with more than one
child in ".
(iii) The set C" of chaining cubes consists of the elements I 2 " with exactly one child in
".
Moreover, the set C" can be divided into n maximal chains Ck such that C" = [nk=1 Ck with
Ck = fI0; ; Im,1g, m = m(k), where each cube Ii+1 is a child of Ii, i = 0; ; m , 2, I0 is
not a child of a chaining cube and Im,1 is not a parent of a chaining cube. For a set S , let
jS j denote its cardinality. We have (see [7])
jN"j jF"j , 1 and n 2jF"j , 1:
Now, let us describe how to construct a partition P" of [0; 1)d into rings R with (R) ".
In fact, we have P" = P"1 [ P"2 [ P"3, where P"1 is the collection of all children J of the
nal cubes I 2 F" and P"2 is the collection of the children J of the branching cubes I 2 N"
such that J 2= " . The collection P"3 consists of good rings (or cubes) generated from the
maximal chains Ck = fI0; ; Im,1g, m = m(k), k = 1; ; n by the following recursion
algorithm. Note that the last cube Im,1 of Ck always contains exactly one child Im from "
which is in either F" or N". So, for each Ck , we rst dene 0 = j0 < j1 < < jp = m in
this way that, assuming ji < m is chosen, we choose ji+1 as follows:
(i) if (Iji n Im) ", then ji+1 := m and the algorithm terminates.
(ii) if (Iji n Iji+1) > ", then ji+1 := ji + 1.
9
(iii) otherwise, ji+1 is chosen such that (Iji n Iji+1 ) " and (Iji n Iji+1 +1) > ".
Then the set P"3 consists of, from each maximal chain Ck , (i) all rings Iji n Iji+1 such that
(Iji n Iji+1 ) ", (ii) the children of Iji that dier from Iji+1 for all i such that (Iji n Iji+1 ) > "
(which is possible only in the case ji+1 := ji + 1). It is shown in [7] that this P" is a partition
of [0; 1)d satisfying the following theorem.
Theorem D. Let " > 0 be such that " 6= ;. Then, there exist a partition P" of [0; 1)d
f" of pairwise disjoint rings
into disjoint rings such that (K ) " if K 2 P" , and a set P
f", and jP"j 8jPf" j. (In particular, we can choose P" to be the
such that (K ) > " if K 2 P
partition produced by the algorithm above.)
This theorem not only gives a partition of [0; 1)d into disjoint good rings, but also it shows
the number of good rings in the partition is controlled by the number of certain bad rings
that are pairwise disjoint. The latter is more important to the estimation of approximation
degree.
5 Multivariate Free Splines on Ring Partitions
It is easy to see that n;r are nonlinear manifolds, i.e., the sum of two functions from n;r
does not have to lie in n;r . However, as shown in the two lemmas below,Pthe sum belongs
to Cn;r . This will be shown via Sn;r (I ), the set of all S such that S = ni=1 piIi , where
Ii I are dyadic cubes (which are not necessarily disjoint) and pi 2 r,1.
Lemma 3. If n 2 N and I 2 DP
(Rd), then Sn;r (I ) N;r (I ) for some N (n,1)2d +n+1 <
n(2d + 1). That is, if S (x) = ni=1 pi (x)Ii (x), where fIigni=1 is a collection of n (distinct
but not necessarily disjoint) dyadic cubes contained in I , and pi 2 r,1 , then it can be
represented as
(5.1)
S (x) =
N
X
j =1
qj (x)Rj (x);
fRj gNj=1 2 r(I ); qj 2 r,1:
Proof. We use induction on n. It is trivial to verify the result for n = 1, that is, S1;r (I ) 2;r (I ). Now wePsuppose the result is valid for all I 2 D (Rd) and all n, 1 n < n.
Let S (x) = ni=1 pi (x)Ii (x), where fI1; : : : ; Ing is a collection of distinct cubes in I , and
let Ie be the smallest dyadic cube in D (I ) that contains [iIi. The following two cases are
possible.
Case 1 : Ie coincides with one of Ii , say, Ie = In . Then the cubes I1; : : : ; In,1 are contained
in Ie and
n,1
X
S (x) , pn (x) =
i=1
pi (x)Ii (x) for x 2 Ie:
Thus, we can use the induction hypothesis for Sn,1;r (Ie) to conclude that, for x 2 Ie,
S (x) , pn (x) =
Ne
X
j =1
qj (x)Rj (x); fRj gNje=1 2 r(Ie) ;
10
where Ne (n , 2)2d + n. Now, if Ie ( I , then
S (x) = 0 I nIe(x) +
Ne
X
j =1
(qj (x) + pn (x)) Rj (x)
for any x 2 I , and fRj gNje=1 [ fI n Ieg 2 r(I ). If Ie = I , then
S (x) =
Ne
X
j =1
(qj (x) + pn (x)) Rj (x)
for any x 2 I , and fRj gNje=1 2 r (I ). In both of these cases N Ne + 1 (n , 2)2d + n + 1 (n , 1)2d + n + 1.
Case 2 : Ie ) Ii , i = 1; : : : ; n. Then each of the cubes Ii , i = 1; : : : ; n, is contained in one
of the children of Ie. Let C1; : : : ; Cm, 2 m 2d , be the children of Ie containing at least
one of Ii, i = 1; : : : ; n (m cannot be 1 since, otherwise, Ie would not be the smallest cube
containing [iIi), and let Cm+1; : : : ; C2d be the children of Ie having empty intersection with
[iIi. For each
k = 1; : : : ; m, denote the number of cubes Ii, 1 i n, contained in Ck by
P
m
nk . Then k=1 nk = n, and, since m 2 and nk 1, we conclude that nk n , 1 for all
k = 1; : : : ; m. Thus, we can use the induction hypothesis for each of Snk ;r (Ck ), k = 1; : : : ; m,
and conclude that
n
X
j =1
pj (x)Ij (x) =
lk
m X
X
k=1 j =1
qk;j (x)Rk;j (x)
for any x 2 I , where lk (nk , 1)2d + nk + 1 and fRk;j gljk=1 2 r (Ck ). Now,
Se(x) =
X
2d,m
k=1
0 Cm+k (x) +
lk
m X
X
qk;j (x)Rk;j (x)
k=1 j =1
[mk=1fRk;j gljk=1
S
for any x 2 Ie (actually any x 2 I ). Note that
[2kd=1,m fCm+k g 2 r(Ie) and,
thus,
(e
e I;
S (x) = SSe((xx));+ 0 (x); ifif IIe =
( I:
I nIe
S
S
In the case Ie ( I , [mk=1 fRk;j gljk=1 [2kd=1,m fCm+k g fI n Ieg 2 r (I ). Thus,
N
2d , m + 1 +
2d , m + 1 +
m
X
k=1
m
lk
X,
(nk , 1)2d + nk + 1
k=1
d
= 2 , m + 1 + (n , m)2d + n + m
= (n , m + 1)2d + n + 1 (n , 1)2d + n + 1;
which completes the proof of the lemma.
11
Lemma 4. If m; n; r 2 N, and I 2 D (Rd), then m;r (I ) + n;r (I ) (2d+1)(m+n);r (I ).
Proof. It can be readily veried that n;r Sn;r and Sn;r + Sm;r Sn+m;r . These inclusions
and Lemma 3 immediately imply that
n;r + m;r Sn;r + Sm;r Sn+m;r (2d+1)(n+m);r :
The following lemma shows that any function f 2 Lp(I ), I 2 D , has a best approximant
from the manifold n;r . Its proof is the same as that of Lemma 6.1 of [7].
Lemma E. For each f 2 Lp(I ) and n 2 N there exists g 2 n;r (I ) such that kf , gkLp(I ) =
E (f; n;r )Lp .
6 Adaptive Approximation in V;pr
Theorem 5. Let 0 < < p < 1, := 1= , 1=p, and r 2 N. Then for f 2 Lp([0; 1)d ) and
t > 0 we have
r ) = inf kf , g k + t jg j r W (f; t) :
K (f; t ; Lp; V;p
Lp
V;p
r
;p
g 2V r
;p
In the case d = 1, a version of this theorem was proved in [19]. Note that, if d = 1,
then a partition of [0; 1] into rings is just a regular partition into intervals. Theorem 5 is an
immediate corollary of the following result.
Theorem 6. Let 0 < < p < 1, := 1= , 1=p, and r 2 N. Then
(i) For any f 2 Lp([0; 1)d) and n 2 N there exists g 2 n;r such that
(6.1)
kf , gkLp C Wr(f; 1=n);p
(Jackson inequality);
(ii) For any g 2 n;r we have
(6.2)
jgjV;pr Cn Wr (g; 1=n);p
(Bernstein inequality).
Theorem 6 will be proved in Sections 6.1 and 6.2.
r , using (2.1) and (2.2) we have
Proof of Theorem 5. First of all, for any g 2 V;p
Wr (f; t);p C (,Wr (f , g; t);p + Wr(g; t);p)
C kf , gkLp + t jgjV;pr :
r , we obtain
Hence, taking inmum over all g 2 V;p
Wr (f; t);p CK (f; t; Lp; V;pr ) :
12
Now, suppose that Theorem 6 is proved. Let t > 0 and choose n := [1=t] + 1. Then
Theorem 6 and inequality (2.1) imply that there exists g 2 n;r such that
t jgjV;pr C (tn) Wr (g; 1=n);p
C Wr (g; 1=n);p
C (,Wr (g , f; 1=n);p + Wr (f;1=n);p)
C kg , f kLp + Wr (f; 1=n);p
C Wr (f; 1=n);p ;
and, therefore,
r ) kf , g k + t jg j r
K (f; t ; Lp; V;p
Lp
V;p
C Wr (f; 1=n);p C Wr (f; t);p:
Corollary 7. Let 0 < < p < 1, := 1= , 1=p, and n; r 2 N. Then
r ;
r for any f 2 V;p
(i) E (f; n;r )Lp Cn, jf jV;p
(ii) jgjV;pr Cn kgkLp for any g 2 n;r .
Proof. The statement (i) immediately follows from (6.1) and (2.2), and (ii) is a consequence
of (6.2) and (2.1).
The following is a consequence of the above corollary and Theorems A and 5.
Corollary 8. Let 0 < < p < 1, := 1= , 1=p, r 2 N. Then, for 0 < < and
0 < q 1,
(6.3)
,
r
Aq(Lp; fn;r gn2N) = Lp; V;p
=;q
:
Corollary 9. Let 0 < < p < 1 and r 2 N. Then, for 0 < < 1= , 1=p and 0 < q < 1,
we have
Aq(Lp; fn;r gn2N) =
f 2 Lp([0;
Z 1 t,Wr (f; t);pq dt < 1 :
t
0
1)d )
Corollary 10 (q = 1). Let 0 < < p < 1 and r 2 N. Then, for 0 < < 1= , 1=p,
E (f; n;r )Lp = O(n, ) () Wr (f; t);p = O(t):
The following corollary shows that there exists g 2 n;r (in fact, the piecewise polynomial
function g that we construct in Section 6.1 will do), which is a near-minimizer for the K r ).
functional K (f; n, ; Lp; V;p
Corollary 11. Let 0 < < p < 1, := 1= , 1=p, and r 2 N. Then for f 2 Lp([0; 1)d )
and n 2 N there exists g 2 n;r such that
kf , gkLp + n, jgjV;pr CK (f; n, ; Lp; V;pr ) :
13
Proof. Using Theorem 5 with t = 1=n, Theorem 6, and properties of Wr we conclude that
there exists g 2 n;r such that
kf , gkLp + n, jgjV;pr kf , gkLp + C Wr (g; 1=n);p
kf , gkLp + C Wr (g , f; 1=n);p + C Wr (f; 1=n);p
C kf , gkLp + C Wr(f; 1=n);p
r ):
C Wr(f; 1=n);p CK (f; n, ; Lp; V;p
6.1 Jackson Inequality for V;pr
First of all, we show that any set of (pairwise) disjoint rings and cubes can be complemented
to a partition of [0; 1)d in r.
Lemma 12. Let R be a collection of pairwise disjoint dyadic rings and cubes contained in
a dyadic cube I , and let jRj denote its cardinality. Then there exists a partition TR (I ) of I
into dyadic rings (TR (I ) 2 r (I )) such that R TR (I ) and jTR (I )j (2d + 2)jRj , 2d + 1
(and, therefore, jTR (I )j 2d+1 jRj).
Proof. The idea of the proof of this lemma is similar to that of Lemma 3. Clearly the
statement is true for a cube I 2 D if and only if it is true for I = [0; 1)d . We proceed
by
on jRj. If jRj = 1, then R = fK g. Now we
choose TR := TR([0; 1)d ) =
[0;induction
d
1) n K; K (if K is a cube, i.e., K = K ), and TR = [0; 1)d n K ; K; K (if K is a
non-degenerate ring, K = K n K ). Clearly, jTRj 3.
Now, suppose that the lemma is proved for all collections R such that jRj N , and
consider R such that jRj = N + 1, N 1, and I = [0; 1)d . For a set [0; 1)d denote
R(
) = fK 2 Rj int (K ) \ int (
) 6= ;g. Let Q be the smallest dyadic cube in D (I ) that
contains [R2RR. We have the following two possible cases similar to those in Lemma 3.
Case 1: Q coincides with R for some R 2 R. Since R(R ) = R n fRg contains N
cubes and rings from R we can use the induction hypothesis to conclude that there exists a
partition TR(R)(R) of R such that
jTR(R)(R)j (2d + 2)jR(R )j , 2d + 1 (2d + 2)N , 2d + 1 :
Now, TR := TR(R)(R ) [ fRg [ f[0; 1)d n Rg is a desired partition of [0; 1)d, and
jTRj = 2 + jTR(R)(R)j (2d + 2)(N + 1) , 2d + 1 :
Case 2: Q ) R , 8R 2 R. By the assumption of Q, at least two of its 2d children
I , = 1; 2; : : : ; 2d , contain members of R in this case, therefore jR(I )j N for any
1 2d , and we can use the induction hypothesis to construct partitions TR(I )(I ) of I
as follows:
if R(I ) 6= ; then let TR(I )(I ) be a partition of I containing R(I ) and such that
jTR(I )(I )j (2d + 2)jR(I )j , 2d + 1 (its existence is guaranteed by our induction
hypothesis).
if R(I ) = ;, then we choose TR(I )(I ) := fI g.
14
Now,
TR = [0; 1)d n Q [ [2d=1 TR(I )(I )
is a partition of [0; 1)d containing R. Taking into account that
X
jR(I )j = jRj;
I :R(I )6=;
we have
jTRj = 1 +
2d
X
=1
jTR(I )(I )j
= 1 + jfI jR(I ) = ;gj +
1 + jfI jR(I ) = ;gj +
X
I :R(I )6=;
jTR(I )(I )j
X , d
(2 + 2)jR(I )j , 2d + 1
I :R(I )6=;
1 + jfI jR(I ) = ;gj , (2d , 1) jfI jR(I ) 6= ;gj + (2d + 2)jRj
(2d + 2)jRj , 2d + 1 ;
since jfI jR(I ) =
6 ;gj 2 and jfI jR(I ) = ;gj + jfI jR(I ) 6= ;gj = 2d.
Proof of (6.1). Let (R) = Ef (R)pp, " = n,1 Wr (f; 1=n)p;p (without loss of generality we
can assume that Wr (f; 1=n);p =
6 0, since Wr (f; t);p = 0 only if f 2 r,1), and let P" be
a partition produced by the algorithm described in Section 4. We use Theorem D to show
that jP"j Cn. Suppose that jP"j n (otherwise, we are done). Since the set Pf" (see
Theorem D) consists of pairwise disjoint rings and cubes contained in [0; 1)d, we can use
Lemma 12 to enlarge Pf" to TPf" , a partition of [0; 1)d into dyadic rings such that
jPf"j jTPf" j 2d+1jPf"j :
If we denote jPf"j = N and jTPf" j = Ne , then N Ne 2d+1 N . Now, note that the inequalities
jP"j n (our assumption above) and jP"j 8N (Theorem D) imply that Ne N n=8.
Recalling that Ef (Q)pp > " for Q 2 Pf", we have
N = jPf"j ",=p
X
Q2Pf"
Ef (Q)p ",=p
X
Q2TPf"
Ne
Ef (Q)p
X
C",=pN sup Ne , Ef (Qi)p
fQi gNie=1 2r
C",=pN i=1
sup
sup
n
0<h1=Ne fQi gi=1 2rh
h
n
X
Ef (Qi)p
i=1
C",=pN Wr (f; 1=N );p C",=pN Wr (f; 1=n);p
e
15
Cn=pN ;
which implies N Cn, since = 1= , 1=p.
Dene g by
g(x) := PIi (x); for x 2 Ii;
where Ii 2 P", and PIi are best Lp approximants to f on Ii from polynomials of degree < r.
Then g 2 Cn;r and
X
kf , gkpLp =
kf , PIi kpLp(Ii ) "jP"j
Ii 2P"
which implies (6.1).
Cn" C Wr (f; 1=n)p;p;
6.2 Bernstein Inequality for V;pr
Let g 2 n;r be a piecewise polynomial function of order r dened on a partition Pg =
fRigni=1 2 r , i.e., for each Ri 2 Pg , gjRi 2 r,1. In the following lemma we show that, for
any nite ring partition P = fQigi2 2 r of [0; 1)d, if
g := fi 2 j Eg (Qi)p 6= 0g ;
then jg j 2n. More precisely, we prove
Lemma 13. Let P 2 r be given. For any Q 2 P with Eg (Q)p 6= 0, there exists an R 2 Pg
that satises one of the two conditions below:
(i) Q ) R and Q \ R 6= ;;
(ii) R Q ) R 6= ; and Q 6 R .
Moreover, any given R 2 Pg corresponds to at most one ring Q satisfying (i), and at most
one Q satisfying (ii). Therefore, jfijEg (Qi )p 6= 0; Qi 2 Pgj 2jPg j.
Proof. We shall repeatedly use the fact that two dyadic cubes are either disjoint or one is
contained in the other. We x Q such that Eg (Q)p 6= 0. Because Pg 2 r , there exists
R 2 Pg such that Q \ R Q \ R 6= ; and Q 6 R, thus either Q ) R , which is (i); or
R Q. In the latter case, from Q 6 R we know Q \ R 6= ;, and in particular R 6= ;;
from Q \ R 6= ; we know Q 6 R . Therefore Q ) R. From Q 6 R again, we know
Q 6 R , which gives (ii).
For the uniqueness of the ring Q in (i), we x R 2 Pg and suppose there are two such
rings Q and Q0. Since Q \ Q0 R 6= ;, one of them contains the other. Without loss of
generality, we assume Q Q0 . Since Q \ Q0 = ;, we have Q Q0 ) R ; but Q can
not contain R, for Q \ R 6= ;. This contradiction shows the ring in (i) is unique.
For the uniqueness of (ii), we suppose there are two rings Q and Q0 2 P both satisfying
(ii) for the same ring R. Similar to the above, since Q \ Q0 R 6= ;, we can assume
Q Q0. From Q \ Q0 = ; we derive
R Q ) Q Q0 ) R ;
which contradicts the fact Q 6 R .
16
Proof of (6.2). Now, let P = fQi gi2 2 r be an arbitrary nite partition of [0; 1)d into
dyadic rings. We consider its subset fQigi2g , whose cardinality jg j 2n by Lemma 13.
According to Lemma 12 there exists a partition TP;g such that fQigi2g TP;g and
jTP;gj 2d+1 jg j 2d+2 n:
Now, denoting h := 1=(2d+2 n), we have
0
11=
X
jgjV;pr sup
Eg (Qi)p
= sup @ Eg (Qi)p A
P2r i2
P2r i2g
0
11=
!1=
X
X
sup @
Eg (R)p A suph
Eg (R)p
P2r R2TP;g
2r R2
!1=
X
X
!1=
Cn suph h
Eg (R)p
2r
R2
Cn Wr (g; 1=n);p ;
Cn Wr (g; h);p
which is the inequality (6.2).
7 Adaptive Approximation in the Besov Space B In this section, we develop results in the Besov spaces B , which was dened on page 3.
Theorem 14 (Jackson inequality). For every f 2 B , 0 < < r, 0 < p < 1,
E (f; n;r )Lp Cn,=djf jB :
Theorem 15 (Bernstein inequality). Let g 2 n;r , i.e., g = PR2P pR R, where P 2 r
with jPj n, and pR 2 r,1. Also, let 0 < p < 1 and 0 < < minfr; (d,d1)p g. Then
jgjB Cn=dkgkLp :
Corollary 16. Let 0 < p < 1 and 0 < < minfr; (d,d1)p g. Then, for 0 < < =d and
0 < q 1,
Aq (Lp; fn;r gn2N) = (Lp; B )d=;q :
This corollary can be restated as follows
Corollary 160. Let 0 < p < 1 and 0 < < minf dr ; (d,11)p g. Then, for 0 < < and
0 < q 1,
,
Aq (Lp; fn;r gn2N) = Lp; B d
17
=;q :
We can now characterize the interpolation spaces (Lp; B )=;q in terms of the modulus Wr (f; t);p. The following result immediately follows from Corollaries 9 and 16, and
Theorem B.
Corollary 17. Let 0 < < p < 1, r 2 N, 1= = =d + 1=p, and 0 < < minfr; (d,d1)p g.
Then for 0 < < and 0 < q < 1,
Z 1 dt
q
d
,
=d
(Lp; B )=;q = f 2 Lp([0; 1) )
t Wr (f; t);p t < 1 :
0
In particular, if q = = (=d + 1=p),1 , then
Z 1 dt
d
,
=d
(Lp; B )=; = B = f 2 Lp([0; 1) )
t Wr (f; t);p t < 1 ;
0
and, thus,
Z 1
Z 1
dt
,
d
t Wr (f; t );p t < 1 ()
t,!r (f; t) dtt < 1:
0
0
Using Corollaries 10 and 16 one can also get a similar statement in the case q = 1.
7.1 Proof of Jackson Inequality for B Without loss of generality we can assume that jf jB 6= 0. Let (R) = Ef (R)pp, = (=d +
1=p),1 , and " = n,p= jf jpB . Also, let P" be a partition of [0; 1)d produced by the algorithm
of Section 4. Then jP"j 8jPf"j (see Theorem D), where Pf" is a set of pairwise disjoint
dyadic rings such that for all R 2 Pf", (R) > ".
We now estimate jPf"j. If R 2 Pf", then 1 < ",=pEf (R)p , and using Corollary 2 we have
the following estimates.
(7.1)
jPf"
j ",=p
X
R2Pf"
Ef (R)p
C",=p
where, if R 2 Pf" is a cube, then R := 1 and r1R := R.
We will now show that
(7.2)
R
XX
R2Pf" i=1
R
XX
R2Pf" i=1
jf jB(riR) ;
jf jB(riR) C jf jB ;
which together with (7.1) implies that jP"j 8jPf"j C",=pjf jB Cn.
To prove (7.2) note that if Q is a regular solid then the following holds (see DeVore [8,
ineq. (4.5)], for example, keeping in mind that the result for a regular solid follows from that
for a cube by change of variables):
!r (f; t; Q)
t,d
Z
Z
[,t;t]d Q(rs)
18
jrs(f; x)j dx ds;
where Q(h) := fxj[x; x + h] Qg and rs is the usual rth dierence. Thus, taking into
account that according to Lemma 1 each x 2 R belongs to at most 2d regular solids riR,
we have
R
XX
R2Pf" i=1
jf jB(riR)
=
R Z 1
XX
R2Pf" i=1 0
1
=
t,,1
t,,1!r (f; t; riR) dt
0 R
1
X
X
@
!r (f; t; riR) A dt
0
R02Pf" i=1
1
Z1
Z Z
R
X
X
C t,,1 @
t,d
jrs(f; x)j dxdsA dt
R
d
R2PfZ" i=1 Z [,t;t] ri (rs)
Z0 1
,
,
1
,
d
r
C t
t
js(f; x)j dxds dt
[,t;t]d [0; 1)d (rs)
Z0 1
Z
C
t,,1 !r (f; t; [0; 1)d ) dt C jf jB :
0
Thus, jP"j Cn, and dening g(x) := PIi (x), for x 2 Ii, where Ii 2 P", and PIi are best Lp
approximants to f on Ii from polynomials of degree < r (hence, g 2 Cn;r ), we have
kf
, gkpLp
=
Z
jf
d
[0; 1)
X
R2P"
, gjp
=
XZ
R2P" R
" = "jP"j Cn" jf , gjp =
Cn1,p=
X
R2P"
p
jf jB :
Ef (R)pp
Thus,
E (f; n;r )Lp kf , gkLp Cn,=djf jB :
7.2 Proof of Bernstein Inequality for B The following proof is somewhat similar to the proofs that were used in [15] and [9]. We
denote aR(x) := pR (x)R(x) and note that
kgkpLp
=
=
Z
[0; 1)d
XZ
R2P R
To estimate jgjB we rst show that
(7.3)
jg(x)jp dx =
!r (g; t) = !r
XZ
R2P R
jaR(x)jp dx =
X
R2P
jg(x)jp dx
kaRkpLp(R) :
, X a ; t C X ! (a ; t) :
R r R R2P
R2P
19
P
Note that this inequality is trivial if 1, since, in this case, k fikL general , we let x; h 2 Rd be xed. Then
rh(g; x)
P
r
X
(,1)r,i
P kfik
L .
For
r
g(x + ih)
i
i=0
r X
r
X
r
,
i
=
(,1) i
aR(x + ih)
i=0
R2P
r
r
X
X
r
,
i
=
(,1) i
aR(x + ih)
i=0
R2P ;R\fx+ih:0irg6=;
= rh(eg; x) ;
=
where eg(x) = R2Pe aR(x), Pe := fR 2 P ; R \ fx + ih : 0 i rg 6= ;g. Now, using the
observation that Pe r + 1 we have
X r (a ; x)
h R
e
X r R2P X
jrh(g; x)j = jrh(eg; x)j = C (r; )
R2Pe
jh(aR; x)j C
R2P
jrh(aR; x)j :
Therefore, integrating the P
last inequality
over [0; 1)d, taking supremum over h : jhj t, and
P
using the inequality suph ( fi) suph fi, we obtain (7.3).
We now x R 2 P and h 2 Rd, and denote
D(R; r; h) := x 2 [0; 1)djfx; : : :; x + rhg \ R 6= ;; fx; : : :; x + rhg \ RC 6= ; ;
where RC denotes the complement of R (RC = [0; 1)d n R). Then
vol (D(R; r; h)) C min fvol(R); vol(@R)jhjg C min vol(R); vol(R)1,1=djhj :
Also,
jrh(aR; x)j 2r
Thus,
!r (aR; t)
= sup
ja (x)j + : : : + ja (x + rh)j ; x 2 D(R; r; h) ;
R
R
0;
Z
otherwise :
j
rh(aR; x)j
d
Z
dx sup
Z
jhjt [0; 1)
jhjt D(R;r;h)
2r (r + 1) sup
kaRkL1 dx
jhjt D(R;r;h)
C kaRkL1 sup vol(D(R; r; h))
jhjt
C kaRkL1(R) min vol(R); vol(R)1,1=dt :
20
jrh(aR; x)j dx
Now, vol(R) vol(R), and, hence, for any polynomial pr of total degree < r, kpr kLp(R) kpr kLp(R) and
kpr kL1 (R) kpr kL1(R) C (vol(R)),1=p kpr kLp(R) C (vol(R)),1=p kpr kLp(R)
(see Ditzian [20], for example). Thus,
!r (aR; t) C (vol(R)),=p min vol(R); vol(R)1,1=dt kaRkLp(R) ;
and using (7.3) and the fact that < 1 (this inequality is equivalent to < (d,d1)p ) we have
jgjB
=
Z1
0
C
C
XZ 1
R2P 0
X
R2P
C
r (g; t) dt C
t,,1!
R2P 0
t,,1 (vol(R)),=p min
R2P
t,,1!r (aR; t) dt
vol(R); vol(R)1,1=dt ka k dt
R Lp (R)
(vol(R)),=p kaRkLp(R)
vol(R)1,1=d
X
XZ 1
Z vol(R)1=d
0
t, dt + vol(R)
(vol(R))1,=p,=d kaRkLp(R) = C
Finally, since < p, using Holder's inequality, we have
jg jB C
X
R2P
kaRkLp(R)
!1=
C jPj
1=,1=p
X
R2P
!
Z1
1=d
Xvol(R) R2P
t,,1 dt
kaRkLp(R):
kaRkpLp(R)
!1=p
Cn=dkgkLp :
8 Wavelet Decompositions
Let 2 W1s (Rd) be a compactly supported function which has the following properties:
is renable, i.e.,
X
(8.1)
(x) = cj (2x , j ) :
j 2Zd
satises the Strang-Fix conditions of order r:
(8.2)
^(0) = 1; ^(2j ) = 0; j 2 Zd; j 6= 0;
D ^(2j ) = 0; j 2 Zd; j 6= 0; j j < r :
The shifts of are locally linearly independent, i.e.,
(8.3)
8Q 2 D the
functions ( , j );
j 2 Q = j 2 Zdj meas (fxj(x , j ) 6= 0g \ Q) > 0 ;
are linearly independent over Q.
21
Dene
e n() = f f =
X
I 2D
aI I such that jfaI jaI 6= 0gj n ;
where we use the usual indexing of the translates of dyadic dilates of by dyadic cubes, i.e.,
I (x) := (2k x , j ), where I = j 2,k + 2,k [0; 1)d.
Theorem F (DeVore, Jawerth and Popov [11]). If 2 W1s (Rd) is a compactly supported function satisfying (8.1)-(8.3), then, for each 0 < < minfr; sg and f 2 B ,
E (f; e n())Lp = inf
kf , gkLp Cn,=djf jB ; 0 < p < 1:
e
g2n ()
Theorem G (Jia [21]). Let be a compactly supported function in W1s (Rd), s 2 N. Sup-
pose that is renable, and its shifts are locally linearly independent. Then, for 0 < < s
and 0 < p 1,
jf jB Cn=dkf kLp for all f 2 e n ();
where C is a constant depending only on and p when p is small.
We remark that the above result was proved in [21] for nitely generated shift invariant
spaces. The following result now follows from Theorems G, F and A.
Theorem H. Let 2 W1s (Rd), s 2 N, be a compactly supported function satisfying (8.1)(8.3). Also, let 0 < p < 1 and 0 < < minfr; sg. Then, for 0 < < =d and 0 < q 1,
we have
Aq (Lp; fe n()gn2N) = (Lp; B )d=;q :
Thus, in particular, for q = = ( + 1=p),1 we have
A (Lp; fe n()gn2N) = (Lp; B )d=; = B d :
From Corollaries 8, 16 and Theorem H we obtain the following.
Corollary 18. Let 2 W1s (Rd), s 2 N, be a compactly supported function satisfying (8.1)(8.3) (i.e., is a renable function having locally linearly independent shifts and satisfying
the Strang-Fix conditions of order r). Also, let 0 < < p < 1, = 1= , 1=p, and
< minf dr ; ds ; (d,11)p g. Then, for 0 < < and 0 < q 1,
,
Aq (Lp; fn;r gn2N) = Aq (Lp; fe n()gn2N) = Lp; B d
In particular, for q = = ( + 1=p),1 we have
,
A (Lp; fn;r gn2N) = A (Lp; fe n()gn2N) = Lp; B d
,
r
=;q = Lp ; V;p
=;
,
= Lp; V;pr
=;q :
=;
= B d :
We now restate this corollary in somewhat more standard and easier to use form (we
choose = d and = d ).
22
Corollary 180. Let 2 W1s (Rd), s 2 N, be a compactly supported function satisfying (8.1)(8.3) (i.e., is a renable function having locally linearly independent shifts and satisfying
the Strang-Fix conditions of order r). Also, let 0 < < p < 1, 1= = =d + 1=p, and
< minfr; s; (d,d1)p g. Then for 0 < < and 0 < q 1,
,
=d
e n()gn2N) = (Lp; B )=;q = Lp; V;pr
A=d
q (Lp ; fn;r gn2N) = Aq (Lp ; f
In particular, for q = = (=d + 1=p),1 we have
,
=d
e n()gn2N) = Lp; V;pr
A=d
(Lp ; fn;r gn2N) = A (Lp ; f
In other words,
=;
=;q :
= (Lp; B )=; = B :
1 X
n=dE (f; n;r )Lp n1 < 1
n=1
1 h
i
X
()
n=dE (f; e n())Lp n1 < 1
Zn=11 r ) dt < 1
()
t,=K (f; t; Lp; V;p
t
Z0 1 ()
t,=dWr (f; t);p dtt < 1:
f 2 B ()
0
The inequality < (d,d1)p is sharp and cannot be removed. The reason for this is
r )
that spaces (Lp; V;p
=; contain certain piecewise polynomials (though not all of them)
d
if > (d,1)p , and, at the same time, for these the spaces B contain no characteristic
functions (see the next section for more details). We also note that this somewhat anomalous
situation does not exist in the univariate case (see also [15] for discussions).
8.1 Remarks
Lemma 19. Let r 2 N, 0 < < r, and 1= = =d + 1=p. Then, for f 2 B ,
(8.4)
jf jV;pr C jf jB:
Proof. For any partition fRi gi2 2 r using Lemma 1, Corollary 2 and (7.2) we have
X
i2
!r (f; len(Ri ); Ri)p
C
X
i2
Ef (Ri)p
C
Ri
XX
i2 =1
jf jB(rRi ) C jf jB :
Therefore, taking sup over all partitions in r we obtain (8.4).
The inequality (8.4) immediately implies that
r ) CK (f; t; L ; B );
K (f; t; Lp; V;p
p
23
hence,
,
r
(Lp; B );q Lp ; V;p
;q
for 0 < < 1 and 0 q 1. In particular, for 0 < < and q = = (=d + 1=p),1 ,
,
r
(Lp; B )=; = B Lp ; V;p
=; :
The proof of the following lemma is rather straightforward and will be omitted.
Lemma I. Let Q [0; 1)d be a cube, and let aQ(x) := pr (x)Q(x) (i.e., aQ is a piecewise
polynomial function on [0; 1)d ). Then
aQ 2 Bq(L )
()
< 1;
if 0 < q < 1
1; if q = 1:
In particular, for 0 < p < 1,
aQ 2 B () < (d ,d 1)p :
r contains some piecewise polynomial functions (for example,
Obviously, the space V;p
[0;1=2)d(x)). In fact, it contains all piecewise polynomial functions on dyadic ring partitions.
Thus, it follows from Lemmas 19 and I that, if 1= = =d + 1=p and (d,d1)p , then
r :
B ( V;p
Also, if > (d,d1)p , 1= = =d + 1=p,
(8.5)
d
(d,1)p
,
< and = (=d + 1=p),1 , then
e n()gn2N) = B ( Lp; V;pr
A=d
(Lp ; f
(This, in particular, shows that the condition <
cannot be removed.)
Thus, on one hand, we know that
=;
d
= A=d
(Lp ; fn;r gn2N) :
(d,1)p
in Corollary 18(180 ) is sharp and
e n()gn2N) A=d
A=d
(Lp ; f
(Lp ; fn;r gn2N) ;
which means that the error of approximation from the manifold fn;r gn2N is not worse than
the error of approximation from fe n ()gn2N. On the other hand, the error of approximation
by elements of fn;r gn2N can be essentially better (smaller) than the error of approximation
by elements of fe n ()gn2N since, in the case q = , there exist functions (for example,
characteristic functions of dyadic rings and their liner combinations) such that
1 h
X
n=1
e n())Lp i 1 = 1
n=dE (f; n
and
24
1 X
n=1
n=dE (f; n;r )Lp n1 < 1 :
Acknowledgement
The authors are indebted to Ron DeVore for inspirational discussions during their visit to
the University of South Carolina which motivated this work. We are also grateful to him
and Albert Cohen for their input on the rst draft of this paper, and for providing us with
copies of the manuscript [7].
References
[1] C. Bennett and R. Sharpley, Interpolation of Operators, Academic Press, New York,
1988.
[2] J. Bergh and J. Peetre, On the space Vp (0 < p 1), Bolletino Un. Mat. Ital., 4,
632{648 (1974).
[3] M. S. Birman and M. Z. Solomjak, Piecewise-polynomial approximations of functions of
the classes Wp, Math. USSR{Sb., 2, 295{317 (1967).
[4] Yu. Brudnyi, Spline approximation and functions of bounded variation, Dokl. Akad.
Nauk SSSR, 215, 518{521 (1974).
[5] Yu. A. Brudnyi, A multidimensional analog of a theorem of Whitney, Mat. Sbornik, 82
(124), 157{170 (1970).
[6] H. G. Burchard and D. F. Hale, Piecewise polynomial approximation on optimal meshes,
JAT, 14, 128{147 (1975).
[7] A. Cohen, R. DeVore, P. Petrushev and H. Xu, Nonlinear approximation and the space
BV (R2) (preprint).
[8] R. A. DeVore, A note on adaptive approximation, Approx. Theory Appl., 3:4, 74{78
(1987).
[9] R. A. DeVore, Degree of nonlinear approximation, Approx. Theory VI, C. K. Chui,
L. L. Schumaker and J. D.Ward (eds.), 175{201 (1989).
[10] R. A. DeVore, R. Howard and C. A. Micchelli, Optimal nonlinear approximation, Manus.
Math., 63, 469{478 (1989).
[11] R. A. DeVore, B. Jawerth and V. A. Popov, Compression of wavelet decompositions,
Amer. J. Math., 114, 737{785 (1992).
[12] R. A. DeVore, G. Kyriazis, D. Leviatan and V. M. Tikhomirov, Wavelet compression
and nonlinear n-widths, Advances in Comp. Math., 1, 197{214 (1993).
[13] R. A. DeVore and G. G. Lorentz, Constructive Approximation, Berlin: Springer-Verlag,
1993.
25
[14] R. A. DeVore, P. Petrushev and X. M. Yu, Wavelet approximation in the space C (Rd),
in: Progress in Approximation Theory, ed. A. A. Gonchar and E. Sa (Springer, New
York, 1992), 261{283.
[15] R. A. DeVore and V. A. Popov, Free multivariate splines, CA, 3, 239{248 (1987).
[16] R. A. DeVore and V. A. Popov, Interpolation of Besov spaces, Trans. AMS, 305, 397{
414 (1988).
[17] R. A. DeVore and V. A. Popov, Interpolation spaces and nonlinear approximation, in:
Functions Spaces and Approximation, ed. M. Cwikel, J. Peetre, Y. Sagher, and H.
Wallin (Lecture Notes in Mathematics, Springer, New York/Berlin, 1988), 191{205.
[18] R. A. DeVore and R. C. Sharpley, Besov spaces on domains in Rd, Trans. AMS, 335(2),
843{864 (1993).
[19] R. A. DeVore and X. M. Yu, K -functional for Besov spaces, JAT, 67, 38{50 (1991).
[20] Z. Ditzian, Polynomial approximation in Lp(S ) for p > 0, CA, 12, 241{269 (1996).
[21] R.-Q. Jia, A Bernstein-type inequality associated with wavelet decomposition, CA, 9,
299{318 (1993).
[22] P. Oswald, On the degree of nonlinear spline approximation in Besov-Sobolev spaces,
JAT, 61, 131{157 (1990).
[23] A. Pekarskii, Estimates of the derivatives of rational functions in Lp[1; ,1], Mat. Zametki 39 (1986), 388-394 (English translation in Math. Notes, 39 (1986), 212-216).
[24] P. Petrushev, Direct and converse theorems for spline and rational approximation and
Besov spaces, in: Functions Spaces and Approximation, ed. M. Cwikel, J. Peetre, Y.
Sagher, and H. Wallin (Lecture Notes in Mathematics, Springer, New York/Berlin,
1988), 363{377.
26
© Copyright 2024 ExpyDoc
