Greedy approximation with regard to non-greedy bases
- PDF / 381,934 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 59 Downloads / 207 Views
Greedy approximation with regard to non-greedy bases V. N. Temlyakov · Mingrui Yang · Peixin Ye
Received: 23 September 2009 / Accepted: 15 April 2010 / Published online: 8 June 2010 © Springer Science+Business Media, LLC 2010
Abstract The main goal of this paper is to understand which properties of a basis are important for certain direct and inverse theorems in nonlinear approximation. We study greedy approximation with regard to bases with different properties. We consider bases that are tensor products of univariate greedy bases. Some results known for unconditional bases are extended to the case of quasi-greedy bases. Keywords Greedy algorithm · m-term approximation · Greedy basis · Quasi-greedy basis Mathematics Subject Classifications (2010) 41A25 · 41A46 · 41A63
Communicated by Qiyu Sun. The research of P. Ye was supported by the Natural Science Foundation of China (Grant No. 10971251). V. N. Temlyakov · M. Yang (B) Department of Mathematics, University of South Carolina, Columbia, SC 29208, USA e-mail: [email protected] V. N. Temlyakov e-mail: [email protected] P. Ye School of Mathematical Sciences and LPMC, Nankai University, Tianjin, 300071, China e-mail: [email protected]
320
V.N. Temlyakov et al.
1 Introduction We study the efficiency of greedy algorithms for m-term nonlinear approximations with regard to bases. Let X be an infinite-dimensional separable Banach space with a norm · := · X and let := {ψn }∞ n=1 be a normalized basis for X (ψn = 1, n ∈ N). All bases considered in our paper are assumed to be normalized. For a given f ∈ X we define the best m-term approximation with regard to as follows: bk ψk , σm ( f, ) X := inf f − bk , k∈
X
where the inf is taken over coefficients bk and sets of indices with cardinality || = m. There is a natural algorithm of constructing an m-term approximant. For a given element f ∈ X we consider the expansion f =
∞
ck ( f, )ψk .
k=1
We call a permutation ρ, ρ( j) = kj, j = 1, 2, ..., of the positive integers decreasing and write ρ ∈ D( f ) if |ck1 ( f, )| ≥ |ck2 ( f, )| ≥ ... . In the case of strict inequalities here D( f ) consists of only one permutation. We define the m-th greedy approximant of f with regard to the basis corresponding to a permutation ρ ∈ D( f ) by formula X Gm ( f ) := Gm ( f, ) := Gm ( f, ) := Gm ( f, , ρ) :=
m
ckj ( f, )ψkj .
j=1
This algorithm is known in the theory of nonlinear approximation under the name of Thresholding Greedy Algorithm (TGA). The best we can achieve with the algorithm Gm is f − Gm ( f, ) X = σm ( f, ) X , or a little weaker f − Gm ( f, ) X ≤ Cσm ( f, ) X
(1)
for all f ∈ X with a constant C independent of f and m. Bases satisfying (1) are of special interest in nonlinear approximation. The following concept of a greedy basis has been introduced in [6]. Definition 1 We call a basis a greedy basis if for every f ∈ X there exists a permutation ρ ∈ D( f ) such that f − Gm ( f, ) ≤ Cσm ( f, ) X with a constant C independent of f and m.
Data Loading...
