Localization of frames II

Appl. Comput. Harmon. Anal. 17 (2004) 29–47 www.elsevier.com/locate/acha Localization of frames II Elena Cordero a and Karlheinz Gröchenig b,∗ a Department of Mathematics, University of Torino, Italy b Institute of Biomathematics and Biometry, GSF—National Research Center for Environment and Health, Ingolstädter Landstrasse 1, D-85764 Neuherberg, Germany Received 26 October 2003; revised 12 February 2004; accepted 12 February 2004 Available online 25 May 2004 Communicated by Joachim Stöckler, Guest Editor Abstract The theory of localized frames is refined to include quasi-Banach spaces and spaces with multiple generators. Applications are given to nonlinear approximation with frames and to the convergence of the iterative frame algorithm in finer norms, and to the characterization of Besov spaces with wavelet frames.  2004 Elsevier Inc. All rights reserved. Keywords: Frame; Banach frame; Frame algorithm; Quasi-Banach space; Jaffard’s lemma; Nonlinear approximation; Shift-invariant spaces with multiple generators; Wavelet frames; Besov spaces MSC: 42C15; 46E99; 46B15; 47B37; 41A63; 94A12 1. Introduction The rise of frame theory in applied mathematics is due to the flexibility and redundancy of frames. Structured frames are much easier to construct than structured orthonormal bases. Redundancy is useful in the case of lossy data, often provides more numerical stability, and plays a pivot role in the spectacular applications of Σ∆-quantization [12]. The concept of frames was introduced by Duffin and Schaeffer [15] and popularized greatly by the work of Daubechies and her coauthors [7–10]. For up-todate treatments of frames one may consult the monographs [4,5,30] or the special issue [2]. Although the frame concept is a pure Hilbert space concept, it was recognized early on that the usefulness of frames goes far beyond Hilbert space theory. For instance, wavelet frames are used to detect smoothness * Corresponding author. E-mail addresses: [email protected] (E. Cordero), [email protected] (K. Gröchenig). 1063-5203/$ – see front matter  2004 Elsevier Inc. All rights reserved. doi:10.1016/j.acha.2004.02.002 30 E. Cordero, K. Gröchenig / Appl. Comput. Harmon. Anal. 17 (2004) 29–47 and compression properties of functions, Gabor frames characterize the time-frequency concentration of distributions, and frames of reproducing kernels yield sampling theorems in function spaces. In all these applications, the frames satisfy some additional hypotheses: the wavelet of a wavelet frame must satisfy smoothness and moment conditions, whereas the Haar wavelet is not appropriate; a Gaussian window works very well for Gabor frames, whereas a rectangular Gabor window does not capture frequency concentration. While in these concrete examples it is well understood what constitutes a “good frame,” it is not obvious how to formulate appropriate conditions for arbitrary frames. The preceding paper [28] is an attempt to understand “good frames.” In our opinion, the relevant property to distinguish “good frames” among arbitrary frames is a new form of localization for frames. The main result of [28] asserts that the localization properties of a frame are inherited by its dual frame. For “good frames” in this sense, we show that a class of associated Banach spaces can be characterized completely by the magnitude of the frame coefficients and that the frame expansion is stable in these Banach spaces. The examples considered in [28] are the sampling theory in shift-invariant spaces and Gabor frames. Frames of reproducing kernels in shift-invariant spaces can be shown to be “local” and lead to local reconstruction formulas. Likewise, Gabor frames with suitable time-frequency localization possess a dual frame with the same time-frequency localization, and as a consequence the time-frequency concentration of distributions can be characterized using Gabor frames. These examples settled two conjectures about sampling and about Gabor frames in the literature. Another application of localized frames was given in [27] where a conjecture of Feichtinger was partially solved. The circulation of the preprint [28] has stimulated a number of further investigations: in [6] precise error estimates are derived for the finite section method, these work exactly for localized frames, in [16] an equivalence relation of localized frames and applications to α-modulation spaces are studied. Independently and in a completely different direction, Balan, Casazza, Heil, and Landau [3] have introduced a similar concept of localization to define the density of an abstract frame. Based on their theory of localization, they prove deep inequalities relating this density to the excess of frames. In this paper we study several new facets of localized frames and answer several questions that came up in discussions of localized frames. While our methods are mostly standard, we use Banach algebra techniques for some decisive arguments. Our results owe their depth to a highly nontrivial theorem of Jaffard and Journé [31]. Specifically, we will extend the characterization of functional properties by means of frames to certain quasi-Banach spaces. Quasi-Banach spaces have made a comeback through the rise of nonlinear approximation theory. We will show that localized frames yield sparse representations for the associated classes of quasi-Banach spaces. Next we will investigate the convergence of the iterative frame algorithm of Duffin and Schaeffer (and some of its accelerations) in the norm of the associated Banach spaces. Sometimes, in particular for frames without structure, the iterative frame algorithm is still preferred to more sophisticated methods, because it does not require any knowledge of the dual frame. We show that the iterative frame algorithm converges automatically in much finer norms. Our result shows that localized frames possess a surprising robustness in their numerical performance. To say it more flamboyantly, localized frames are “good frames” for numerical analysis. As an example we will treat the sampling problem in shift-invariant spaces with multiple generators. This requires the study of frames that are localized with respect to Riesz basis with additional structure. In the final example we will characterize certain Besov spaces by localized wavelet frames. This E. Cordero, K. Gröchenig / Appl. Comput. Harmon. Anal. 17 (2004) 29–47 31 characterization is remarkable in that we do not need any a priori assumptions on the dual frame. (A more extensive treatment of wavelet frames will be carried out elsewhere.) The results presented here could be summarized by saying that localized frames are indeed “good frames.” We hope that this concept will have many more applications and motivate further results. The paper is organized as follows: In Section 2 we introduce the concept of localized frames and discuss the associated (quasi)-Banach spaces. In Section 3 we derive frame expansions and characterizations for the quasi-Banach spaces with parameter p < 1. Section 4 is devoted to nonlinear approximation with frames and shows that the associated Banach spaces possess sparse representations with respect to localized frames. In Section 5 we investigate the convergence of the iterative frame algorithm. In Section 6 we adjust the concept of localization to deal with shift-invariant spaces with multiple generators. Finally, in Section 7 we apply localized wavelet frames for a characterization of certain Besov spaces. 2. Localization of frames and associated Banach spaces We first review the new concept of localization for frames and summarize the main results from [28]. Throughout the paper E = {ex : x ∈
X } denotes a frame for a given Hilbert space H; this means that the frame operator Sf = SE f = x∈X f, ex ex is bounded and boundedly invertible on H. The set {gn : n ∈ N } is always a Riesz basis for H with dual basis {gn : n ∈ N }. The set N is assumed to be separated in Rd , i.e., infx,y∈N : x=y |x − y|
δ > 0, and X is relatively separated in Rd , i.e., X is a finite union of separated sets. We should think of the index as a kind of localization. For instance, if H = L2 (Rd ), then the index x in ex (t) indicates that the essential support of ex is centered at x. 2.1. Localized frames Definition 1. A frame E = {ex : x ∈ X } for a Hilbert space H is called polynomially localized with respect to the Riesz basis {gn } with decay s > 0 (or simply s-localized) if     ex , gn   C 1 + |x − n| −s (1) and     ex , gn   C 1 + |x − n| −s (2) for all n ∈ N and x ∈ X . Similarly, a frame E = {ex : x ∈ X } for H is called exponentially localized with respect to the Riesz basis {gn } if for some α > 0     max ex , gn , ex , gn   Ce−α|x−n| ∀x ∈ X , n ∈ N . (3) The main theorem in the theory of localized frames asserts that the dual frame E = { ex := S −1 ex : x ∈ X } possesses the same localization properties. In the following d is the dimension of the “carrier” space Rd for N and X . Theorem 2.1. (a) If E is s-localized with respect to the Riesz basis {gn } for some s > d, then E is also s-localized. (b) If E is exponentially localized, then E is also exponentially localized (with a possibly different exponent in (3)). 32 E. Cordero, K. Gröchenig / Appl. Comput. Harmon. Anal. 17 (2004) 29–47 To give the reader an idea what is involved in this statement, we sketch a short proof for polynomially localized frames. The precise details can be found in [28]. Proof. The proof is based on two important facts from the theory of Banach algebras. Let As be the class of N × N -matrices A = (akl ) such that  −s |akl |  C 1 + |k − l| for all k, l ∈ N . (4) Jaffard [31] proved the following properties: (a) If s > d, then As is an algebra (under matrix multiplication). (b) If A ∈ As for s > d and if A is invertible on ℓ2 (N ), then A−1 ∈ As . See [31], also [29] for a new proof and refinements. Step 1. Let (Γf )(n) = f, gn . Since of H, Γ is an isomorphism from H
{gn : k ∈ N } is a Riesz basis 2 −1 2 onto ℓ (N ) with inverse Γ c = k∈N cn gn for c = (cn ) ∈ ℓ (N ). Then the frame operator S can be factored as S = Γ −1 T Γ, (5) where T is the matrix of S with respect to the given Riesz basis. It has the entries  Tkl = Sgl , gk  = gl , ex ex , gk , k, l ∈ N . x∈X It follows that T is invertible on ℓ2 (N ) if and only if S is invertible on H. Step 2. Let bkl = maxx∈X ∩(k+[0,1]d ) |ex , gl | and ckl = maxx∈X ∩(k+[0,1]d ) |ex , gl | for k, l ∈ N . The slocalization of E implies that B, C
∈ As . Since X is relatively separated, supk∈N card{x ∈ X : x ∈ k + [0, 1]d } = ν < ∞ and therefore x∈X ∩(k+[0,1]d ) |ex , gl |  νbkl and similarly for C. Step 3. We estimate the entries of T :      gl , ex ex , gk   ν 2 |Tkl |  bml cmk = ν 2 (C ∗ B)kl . m∈N x∈X ∩(m+[0,1]d ) m∈N Since B, C and C ∗ are all in the algebra As , we find that T ∈ As as well, explicitly, |Tkl |  C(1 + |k − l|)−s , k, l ∈ N . Step 4. Since T ∈ As and T is invertible on ℓ2 (N ) by Step 1, Jaffard’s lemma implies that T −1 ∈ As . Let U be the matrix with entries ukl = |(T −1 )kl |, then also U ∈ As . Step 5. To show that E is s-localized, we must check the size of S −1 ex , gl  and S −1 ex , gn . Using (5) in the form Γ S −1 = T −1 Γ , we obtain that  −1    S ex , gl  = (Γ S −1 ex )(l)  ckl = max max x∈X ∩(k+[0,1]d ) x∈X ∩(k+[0,1]d )    −1    −1 (T Γ ex )(l) =  = max max (T )lm ex , gm   x∈X ∩(k+[0,1]d ) x∈X ∩(k+[0,1]d ) m∈N        ulm max ex , gm  = ulm ckm = (CU ∗ )kl . m∈N x∈X ∩(k+[0,1]d ) m∈N E. Cordero, K. Gröchenig / Appl. Comput. Harmon. Anal. 17 (2004) 29–47 33  = (c̃kl ) ∈ As . Since C, U ∈ As and As is an algebra, we find that C Step 6. To obtain the estimate for S −1 ex , gl , we interchange the role of gn and g˜n . Precisely, define Γf (n) = f, gn  and Tkl = S gl , gk , then S = Γ−1 TΓ. The same argument as above shows that the matrix B̃ with entries b̃kl = maxx∈X ∩(k+[0,1]d ) |S −1 ex , gl | is also in As . This means that E is slocalized. ✷ For applications, including the solution of two conjectures in sampling theory and Gabor theory, the reader should consult [28]; for a refinement of Theorem 2.1 to other decay conditions see [29]. 2.2. Associated Banach spaces p Let m be a positive, even, and continuous function on Rd and ℓm (X ) the corresponding weighted ℓp -space defined by the norm 1/p  , (6) c ℓpm = |cx |p m(x)p x∈X with the usual modification for p = ∞. p p Definition 2. Let 0 < p  ∞. If ℓm (N ) ⊆ ℓ2 (N ), then the Banach space Hm is defined to be  p = f ∈ H: f = Hm cn gn for c ∈ ℓpm (N ) (7) n∈N p p with norm f Hpm = c ℓpm . If ℓm
ℓ2 (N ) and p < ∞, then
Hm is defined as the completion of the subspace H0 of finite linear combinations, i.e., H0 = {f = n∈N cn gn : supp c finite}, with respect to the ∗ 2 ∞ norm f Hpm = c ℓpm . If p = ∞ and ℓ∞ m
ℓ , then Hm is weak completion of H0 . Remark 1. (1) Note that cn is uniquely determined, in fact, cn = f, gn  or c = Γf . p p (2) If ℓm (N ) ⊆ ℓ2 (N ), then Hm is a (dense) subspace of H. To make the analysis of the associated spaces accessible to harmonic analysis methods, we will only use two types of weights: A nonnegative, continuous, and even function m on Rd is called an s-moderate weight if there are constants C, s
0 such that  s m(t + x)  C 1 + |t| m(x) for all t, x ∈ Rd . (8) A weight function m is called subexponential if there are constants C, γ > 0 and 0  β < 1 such that β m(t + x)  Ceγ |t | m(x) for all t, x ∈ Rd . (9) By setting x = 0 in (8) and in (9) we see that an s-moderate weight m grows at most polynomially, i.e., β m(t)  C(1 + |t|)s , and a subexponential weight grows at most like Ceγ |t | . 2.3. Frame analysis of the associated Banach spaces A thorough analysis of the coefficient map and synthesis operator that are associated with every frame p leads to a complete understanding of the Banach spaces Hm by means of their frame coefficients [28]. 34 E. Cordero, K. Gröchenig / Appl. Comput. Harmon. Anal. 17 (2004) 29–47 Theorem 2.2. Assume that E = {ex : x ∈ X } is an r-localized frame with respect to the Riesz basis {gn } and that r > s + d. p (a) Then the frame operator S is invertible simultaneously on all Banach spaces Hm , where 1  p  ∞ and m is an s-moderate weight. (b) The frame expansion   f= f, ex  ex = f, ex ex (10) x∈X x∈X p ∞ ). converges unconditionally in Hm for 1  p < ∞ (and weak∗ unconditionally in Hm (c) We have the norm equivalence 1/p 1/p     f, ex p m(x)p f, ex p m(x)p . ≍ f Hpm ≍ x∈X (11) x∈X If E is exponentially localized, (a)–(c) hold simultaneously for the larger class of all subexponential weights. p 3. Frame analysis of the quasi-Banach spaces Hm , 0 < p < 1 p In this section we extend Theorem 2.2 to the quasi-Banach space Hm , p < 1. The extension of Theorem 2.2 to the case of quasi-Banach spaces is necessary for several concrete reasons: (a) In approximation theory the parameter p describes the “sparsity” of a representation, and there is no reason to limit the sparsity to p
1, when higher sparsity (corresponding to smaller p) is of practical interest. (b) In the theory of Besov spaces as well as in other families of function spaces it is unnatural to restrict to the Banach space case. The complete results should be formulated for the full range of parameters. To extend Theorem 2.2 to p < 1, we need to analyze the boundedness of the coefficient and reconstruction operators for the frame
E. Let Cf = CE f = (f, ex )x∈X be the coefficient operator associated to E, and Rc = RE c = x∈X cx ex for c = (cx )x∈X be the reconstruction operator. Then p S = SE = RE CE . To prove a version of Theorem 2.2 for Hm , p < 1, we have to show that both C and R are well-defined in the quasi-Banach space case. Although formally we have R = C ∗ , we have to prove the boundedness of R and C separately, because duality arguments do no longer work for p < 1. The first lemma is an extension of [28, Lemma 3] to the case 0 < p < 1. If N = X = Zd , the following p p lemma coincides with Young’s theorem ℓm ∗ ℓpv ֒→ ℓm for 0 < p  1. Lemma 3.1. Let A = (Axn ), x ∈ X , n ∈ N be an X × N -matrix with associated operator (Ac)(x) =
n∈N Axn cn , and let 0 < p  1 and ǫ > 0. p p (a) If |Axn |  C(1 + |x − n|)−s−(d+ǫ)/p , ∀n ∈ N , x ∈ X , then A is bounded from ℓm (N ) to ℓm(X ) for all s-moderate weights m. p p (b) If |Axn |  Ce−α|x−n| , x ∈ X , n ∈ N , then A maps ℓm (N ) to ℓm (X ) for all subexponential weights m.

Proof. (a) Since | x∈X cx |p  x∈X |cx |p for 0 < p  1, we can argue as in [28, Lemma 2.1], namely,  p    p  Ac ℓp (X ) = Axn cn  m(x)p  m x∈X n∈N 35 E. Cordero, K. Gröchenig / Appl. Comput. Harmon. Anal. 17 (2004) 29–47   −sp−(d+ǫ) p 1 + |x − n| |cn | m(x)p C x∈X n∈N  C sup n∈N × =C ′  x∈X    −sp −(d+ǫ)  m(n)−p m(x)p sup 1 + |x − n| 1 + |x − n| x∈X , n∈N |cn |p m(n)p n∈N p c ℓp (N ) . m (12) Since X is relatively separated, the first supremum occurring in (12) is finite (see also [28, Lemma 2.1]), the second supremum is finite because of m(x − n + n)p  C(1 + |x − n|)ps m(n)p for all x, n ∈ Rd . (b) is shown similarly and left to the reader. ✷ We now show that the frame operator of localized frames is well behaved on the quasi-Banach spaces 0 < p < 1. For polynomial localization the results hold only above a critical index p0 , whereas for exponential localization there is no restriction on p. p Hm , Proposition 3.2. Assume that E is an r-localized frame for some r > s + d. Let p0 be the critical index d < 1. If p0 < p  ∞ and m is an s-moderate weight, then p0 = r−s p p (a) the coefficient operator CE is bounded from Hm to ℓm (X ), p p (b) the synthesis operator RE extends to a bounded mapping from ℓm (X ) to Hm , and p p (c) the frame operator S = SE = DE CE maps Hm into Hm , and the series converges unconditionally for p0 < p < ∞. If E is an exponentially localized frame, then these statements hold for all subexponential weights and all p, 0 < p  ∞. Proof. We prove these statements for polynomially localized frames and leave the simple modifications for exponentially localized frames to the reader. The case p
1 is already contained in [28], so we may assume p  1.
(a) Set Axn = gn , ex . If f = n∈N cn gn , then         (Cf )(x) = f, ex  =  cn gn , ex  = (Ac)(x). (13)  n∈N p By hypothesis, |Axn |  C(1 + |x − n|)−r , so Lemma 3.1(a) implies that A is bounded on ℓm (N ), provided d = p0 . Consequently, that r > s + pd or p > r−s CE f p ℓm (X ) = Ac p ℓm (N )  C′ c p ℓm (N ) = C′ f (b) Set bnx = ex , gn . We need to show that for   (Rc)(n) = cx ex , g˜n = (Bc)(n) Hpm . p c ∈ ℓm (X ) the sequence with entries x∈X is in p ℓm (N ). As above this follows from the hypothesis and Lemma 3.1(a) (with X and N interchanged). 36 E. Cordero, K. Gröchenig / Appl. Comput. Harmon. Anal. 17 (2004) 29–47 (c) follows by combining (a) and (b). As for the unconditional convergence of the series defining S, let ǫ > 0 and choose N0 = N0 (ǫ), such that f, ex x ∈/ N0 ℓpm  ǫ. Then for any finite set N1 ⊇ N0 , assertions (a) and (b) imply that        Sf −   f, ex ex     RE op f, ex x ∈/ N1 ℓp < RE op ǫ. This means that m p Hm x∈N1
p converges unconditionally in Hm . x∈X f, ex ex ✷ We can now formulate the main result about the frame characterization for the quasi-Banach spaces p < 1. p Hm , Theorem 3.3. Assume that E = {ex : x ∈ X } is an r-localized frame with respect to the Riesz basis {gn } d < 1. and that r > s + d. Set p0 = r−s p (a) Then the frame operator S is invertible simultaneously on all quasi-Banach spaces Hm , where p0 < p  ∞ and m is an s-moderate weight. (b) The frame expansion   f= f, ex  ex = f, ex ex (14) x∈X x∈X p ∞ converges unconditionally in Hm for p0 < p < ∞ (and weak∗ unconditionally in Hm ). (c) We have the norm equivalence f Hpm ≍   f, ex p m(x)p 1/p ≍ x∈X   f, ex p m(x)p 1/p (15) . x∈X If E is an exponentially localized frame, then (a)–(c) hold simultaneously for all subexponential weights and all p, 0 < p  ∞. p Proof. Since S = Γ −1 T Γ by (5) and since by definition Γ is an isometric isomorphism between Hm p p p and ℓm (N ), S is invertible on Hm if and only if T is invertible on ℓm (N ). We have seen in the proof of −1 −1 Theorem 2.1 that T ∈ Ar whenever E is r-localized, therefore T is bounded simultaneously on all p ℓm (N ) for p > p0 and s-moderate weights by Lemma 3.1. This proves (a). p (b) follows from Proposition 3.2, since the identity on Hm factors as I = RECE and both E and E are r-localized and r > s + d/p. (c) This factorization also implies the norm equivalence: Since f = RECE f , we have f Hpm  RE op CE f p ℓm (X )  RE op CE op f Hpm . The second norm equivalence is shown by using the factorization I = RE CE. p ✷ Remark 2. Note that for the treatment of the Banach spaces Hm with s-moderate weights we need d < 1. r-localized frames with r > s + d. Consequently, we have always p0 = r−s 37 E. Cordero, K. Gröchenig / Appl. Comput. Harmon. Anal. 17 (2004) 29–47 4. Nonlinear approximation with localized frames The main question in nonlinear approximation theory is how well elements in a Banach space can be approximated by a given dictionary. Good approximation properties usually yield sparse representations with respect to the given dictionary. See [13,36] for an extended discussion of the state of art of nonlinear approximation. In this brief section we investigate the approximation properties of a localized frame E. More precisely, we consider so-called N -term approximation with respect to E. Definition 3. For a frame E of H we let ΣN = p =  cx ex : F ⊆ X , card F  N x∈F denote the set of all linear combinations consisting of at most N terms. The N -term approximation error in H is defined by σN (f ) = inf p∈ΣN f −p H. The main tool for investigation of N -term approximation is the following lemma of Stechkin [34] and DeVore and Temlyakov [14]. Lemma 4.1. Assume that a1
a2
· · ·
an
· · ·
0, 0 < p < 2, and set α =
2 1/2 ( ∞ . Then there is a constant C = C(p) > 0, such that j =N+1 |aj | ) 1 a C  ∞   α p 1 N σN−1 (a) p  N N=1 1/p 1 p − 1 2 and σN (a) =  C a p. The following theorem shows that localized frames possess the same approximation power as the underlying Riesz basis. In the following we use only the trivial weight m ≡ 1 and write Hp instead p of Hm . Theorem 4.2. Assume that E is s-localized with respect to the Riesz basis {gn : n ∈ N } and that s > d. Set α = p1 − 21 > 0 for p < 2 and p0 = ds < 1. If p0 < p < 2 and f ∈ Hp , then  ∞   N=1 p 1 N α σN−1 (f ) N 1/p C f Hp . In particular, if f ∈ Hp and ds < p < 2, then σN (f ) = O(N −α ). If E is exponentially localized, then (16) holds for all p, 0 < p < 2. (16) 38 E. Cordero, K. Gröchenig / Appl. Comput. Harmon. Anal. 17 (2004) 29–47
Proof. By Theorems 2.2 and 3.3 every f ∈ Hp has the frame expansion f = x∈X f, ex ex with coefficients c = (cx ) := (f, ex )x∈X ∈ ℓp (X ) and c p ≍ f Hp . Let |cx1 |
|cx2 |
|cx3 |
· · ·
0
be a nonincreasing rearrangement of these coefficients and set pN = N j =1 cxj exj ∈ ΣN . Then   ∞ 1/2  ∞       2 = CσN (c). cxj exj   C |cxj | σN (f )  f − pN H =    j =N+1 H j =N+1 Since the characterization (11) of Hp (with trivial weight) holds exactly for ds < p < 2, we find that 1/p ∞ 1/p ∞     1 1 p p C  C ′ c p  C ′′ f Hp N α σN−1 (c) N α σN−1 (f ) N N N=1 N=1 after invoking Lemma 4.1. For exponentially localized frames, (15) and therefore the statement hold for 0 < p < 2. ✷ Remark 3. (1) It is an open problem for which frames the converse of (16) holds. If we use the Riesz basis {gn } as our dictionary, then Lemma 4.1 implies immediately that ∞ 1/p   1 p ≍ f Hp , N α σN (f ) N N=1 see [14]. To prove this equivalence for frames, we would need a Bernstein-type inequality for finite linear combinations of frame elements. However, a recent example of Gribonval and Nielsen [22] shows that the converse inequality in (16) need not be true even for exponentially localized frames and that the approximation space of a localized frame may be strictly larger than the approximation space of the underlying basis. (2) For another interpretation of Theorem 4.2 and a much more general theory of nonlinear approximation the reader should consult the work of Gribonval and Nielsen [20,21]. (3) Note that for polynomial localization, there is a saturation effect in the approximation power, given by p0 = ds < 1, whereas for exponential localization this does not happen. (4) At this time it is not clear how the redundancy affects the properties of N -term approximation. This seems an interesting question in its own right. 5. Convergence of the iterative frame algorithm For a frame with frame bounds A, B > 0, the inverse frame operator can be calculated (at least in principle) by the Neumann series S −1 = α ∞  (I − αS)k (17) k=0 for arbitrary relaxation parameter α < 2/B [15]. This geometric series converges in the operator norm of B(H). It is useful to recast the frame reconstruction as an iterative algorithm as follows: E. Cordero, K. Gröchenig / Appl. Comput. Harmon. Anal. 17 (2004) 29–47 f0 = Sf =  39 f, ex ex , x∈X fn+1 = fn + αS(f − fn ), n
0. (18) Then f = limn→∞ fn is the reconstruction of f from the frame coefficients f, ex . In practice, much more efficient algorithms are used, for instance, conjugate gradient acceleration and/or exploitation of the additional structure of a frame [25,35], but (18) is still the starting point for the analysis of iterative frame algorithms. Therefore an important question is whether this algorithm also converges in other norms. Specifically, p if E is localized, does the series (17) also converge in the norm of the associated Banach spaces Hm ? In the light of Theorem 4.2, this amounts to asking whether the iterative frame algorithm preserves the sparsity of a representation. Using the methods developed for localized frames so far, we can now answer this question affirmatively. Theorem 5.1. If E is r-localized with respect to a Riesz basis for r > s + d, then the Neumann series (17) p p converges in the operator norm of Hm and the iterative algorithm (18) converges in Hm for 1  p  ∞ p and all s-moderate weights m. (If E is exponentially localized, then the convergence is in Hm for all subexponential weights.) Proof. As for Theorem 2.1, the core of this proof is a Banach algebra argument. Step 1. We take up the notation of Section 2. Since Γ defined by (Γf )(n) = f, gn  is an isometric p p isomorphism between Hm and ℓm (N ), and since S = Γ −1 T Γ from (5), the convergence of the series p (17) in the operator norm on Hm is equivalent to the convergence of the series T −1 = α ∞  (I − αT )k (19) k=0 p in the operator norm on ℓm (N ). Step 2. Recall that Ar is the matrix algebra defined by the decay condition (4). Let σℓpm (A) be the p spectrum of the operator A acting on ℓm (N ) and rℓpm (A) = max{|λ|: λ ∈ σℓpm (A)} be the corresponding p spectral radius. If A ∈ Ar and λ ∈ C, then A − λI ∈ Ar is bounded simultaneously on all ℓm for 1  p  ∞ and all s-moderate weights m by Lemma 3.1. Now assume that λ ∈ / σℓ2 (A), i.e., A − λI is invertible on ℓ2 (N ). Then Jaffard’s lemma [31] implies that (A − λI)−1 ∈ Ar and thus (A − λI)−1 is p also bounded on all ℓm , i.e., λ ∈ / σℓpm (A). In conclusion, Jaffard’s lemma implies that σℓpm (A) ⊆ σℓ2 (A), and in particular rℓpm (A)  rℓ2 (A). (20) Step 3. Now we apply (20) to the operator I − αT occurring in (19). The geometric series (19) converges on ℓ2 because I − αT op = rℓ2 (I − αT ) < 1 for α < 2/B. By (20) we also have rℓpm (I − αT ) < 1. This inequality for the spectral radius suffices to guarantee the convergence of (19) in the operator norm p on ℓm . ✷ 40 E. Cordero, K. Gröchenig / Appl. Comput. Harmon. Anal. 17 (2004) 29–47 Remark 4. In our opinion, this statement is of immense practical importance, because the convergence of the frame algorithm (and its accelerations) in different norms expresses a strong form of numerical stability of the frame algorithm. Theorem 5.1 says that for data (f, ex ) in a subspace of ℓ2 (X ) the frame algorithm converges automatically in the correct norm. 6. Localization with respect to Riesz bases with multiple generators In applications of frame theory to shift-invariant spaces with multiple generators and to wavelet theory in higher dimensions, we encounter Riesz bases with structured index sets. In this section we deal with some technical modifications of the general theory and, as an example, we treat the sampling problem in shift-invariant spaces with multiple generators. We will keep the treatment elementary, but it is certainly possible to generalize these results further by using the concept of block bases and a vector-valued version of localization. We assume that the Riesz basis for H is of the form G := {gln : n ∈ N , l = 1, . . . , L} with dual basis {gln , n ∈ N , l = 1, . . . , L}. Thus the index set is N × F where N is a separated set in Rd (usually a subset of Zd ) and F = {1, 2, . . . , L} is a finite set. Then we call a frame E = {ex : x ∈ X } for H s-localized with respect to the Riesz basis G if    −s ∀x ∈ X , n ∈ N , (21) max ex , gln   C 1 + |x − n| l=1,...,L    −s max ex , gln   C 1 + |x − n| ∀x ∈ X , n ∈ N . (22) l=1,...,L Similarly we understand exponential localization. The main Theorem 2.1 and its consequences do not apply directly to this variation of localization. To study localized frames with respect to a multiply generated Riesz basis, we use a trick and some re-indexing and reduce this situation to Theorem 2.1. Let u ∈ Rd , |u| = 1, ǫ > 0. We define the map j : N × F → Rd by j (l, n) = n + ǫlu ∀n ∈ N , l = 1, . . . , L. Since N is separated, we may choose ǫ > 0 small enough, such that j is one-to-one and the new index  := j (N × F ) ⊆ Rd is separated. If m = j (l, n) ∈ N  , we write hm = hj (l,n) := gln . Clearly, the set set N  {hm : m ∈ N } is a Riesz basis for H, in fact, it is the same Riesz basis with relabeled index set. We check the localization with respect to {hm }:       ex , hm  = ex , gln   C 1 + |x − n| −s  −s  −s  s   C ′ 1 + |x − m| . 1 + |x − m|  C max 1 + |ǫlu| l=1,...,L The same estimate works for the dual Riesz basis, thus the frame E is localized with respect to the Riesz  } in the sense of Definition 1. Conversely, localization with respect to the re-indexed basis {hm : m ∈ N Riesz basis {hm} implies localization with respect to the multiply generated Riesz basis {gln }. Thus we can now reformulate the main Theorem 2.1 as follows. 41 E. Cordero, K. Gröchenig / Appl. Comput. Harmon. Anal. 17 (2004) 29–47 Theorem 6.1. If E is s-localized with respect to the Riesz basis {gln : n ∈ N , l = 1, . . . , L} and if s > d, then E is also s-localized. Likewise, if E is exponentially localized, then Eis also exponentially localized (with a possibly different exponent in (3)). 6.1. Localization and sampling theory Let Φ = {φj : j = 1, . . . , L} ⊆ L2 (Rd ) be a set of “generators” satisfying the following properties: (i) The integer translates {φl (· − k): k ∈ Zd , l = 1, . . . , L} form a Riesz basis for the generated subspace in L2 (Rd ). We also say that “Φ is a stable generator.” (ii) Each φl is continuous. (iii) Each φl satisfies the decay condition     φl (x)  C 1 + |x| −r ∀x ∈ Rd , (23) for some r > d. Given 0 < p  ∞ and an s-moderate weight function m, we define the multiply generated shiftp invariant space Vm (Φ) as   L     L cln φl (· − n), c ∈ ℓpm (Zd ) Vmp (Φ) = f ∈ S ′ (Rd ): f = . (24) l=1 n∈Zd p Vm (Φ) p In other words, is the (quasi)-Banach space Hm associated to the multiply generated Riesz p p basis. Moreover, under the conditions stated, Vm (ϕ) is a closed subspace of Lm (Rd ) endowed with the equivalent norms f p Lm ≍ c ℓm . p (25) For the general theory of shift-invariant spaces and sampling theory we refer to [1,11,28] and references therein. Since V 2 (Φ) is shift-invariant, the dual basis is again of the form φ̃l (· − n), l = 1, . . . , L, n ∈ Zd for some φ̃l ∈ V 2 (Φ). The following lemma is implicit in the literature on shift-invariant spaces, but does not seem to be sufficiently known. Here we give a new proof that is based on the theory of localized frames. Lemma 6.2. Under the hypotheses (i)–(iii) on Φ, the dual generators also satisfy the decay conditions     φ l (x)  C 1 + |x| −r ∀x ∈ Rd , l = 1, . . . , L. (26) Proof. Since a Riesz basis is also a frame, we can check the localization of the frame (Riesz basis) {φl (· − n): n ∈ Zd , l = 1, . . . , L} with respect to itself and then apply Theorem 6.1. In the following argument we use the easy estimate   −r  −r  −r ∀x ∈ Rd , (27) 1 + |t| 1 + |x − t| dt  C 1 + |x| Rd which holds whenever r > d (see, for instance, [26, Lemma 11.1.1]). 42 E. Cordero, K. Gröchenig / Appl. Comput. Harmon. Anal. 17 (2004) 29–47 Step 1. We show that E = {φl (· − n), n ∈ Zd , l = 1, . . . , L} is r-localized with respect to itself. We have   φl (· − n), φl ′ (· − m) = δl,l ′ δmn by definition, and    −r  −r  −r   φl (· − n), φl ′ (· − m)   C 1 + |x − n| 1 + |x − m| dt  C ′ 1 + |m − n| Rd by (23) and (27). So E is r-localized with respect to the Riesz basis E. l (· − n)}, which in this case coincides with the Step 2. Theorem 6.1 implies that the dual frame E = {φ dual basis, is also r-localized with respect to E. In particular we have     φ l , φl ′ (· − n)   C 1 + |n| −r for l, l ′ = 1, . . . , L and n ∈ Zd . l with respect to the basis {φl (· − n)}, we obtain the desired decay estimate Step 3. Expanding φ   L        φ l , φl ′ (· − n) φl ′ (x − n) l (x) =  φ  ′ l =1 n∈Zd  −r  −r  −r  C ′ 1 + |x| 1 + |n| 1 + |x − n| C (28) m∈Zd for l = 1, . . . , L, where we have used the discrete version of (27) and (23) once more. ✷ The main localization theorem for sampling in multiply generated shift-invariant spaces now goes as follows. Theorem 6.3. Assume that the generator Φ satisfies the assumptions (i)–(iii) for r > s + d. Let m be an d . Assume that a relatively separated set s-moderate weight function and p0 be the critical index p0 = r−s d X ⊆ R satisfies the sampling inequality   f (x)2  B f 2 ∀f ∈ V 2 (Φ) A f 22  (29) 2 x∈X x satisfying the following properties: for some constants A, B > 0. Then there exist dual functions K x satisfy the estimates (a) Localization: The K     K x (t)  C 1 + |t − x| −r for all x ∈ X , t ∈ Rd , with a constant C independent of x and t. p (b) Local reconstruction: Every f ∈ Hm can be reconstructed by  x f= f (x)K x∈X p with unconditional convergence in Vm (Φ) for p0 = d r−s < p < ∞. (30) (31) E. Cordero, K. Gröchenig / Appl. Comput. Harmon. Anal. 17 (2004) 29–47 43 (c) Norm equivalence: A f p Lm    f (x)p m(x)p 1/p B f p Lm ∀f ∈ Vmp (Φ), p0 < p  ∞. (32) x∈X x (t)|  Ce−β|t −x| for some Remark 5. (1) For exponential localization |φj (x)|  Ce−α|x| we obtain |K β ∈ (0, α). The conclusions of Theorem 6.3 then hold for the full range 0 < p  ∞ and all subexponential weights. (2) Since the precise nature of the functionals f → f (x) does not matter, the theorem also holds for sampling from local averages as in [28]. Proof. Under the assumptions stated on Φ, the Hilbert space V 2 (Φ) is a reproducing kernel Hilbert space, and there exist functions Kx ∈ V 2 (Φ) such that f (x) = f, Kx  [1]. The sampling inequality (29) simply says that {Kx : x ∈ X } is a frame for V 2 (Φ). We check the localization properties of this frame with respect to the given Riesz basis:        Kx , φl (· − n)  = φl (x − n)  C 1 + |x − n| −r for x ∈ X , n ∈ Zd , l = 1, . . . , L. Likewise, with the help of Lemma 6.2 we obtain that      −r  Kx ,  φl (· − n)  =  φl (x − n)  C 1 + |x − n| . This means that Kx is r-localized with respect to the multiply generated Riesz basis {φl (· − n): n ∈ Zd , l = 1, . . . , L}. x satisfies the estimates We can now apply Theorem 2.1 and deduce that the dual frame K     K x , φl (· − n)   C ′ 1 + |x − n| −r

x , φl (· − n)φ̃l (· − n), the claimed x = Ll=1 k∈Zd K and the same for the dual generators φ̃l . Since K decay (30) follows as in (28). The remaining assertions are now just a reformulation of the main Theorems 2.2 and 3.3. ✷ 7. Localized wavelet frames and Besov spaces Finally we deal with the characterization of Besov spaces by means of wavelet frames. While theorems of this type actually precede wavelet theory [17], a suitably formulated version of these results can now be obtained as a simple example of the general theory of localized frames. Wavelet frames are frames for L2 (Rd ) with a translation–dilation structure, i.e., E = {ψj kl (x) = j d/2 2 ψl (2j x − k), j ∈ Z, k ∈ Zd , l = 1, . . . , L}. In this example the obvious type of basis to compare with is an orthonormal wavelet basis, which is again of the form {Ψj kǫ (x) = 2j d/2 Ψǫ (2j x − k), j ∈ Z, k ∈ Zd , ǫ = 1, . . . , 2d − 1}. For convenience we choose a Meyer type basis with wavelets Ψǫ ∈ C ∞ (Rd ) ǫ being compact [32]. It is well known that such wavelet bases are unconditional bases for all with supp Ψ Besov–Triebel–Lizorkin spaces. More precisely, let ℓp,q α be the mixed norm space defined by the norm     d −1 q/p 1/q   2 p j αq p,q |cj kǫ | 2 . c ℓα = j ∈Z k∈Zd ǫ=1 44 E. Cordero, K. Gröchenig / Appl. Comput. Harmon. Anal. 17 (2004) 29–47 Let Hαp,q  = f: f =  (j,k)∈Zd+1 d −1 2 cj kǫ Ψj kǫ , ǫ=1 c ∈ ℓp,q α  . By the be the Banach space associated to the Meyer-type wavelet basis with norm f Hp,q = c ℓp,q α α results in [19,23,32] we have the following identification with the homogeneous Besov spaces: p,q Hαp,q = Ḃα+d/p−d/2. (33) Theorem 7.1. Assume that {ψj kl (x) = 2j d/2 ψl (2j x − k), j ∈ Z, k ∈ Zd , l = 1, . . . , L} is a frame for L2 (Rd ) that satisfies the localization condition     ψj kl , Ψj ′ k′ ǫ   C 1 + |j − j ′ | + |k − k ′ | −s ∀j, j ′ ∈ Z, k, k ′ ∈ Zd , l, ǫ, (34)  for some s > d + 1. Then the dual frame ψ j kl satisfies the same localization conditions     ′ ′ ′ −s ψ   ∀j, j ′ ∈ Z, k, k ′ ∈ Zd , l, ǫ. j kl , Ψj ′ k ′ ǫ   C 1 + |j − j | + |k − k | (35) p,q Moreover, a function f ∈ L2 (Rd ) is in Ḃd/p−d/2 for p0 = d/s < p, q  ∞ if and only if 1/q     p q/p f, ψj kl  < ∞. j ∈Z k∈Zd , l∈F p,q The latter expression is an equivalent (quasi-)norm on Ḃd/p−d/2(Rd ). p,p Furthermore, if f ∈ Ḃd/p−d/2 for p0 = d/s < p < 2 and α = 1/p − 1/2, then 1/p ∞  p 1 α p,p  C f Ḃd/p−d/2 , N σN−1 (f ) N N=1 where σN (f ) is the N -term approximation error of f with respect to the wavelet frame as in Definition 3. Proof. We choose the index sets to be N = Zd+1 × {1, . . . , 2d − 1} and X = Zd+1 (with multiplicity L). For p = q the result is just an explicit formulation of Theorems 2.1, 2.2, 3.3, and 6.1 for wavelet p,p frames and the associated Banach spaces Hp = Ḃd/p−d/2 (with weight m ≡ 1). The result on nonlinear approximation follows from Theorem 4.2. The case p = q requires a simple adaption of Proposition 3.2 to mixed norm spaces. Since the index sets are Zd+1 , this amounts to replacing Lemma 3.1 by Young’s min(1,p,q) ⊆ ℓp,q theorem ℓp,q α in the proof of Proposition 3.2. ✷ α ∗ ℓα Remark 6. (1) Since Theorem 7.1 resembles other results in the literature (compare [17,18,24]), let us point out some of the novelties: no assumption is made on the structure of the dual frame, in particular it is not assumed that the dual frame is again a wavelet frame. Likewise, the frame element ψj kl need not be of the form ψl (2j x − k), any frame satisfying (34) yields the same conclusions. This shows that the characterization of Besov spaces is more about the localization properties of frames than about the exact translation–dilation structure of the frames. Of course, this observation is consistent with the characterization of Besov–Triebel–Lizorkin spaces by molecules [18,38]. E. Cordero, K. Gröchenig / Appl. Comput. Harmon. Anal. 17 (2004) 29–47 45
(2) Condition (34) implies in particular that the wavelet ψ satisfies j,k,ǫ |ψ, Ψj kǫ | < ∞. By (33) 1,1 1,1 we have ψ ∈ Ḃd/2 [32]. Thus the localization properties describe a subspace of Ḃd/2 as the class of admissible wavelets. l ⊆ {x ∈ Rd : 0 < a  |x|  b} and |ψl (x)| = O(|x|−s ), (3) Condition (34) is satisfied when supp ψ because in this case ψj kl , Ψj ′ k′ ǫ  = 0 for |j − j ′ | large enough. The condition is different from the conditions of Frazier and Jawerth in [17] and [18, Sections 2 and 3], and neither implies nor is implied by their conditions. Other conditions can be found in [24]. (4) Theorem 7.1 does not cover the entire range of Besov spaces. Using the lifting property of Besov spaces [37, p. 241] it is possible to show the following result. γ (ω) = |ω|γ ψ̂(ω) and fix β > 0. Assume that Eγ = {ψjγkl (t) = Let ψ γ , γ ∈ R, be defined by ψ γ 2j d/2 ψl (2j − k), j ∈ Z, k ∈ Zd , l = 1, . . . , L} is a frame for L2 (Rd ) for γ ∈ {0, −β, β}. If E satisfies the localization condition     ψj kl , Ψj ′ k′ ǫ   C 1 + |j − j ′ | + |k − k ′ | −s 2−β|j −j ′ | ∀j, j ′ ∈ Z, k, k ′ ∈ Zd , l, ǫ, (36)  for some s > d + 1, then the dual frame {ψ j kl } satisfies the same localization conditions. A distribution p,q f is in Ḃα+d/p−d/2 for p0 = d/s < p, q  ∞ and |α|  β if and only if   j ∈Z    f, ψj kl p k∈Zd , l∈F q/p 2αj q 1/q < ∞. p,q The latter expression is an equivalent norm on Ḃα+d/p−d/2. A detailed account of localized wavelet frames will be given elsewhere. The hypothesis that ψ ±β generates a wavelet frame seems redundant, but so far we have not been able to remove it. (5) The “hard analysis” of Frazier and Jawerth [18] and Meyer [33, Chapters VIII.3, 4] suggests an alternative approach to wavelet localization. Imitating the concept of almost diagonalization of operators with respect to wavelet bases, one may define the localization of a wavelet frame with respect to a Meyer wavelet basis by −j −j ′ ′   ψj kl , Ψj ′ k′ ǫ   C2−β|j −j ′ | 2−s|j −j ′ |/2 1 + |2 k − 2 k′ | max(2−j , 2−j ) −s ∀j, j ′ ∈ Z, k, k ′ ∈ Zd , l, ǫ, (37) for some s > d. As explained in [18, Remark 3.2], this condition amounts to an exponential decay with respect to the hyperbolic metric on the upper half space H = Rd × R+ . More precisely, we identify (j, k) ∈ Zd+1 with the point λ = (2−j k, 2−j ) ∈ H and endow H with a metric d that is right invariant under the (ax + b)-group; see [18, p. 53] for the exact formula. Then (37) can be written as   ψj kl , Ψj ′ k′ ǫ   C2−β|j −j ′ | e−sd(λ,λ′) , i.e., exponential localization with respect to a different metric on the index set. While this approach lacks the simplicity of Theorem 7.1, it might lead to more profound results; in particular, we would expect that this type of localization also yields characterizations of the Triebel–Lizorkin spaces. 46 E. Cordero, K. Gröchenig / Appl. Comput. Harmon. Anal. 17 (2004) 29–47 Acknowledgments This work was done while E.C. was visiting the University of Connecticut in October 2002. We thank Akram Aldroubi for a stimulating discussion that motivated Section 5, and Chris Heil whose thoughtful and constructive comments lead to a revision of the Introduction. References [1] A. Aldroubi, K. Gröchenig, Nonuniform sampling and reconstruction in shift-invariant spaces, SIAM Rev. 43 (4) (2001) 585–620. [2] A. Aldroubi, Q. Sun (Eds.), Frames, Kluwer Academic, Dordrecht, 2003, Adv. Comput. Math. 18 (2–4) (2003). [3] R. Balan, P. Casazza, C. Heil, Z. Landau, Density, redundancy, and localization of frames, Preprint, 2003. [4] P.G. Casazza, The art of frame theory, Taiwanese J. Math. 4 (2) (2000) 129–201. [5] O. Christensen, An Introduction to Frames and Riesz Bases, in: Applied and Numerical Harmonic Analysis, Birkhäuser, Boston, MA, 2003. [6] O. Christensen, T. Strohmer, The finite section method and problems in frame theory, Preprint, 2003. [7] I. Daubechies, The wavelet transform, time-frequency localization and signal analysis, IEEE Trans. Inform. Theory 36 (5) (1990) 961–1005. [8] I. Daubechies, Ten Lectures on Wavelets, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992. [9] I. Daubechies, A. Grossmann, Frames in the Bargmann space of entire functions, Comm. Pure Appl. Math. 41 (2) (1988) 151–164. [10] I. Daubechies, A. Grossmann, Y. Meyer, Painless nonorthogonal expansions, J. Math. Phys. 27 (5) (1986) 1271–1283. [11] C. de Boor, R.A. DeVore, A. Ron, The structure of finitely generated shift-invariant spaces in L2 (rd ), J. Funct. Anal. 119 (1) (1994) 37–78. [12] R. DeVore, I. Daubechies, Approximating a bandlimited function from very coarsely quantized data: A family of stable sigma–delta modulators of arbitrary order, Ann. Math. 158 (2) (2003) 679–710. [13] R.A. DeVore, Nonlinear approximation, in: Acta Numerica, 1998, Cambridge Univ. Press, Cambridge, 1998, pp. 51–150. [14] R.A. DeVore, V.N. Temlyakov, Some remarks on greedy algorithms, Adv. Comput. Math. 5 (2–3) (1996) 173–187. [15] R.J. Duffin, A.C. Schaeffer, A class of nonharmonic Fourier series, Trans. Amer. Math. Soc. 72 (1952) 341–366. [16] M. Fornasier, Constructive Methods for Numerical Applications in Signal Processing and Homogenization Problems, Ph.D. thesis, Univ. of Padova and Univ. of Vienna, 2002. [17] M. Frazier, B. Jawerth, Decomposition of Besov spaces, Indiana Univ. Math. J. 34 (4) (1985) 777–799. [18] M. Frazier, B. Jawerth, A discrete transform and decompositions of distribution spaces, J. Funct. Anal. 93 (1) (1990) 34–170. [19] M. Frazier, B. Jawerth, G. Weiss, Littlewood–Paley Theory and the Study of Function Spaces, Conference Board of the Mathematical Sciences, Washington, DC, 1991. [20] R. Gribonval, M. Nielsen, Nonlinear approximation with dictionaries I. Direct estimates, J. Fourier Anal. Appl. 10 (1) (2003) 51–72. [21] R. Gribonval, M. Nielsen, Nonlinear approximation with dictionaries II. Inverse estimates, Preprint, 2003. [22] R. Gribonval, M. Nielsen, On a problem of Gröchenig about nonlinear approximation with localized frames, J. Fourier Anal. Appl. (2004), in press. [23] K. Gröchenig, Unconditional bases in translation and dilation invariant function spaces on Rn , in: Constructive Theory of Functions (Varna, 1987), Bulgar. Acad. Sci., Sofia, 1988, pp. 174–183. [24] K. Gröchenig, Describing functions: Atomic decompositions versus frames, Monatsh. Math. 112 (1) (1991) 1–42. [25] K. Gröchenig, Acceleration of the frame algorithm, IEEE Trans. Signal Process. 41 (12) (1993) 3331–3340, Special Issue on Wavelets and Signal Processing. [26] K. Gröchenig, Foundations of Time–Frequency Analysis, Birkhäuser, Boston, MA, 2001. [27] K. Gröchenig, Localized frames are finite unions of Riesz sequences, Adv. Comput. Math. 18 (2–4) (2003) 149–157. [28] K. Gröchenig, Localization of frames, Banach frames, and the invertibility of the frame operator, J. Fourier Anal. Appl. 10 (2) (2004) 105–132. E. Cordero, K. Gröchenig / Appl. Comput. Harmon. Anal. 17 (2004) 29–47 47 [29] K. Gröchenig, M. Leinert, Symmetry of matrix algebras and symbolic calculus for infinite matrices, Preprint, 2003. [30] D. Han, D.R. Larson, Frames, bases and group representations, Mem. Amer. Math. Soc. 147 (697) (2000) x+94. [31] S. Jaffard, Propriétés des matrices “bien localisées” près de leur diagonale et quelques applications, Ann. Inst. H. Poincaré Anal. Non Linéaire 7 (5) (1990) 461–476. [32] Y. Meyer, Ondelettes et Opérateurs I. Ondelettes, Hermann, Paris, 1990. [33] Y. Meyer, Ondelettes et Opérateurs II. Opérateurs de Calderón–Zygmund, Hermann, Paris, 1990. [34] S.B. Stechkin, On absolute convergence of orthogonal series, Dokl. Akad. Nauk SSSR 102 (1955) 37–40. [35] T. Strohmer, Numerical algorithms for discrete Gabor expansions, in: Gabor Analysis and Algorithms, Birkhäuser, Boston, MA, 1998, pp. 267–294. [36] V.N. Temlyakov, Nonlinear methods of approximation, Found. Comput. Math. 3 (1) (2003) 33–107. [37] H. Triebel, Theory of Function Spaces, Birkhäuser, Basel, 1983. [38] H. Triebel, The Structure of Functions, in: Monographs in Mathematics, vol. 97, Birkhäuser, Basel, 2001.