Simultaneous approximation by greedy algorithms
- PDF / 287,659 Bytes
- 18 Pages / 595 x 842 pts (A4) Page_size
- 67 Downloads / 205 Views
Springer 2006
Simultaneous approximation by greedy algorithms D. Leviatan a, and V.N. Temlyakov b, a School of Mathematical Sciences, Sackler Faculty of Exact Sciences, Tel Aviv University,
Tel Aviv 69978, Israel E-mail: [email protected] b Department of Mathematics, University of South Carolina, Columbia, SC 29208, USA E-mail: [email protected]
Received 12 February 2003; accepted 16 September 2003 Communicated by Yuesheng Xu
Dedicated to our colleague and friend Dr. Charles Micchelli on his 60th birthday We study nonlinear m-term approximation with regard to a redundant dictionary D in a Hilbert space H . It is known that the Pure Greedy Algorithm (or, more generally, the Weak Greedy Algorithm) provides for each f ∈ H and any dictionary D an expansion into a series f =
∞
cj (f )ϕj (f ),
ϕj (f ) ∈ D, j = 1, 2, . . . ,
j =1
2 with the Parseval property: f 2 = j |cj (f )| . Following the paper of A. Lutoborski and the second author we study analogs of the above expansions for a given finite number of functions f 1 , . . . , f N with a requirement that the dictionary elements ϕj of these expansions are the same for all f i , i = 1, . . . , N . We study convergence and rate of convergence of such expansions which we call simultaneous expansions. Keywords: greedy algorithms, convergence, simultaneous approximation. Mathematics subject classifications (2000): primary 41A65; secondary 41A25, 41A46, 46B20.
1.
Introduction
In this paper we study nonlinear approximation. The basic idea behind nonlinear approximation is that the elements used in the approximation do not come from a fixed linear space but are allowed to depend on the function being approximated. The classical Part of this work was done while the first author visited the University of South Carolina in January
2003.
This research was supported by the National Science Foundation Grant DMS 0200187 and by ONR
Grant N00014-96-1-1003.
74
D. Leviatan, V.N. Temlyakov / Simultaneous approximation by greedy algorithms
problem in this regard is the problem of m-term approximation where one fixes a basis in the space, and seeks to approximate a target function f by a linear combination of m terms from that basis. When the basis is a wavelet basis or a basis of other waveforms, then this type of approximation is the starting point for compression algorithms. An important feature of approximation using a basis := {ψk }∞ k=1 of a Banach space X is that each function f ∈ X has a unique representation f =
∞
ck (f )ψk
(1.1)
k=1
and we can identify f with the set of its coefficients {ck (f )}∞ k=1 . The problem of m-term approximation with regard to a basis has been studied thoroughly and rather complete results have been established (see [2, 4–6, 9–11, 15, 19–23, 25–27, 31, 34–37, 42, 43]). In particular, it was established that the greedy type algorithm which forms a sum of m terms with the largest ck (f )ψk X out of expansion (1.1), in many cases almost realizes the best m-term approximation for function classes ([5]), and e
Data Loading...
