Y Maday

O Mula

G Turinici

Convergence analysis of the Generalized Empirical Interpolation Method

Let F be a compact set of a Banach space X . This paper analyses the "Generalized Empirical Interpolation Method" (GEIM) which, given a function f ∈ F , builds an interpolant J n [f ] in an n-dimensional subspace X n ⊂ X with the knowledge of n outputs (σ i (f )) n i=1 , where σ i ∈ X and X is the dual space of X . The space X n is built with a greedy algorithm that is adapted to F in the sense that it is generated by elements of F itself. The algorithm also selects the linear functionals (σ i ) n i=1 from a dictionary Σ ⊂ X . In this paper, we study the interpolation error max f ∈F f -J n [f ] X by comparing it with the best possible performance on an n-dimensional space, i.e., the Kolmogorov n-width of F in X , d n (F, X ). For polynomial or exponential decay rates of d n (F, X ), we prove that the interpolation error has the same behavior modulo the norm of the interpolation operator. Sharper results are obtained in the case where X is a Hilbert space.

Introduction

Let X be a Banach space of functions defined over a domain Ω ⊂ R d or C d , d ≥ 1, and let F be a compact set of X . Without loss of generality, we assume that the functions ϕ ∈ F satisfy ϕ X ≤ 1, where • X is the norm of X . In this paper, we investigate the approximation quality of functions in F with the "Generalized Empirical Interpolation Method" (GEIM, see [START_REF] Maday | A Generalized Empirical Interpolation Method: Application of reduced basis techniques to data assimilation[END_REF][START_REF] Maday | The Generalized Empirical Interpolation Method: Stability theory on Hilbert spaces with an application to the Stokes equation[END_REF]). For a given f ∈ F , the method builds an interpolant J n [f ] in an n-dimensional subspace X n ⊂ X with the knowledge of n outputs of (σ i (f )) n i=1 where the σ i are bounded linear functionals of X . The approximation space X n is built with a greedy algorithm that is adapted to F in the sense that it is generated by some elements of F itself. The algorithm also selects the linear functionals to be used from a dictionary Σ ⊂ X . This procedure is a generalization of the Empirical Interpolation Method (see [START_REF] Barrault | An empirical interpolation method: application to efficient reduced-basis discretization of partial differential equations[END_REF][START_REF] Grepl | Efficient reduced-basis treatment of nonaffine and nonlinear partial differential equations[END_REF][START_REF] Maday | A general multipurpose interpolation procedure: the magic points[END_REF]) that was originally defined for (C( Ω), • ∞ ) and with Dirac masses as linear functionals.

The current setting falls into in the framework of optimal recovery (see, e.g. [START_REF] Micchelli | The optimal recovery of smooth functions[END_REF][START_REF] Micchelli | Lectures on optimal recovery[END_REF]) in the sense that, for a given f ∈ F , we want to approximate it in an appropriate basis and using the knowledge of certain outputs σ i (f ), 1 ≤ i ≤ n. However note that there is an important difference with respect to the classical setting of this field which assumes that F is the unit ball of a smoothness space in X . In the current setting, we allow F to have more general types of geometry/regularity. For this reason, our approximation space X n and the linear functionals are chosen depending on F . This is in contrast to other methods like polynomial/spline/radial interpolation (see, e.g., [START_REF] Buhmann | Radial basis functions[END_REF]) or even meshless methods [START_REF] Belytschko | Meshless methods: an overview and recent developments[END_REF] since there the basis functions are fixed in advance. This idea of adaptivity makes GEIM be also different from kriging [START_REF] Stein | Interpolation of spatial data: some theory for kriging[END_REF] where an underlying stochastic process is a priori given. Here we only assume that F is compact, which enlarges the range of potential applications. For instance, it is possible to apply the methodology to the case where F is the solution manifold of a parametric PDE. This case is relevant for at least two types of applications. The first concerns the approximation of this manifold with reduced basis methods and the treatment of nonlinearities in the PDE (see [START_REF] Grepl | Efficient reduced-basis treatment of nonaffine and nonlinear partial differential equations[END_REF]). The second concerns the coupling of measurement data (represented by the σ i (f ), 1 ≤ i ≤ n) with parametrized models (represented by the space X n ) in a systematic way and on the basis of suitable functional spaces. For the particular setting of GEIM, numerical examples can be found in [START_REF] Maday | A Generalized Empirical Interpolation Method: Application of reduced basis techniques to data assimilation[END_REF][START_REF] Maday | The Generalized Empirical Interpolation Method: Stability theory on Hilbert spaces with an application to the Stokes equation[END_REF] where it was also explained how the method could assist in the placement of sensors in real physical experiments and the minimization of their number. After the submission of this paper, this line of research has been further developed in several relevant works. For Hilbert spaces, an extension has been proposed in [START_REF] Maday | A Parameterized-Background Data-Weak approach to variational data assimilation: formulation, analysis, and application to acoustics[END_REF] which consists in a particular least squares approximation with m ≥ n measurement data. In addition, it has been proven in [START_REF] Binev | Data Assimilation in Reduced Modeling[END_REF] that, when X is a Hilbert space, both GEIM and the least-squares method are optimal in a sense that will be clarified later in this paper. Last but not least, we would like to cite the even more recent work [START_REF] Devore | Data assimilation in Banach spaces[END_REF] on data assimilation in Banach spaces which can be seen as a further abstraction of GEIM and [START_REF] Maday | A Parameterized-Background Data-Weak approach to variational data assimilation: formulation, analysis, and application to acoustics[END_REF][START_REF] Binev | Data Assimilation in Reduced Modeling[END_REF].

Since the interpolation operator J n : X → X n built by the GEIM targets the elements of F , it is important to quantify the error max

u∈F u -J n [u] X . (1)
The aim of this paper is to compare [START_REF] Barrault | An empirical interpolation method: application to efficient reduced-basis discretization of partial differential equations[END_REF] with the best possible performance in an n dimensional subspace of X , which is given by the Kolmogorov n-width of F in X ,

d n (F, X ) := inf Xn⊂X dim(Xn )≤n max u∈F inf v∈Xn u -v X . (2)
In particular, we show that when d n (F, X ) decays polynomially or exponentially, the interpolation error has the same behavior modulo a coefficient depending on the norm of the interpolation operator

Λ n := sup ϕ∈X J n [ϕ] X ϕ X , (3)
called Lebesgue constant. The conditions required on F to guarantee a certain decay rate in the sequence (d n (F, X )) n≥1 are far from trivial and require some regularity of the functions of F (see [START_REF] Pinkus | n-widths in approximation theory[END_REF] for a general reference). For the particular case when F is the solution manifold of a parametric PDE, we refer to [START_REF] Cohen | Kolmogorov widths under holomorphic mappings[END_REF] in which the decay of (d n (F, X )) n≥1 is connected with the regularity of the manifold with respect to the parameters.

The paper is organized as follows: in section 2 we explain the approximation strategy and the greedy algorithm of the GEIM. We also show that, under appropriate hypothesis, the greedy algorithm is of a weak type in the sense of [START_REF] Binev | Convergence rates for greedy algorithms in reduced basis methods[END_REF]. In section 3, we make several remarks on its practical implementation. Then we present the main results of the paper and derive convergence rates of the interpolation error in Banach spaces in section 4. In section 5, improved results are given for the particular case of Hilbert spaces. Note that results on convergence rates of GEIM have already been given in [START_REF] Maday | A priori convergence of the Generalized Empirical Interpolation Method[END_REF] for X = L 2 (Ω) and the main contribution of this work is to extend the results to general Banach spaces. Our methodology is based on the works [START_REF] Binev | Convergence rates for greedy algorithms in reduced basis methods[END_REF][START_REF] Devore | Greedy algorithms for reduced bases in Banach spaces[END_REF] on convergence rates of reduced basis and should be seen as a generalization of them in a sense that will be specified in 4.2.

The Generalized Empirical Interpolation Method

In what follows, we assume that the dimension of the vector space spanned by F is larger than N , where N is some given large number depending on F (N could potentially be infinite). This hypothesis is made since the asymptotic decay of the interpolation error is trivial otherwise. We also suppose given a dictionary Σ ⊂ X of bounded linear functionals with the following properties:

P1: ∀σ ∈ Σ, σ X = 1. P2: Unisolvence: If ϕ ∈ span{F } is such that σ(ϕ) = 0, ∀σ ∈ Σ, then ϕ = 0. P3: ∀ϕ ∈ span{F } the set {σ(ϕ), σ ∈ Σ} ⊂ R is closed.
For all n < N , our goal is to build a sequence of n-dimensional subspaces of X : X n = span{ϕ i ∈ X } n-1 i=0 , that approximate well enough the elements of F . As already mentioned in the introduction, one of the key features that makes the approximation adapted to F is that the basis functions ϕ i , 0 ≤ i ≤ n -1, are chosen in F itself. The approximation in X n of any ϕ ∈ X is done with its so-called generalized interpolant J n [ϕ] ∈ X n which satisfies the following interpolation property for a set of "well-chosen" bounded linear functionals {σ 0 , σ 1 ,. . . , σ n-1 } of Σ:

J n [ϕ] = n-1 j=0 β j ϕ j , such that σ i (J n [ϕ]) = σ i (ϕ), ∀i = 0, . . . , n -1. ( 4
)
The construction of the spaces X n and the selection of the suitable bounded linear functionals of Σ is recursively carried out by a greedy algorithm where the basis functions are selected one after another in F and tuned to improve the accuracy of the interpolation process. In general, from a practical point of view, since F is an infinite compact set, the n th function is chosen in a finite, large enough set F n , where {F n } n∈N is an embedded sequence of subsets of F . Similarly { Σ n } n∈N is an embedded sequence of finite subsets of Σ. For any n ∈ N, Σ n satisfies P2 and P3 for the set F n . In section 3, we discuss how F n can be chosen in practice. At the initialization of the greedy algorithm, the first interpolating function ϕ 0 is chosen as

ϕ 0 = arg max ϕ∈F0 ϕ X , (5)
and we define X 1 := span{ϕ 0 }. The first interpolating bounded linear functional is

σ 0 = arg max σ∈ Σ0 |σ(ϕ 0 )|.
The interpolation operator J 1 : X → X 1 is defined such that (4) is true for n = 1, i.e., σ 0 (J 1 [ϕ]) = σ 0 (ϕ), for any ϕ ∈ X . To facilitate the computation of the generalized interpolant, we express it in terms of q 0 := ϕ 0 / ϕ 0 X . In this basis, the interpolant reads J 1 [ϕ] = σ 0 (ϕ)q 0 , for any ϕ ∈ X . We then proceed by induction. Assume that, for a given 1 ≤ n < N , we built the set of interpolating functions {q 0 , q 1 , . . . , q n-1 } and the set of associated interpolating bounded linear functionals

{σ 0 , σ 1 , . . . , σ n-1 } such that the operator J n [ϕ] = n-1 j=0
α n j (ϕ)q j , is well defined for any ϕ ∈ X and the coefficients {α n j (ϕ)} j=0,...,n-1 , are given by the interpolation problem

     Find α n j (ϕ) n-1 j=0 such that: n-1 j=0 α n j (ϕ)σ i (q j ) = σ i (ϕ), ∀i = 0, . . . , n -1.
We now define ε n (ϕ) := ϕ -J n [ϕ] X , for any ϕ ∈ X , and choose ϕ n such that

ϕ n = arg max ϕ∈Fn ε n (ϕ) (6)
and then σ n such that

σ n = arg max σ∈ Σn |σ(ϕ n -J n [ϕ n ])|.
Note that the existence of σ n is ensured by the property P3 of the dictionary Σ n . The next basis function is then

q n = (ϕ n -J n [ϕ n ]) /σ n (ϕ n -J n [ϕ n ]). We finally set X n+1 := span{q j , j ∈ [0, n]} = span{ϕ j , j ∈ [0, n]}. The interpolation operator J n+1 : X → X n+1 is given by ∀ϕ ∈ X , J n+1 [ϕ] = n j=0 α n+1 j (ϕ)q j
and the coefficients α n+1 j (ϕ), j = 0, . . . , n, are given by the interpolation problem

     Find α n+1 j (ϕ) n j=0 such that: n j=0 α n+1 j (ϕ)σ i (q j ) = σ i (ϕ), ∀i = 0, . . . , n.
It has been proven in [START_REF] Maday | A general multipurpose interpolation procedure: the magic points[END_REF] (for EIM) and [START_REF] Maday | The Generalized Empirical Interpolation Method: Stability theory on Hilbert spaces with an application to the Stokes equation[END_REF] (for GEIM) that for any 1 ≤ n ≤ N , the set {q j , j ∈ [0, n-1]} is linearly independent and that this interpolation procedure is well-posed in X . This follows from the fact that the matrix (σ i (q j )) 0≤i,j≤n-1 is lower triangular with diagonal entries equal to 1. Using the triangular inequality it is standard to derive the following inequality on the interpolation error

∀ϕ ∈ X , ϕ -J n [ϕ] X ≤ (1 + Λ n ) inf ψn∈Xn ϕ -ψ n X , (7)
where Λ n is the Lebesgue constant, i.e., the norm of the interpolation operator J n : X → X n defined in [START_REF] Binev | Convergence rates for greedy algorithms in reduced basis methods[END_REF]. Note that nothing at this point ensures that sup ϕ∈F ϕ -J n [ϕ] X is close to d n (F, X ). One of the main reasons is that the basis set of X n has been derived in a hierarchical manner with the greedy algorithm. It is actually the purpose of this paper to connect these two quantities. As we will see in sections 4 and 5, the Lebesgue constant will be involved in the bounds and it is therefore important to discuss its behavior as n increases. First of all, Λ n depends both on F and Σ. In a practical implementation, it also depends on the choice of the subsets F i and Σ i , 0 ≤ i ≤ n -1. This observation is particularly clear in the case of Hilbert spaces where Λ n = 1/β n , with

β n := inf ϕ∈Xn sup σ∈span{σ0,...,σn-1} ϕ, σ X ,X ϕ X σ X
and the bound [START_REF] Devore | Data assimilation in Banach spaces[END_REF] holds without the 1 on the right hand side (see [START_REF] Maday | The Generalized Empirical Interpolation Method: Stability theory on Hilbert spaces with an application to the Stokes equation[END_REF]). In addition, it has recently been proven in [START_REF] Binev | Data Assimilation in Reduced Modeling[END_REF] that, in this setting, 1/β n is the smallest constant to relate max ϕ∈F ϕ -J n [ϕ] X and max ϕ∈F inf ψn∈Xn ϕ -ψ n X . A (generally very pessimistic) bound for Λ n that does not take into account the dependence on F and Σ was derived in [START_REF] Maday | A Generalized Empirical Interpolation Method: Application of reduced basis techniques to data assimilation[END_REF] and reads

Λ n ≤ 2 n-1 max i∈[0,n-1] q i X . (8)
In [START_REF] Maday | A general multipurpose interpolation procedure: the magic points[END_REF], an example that achieves the bound ( 8) was built but it involves a set F with large n-width in X . This does not correspond to the current setting since we assume that the sequence (d n (F, X )) has a relatively fast decay rate. In this context, numerical evaluations of Λ n indicate that it increases polynomialy (with small degree) in the worst case scenario (see, e.g., [START_REF] Barrault | An empirical interpolation method: application to efficient reduced-basis discretization of partial differential equations[END_REF], [START_REF] Grepl | Efficient reduced-basis treatment of nonaffine and nonlinear partial differential equations[END_REF], [START_REF] Maday | A general multipurpose interpolation procedure: the magic points[END_REF] for examples in the case of the EIM and [START_REF] Maday | The Generalized Empirical Interpolation Method: Stability theory on Hilbert spaces with an application to the Stokes equation[END_REF] for GEIM). For this reason, the conjecture that Λ n depends mildly on the dimension when the n-width of F is small and/or decays with n seems reasonable.

Some comments on the practical implementation of the greedy algorithm

Let us now discuss the choice of the finite sets F n for n ∈ N. These are to be chosen large enough such that the search over F n of arg max ϕ∈Fn ε n (ϕ) (in ( 6)) is "close enough" to the same search over F . The following lemma quantifies this idea:

Lemma 3.1 For any 0 < η < 1, there exits a family {F n ≡ F η n } N n=0 of finite subsets of F such that the greedy algorithm satisfies

     max ϕ∈F η 0 ϕ X ≥ η max ϕ∈F ϕ X , max ϕ∈F η n ϕ -J n [ϕ] X ≥ η max ϕ∈F ϕ -J n [ϕ] X , ∀ n ∈ {1, . . . , N }. (9)
Proof. We first address the case n = 0 as follows. Let η 0 = η. By compactness of F , there exists a finite subset

F η 0 ⊂ F and a function φ0 ∈ F such that max ϕ∈F min ψ∈F η 0 ϕ -ψ X ≤ (1 -η 0 ) φ0 X . (10)
Let ϕ 0 = arg max

ψ∈F η 0 ψ X and ϕ max 0 = arg max ϕ∈F ϕ X . For any ψ ∈ F η 0 , ϕ 0 X ≥ ψ X ≥ -ψ -ϕ max 0 X + ϕ max 0 X ,
from which we infer that ϕ 0 X ≥ -min

ψ∈F η 0 ψ -ϕ max 0 X + ϕ max 0 X ,
which, from [START_REF] Maday | A Generalized Empirical Interpolation Method: Application of reduced basis techniques to data assimilation[END_REF], yields

ϕ 0 X ≥ -(1 -η 0 ) φ0 X + ϕ max 0 X ≥ η 0 ϕ max 0 X .
This completes the proof of the first inequality of (9). For any 1 ≤ n ≤ N , let

η n = 1 -(1 -η)/(1 + Λ n ). (11)
We define

F η n := F η n-1 ∪ Ξ ηn n , where Ξ ηn n is a finite subset of F such that max ϕ∈F min ψ∈Ξ ηn n ϕ -ψ X ≤ (1 -η n ) r n [ φn ] X , (12)
for some φn ∈ F and where r n [ϕ] := ϕ -J n [ϕ], ∀ϕ ∈ X . The existence of Ξ ηn n and φn follows from the compactness of F , the fact that r n : X → X is continuous (with a norm that is upper-bounded by 1 + Λ n ) and that r n (F ) is a compact subset of X . Using that Ξ ηn n ⊂ F η n and inequality [START_REF] Devore | Data assimilation in Banach spaces[END_REF], we derive

max ϕ∈F min ψ∈F η n r n [ϕ -ψ] X ≤ max ϕ∈F min ψ∈Ξ ηn n r n [ϕ -ψ] X ≤ (1 + Λ n )max ϕ∈F min ψ∈Ξ ηn n ϕ -ψ X .
Thus, by using [START_REF] Maday | A priori convergence of the Generalized Empirical Interpolation Method[END_REF] in the previous inequality, we have

max ϕ∈F min ψ∈F η n r n [ϕ -ψ] X ≤ (1 + Λ n )(1 -η n ) r n [ φn ] X = (1 -η) r n [ φn ] X . (13)
Let

ϕ n = arg max ψ∈F η n r n [ψ] X and ϕ max n = arg max ϕ∈F r n [ϕ] X . For any ψ ∈ F η n , r n [ϕ n ] X ≥ r n [ψ] X ≥ -r n [ψ -ϕ max n ] X + r n [ϕ max n ] X ,
which, by using inequality [START_REF] Maday | A general multipurpose interpolation procedure: the magic points[END_REF], finally yields

ϕ n -J n [ϕ n ] X ≥ -(1 -η) r n [ φn ] X + r n [ϕ max n ] X ≥ η ϕ max n -J n [ϕ max n ] X .
which ends the proof. The parameter η above quantifies to what extent the search over F n = F η n differs from the search over F in the greedy algorithm. This relaxation expressed in the form of ( 9) is known as the weak greedy algorithm (in the sense defined in section 1.3 of [START_REF] Binev | Convergence rates for greedy algorithms in reduced basis methods[END_REF]). We set η = 1 as an extreme case where F η n = F (this is the strong greedy algorithm). Then, the smaller the η, the coarser the search over F η n will be in comparison with a search over F .

An important point to note is that the construction above depends on the application of the finite covering property of compact sets. Hence the question: how to obtain the sets {F n } N n=0 in practice? In full generality, this task is not entirely possible since it requires optimizations over the whole set F . However, the problem becomes feasible if we have some additional knowledge of the manifold F like, e.g., information about its geometry or regularity. As an example, let us consider the case where F is a set of parameter dependent functions F = {u(.; µ); µ ∈ D} where D is a compact set of parameters1 . Then the derivability of the mapping µ ∈ D → u(.; µ) and a known uniform bound on this derivative with respect to µ (no regularity in the spacial direction is assumed here) allows to build a finite covering from a finite set in the compact set D in a completely constructive way.

Instead of working with such certified a priori adaptive subsets, another a posteriori adaptative option can be proposed following the arguments presented in [START_REF] Maday | Locally adaptive greedy approximations for anisotropic parameter reduced basis spaces[END_REF] where a knowledge of the geometry of F is learnt on the fly as the greedy algorithm is implemented.

Note finally that, in many actual implementations, a less ideal approach is used where a fixed, unique, large enough, subset F f inite ⊂ F (and a fixed subset Σ) is chosen. In frequent cases where the Kolmogorov dimension is rapidly decaying to zero the greedy algorithm ends after very few iterations and this crude procedure actually works well in practice.

Convergence rates of the GEIM in a Banach space

In order to have consistent notations in what follows, we define ϕ n = 0 and X n = X N for n > N . In this section, X is a Banach space.

Preliminary notations and properties

To fix some notations, let K be a nonempty subset of X . For every ϕ ∈ X , the distance between ϕ and the set K is dist(ϕ, K) := inf y∈K ϕ -y X .

For any ϕ ∈ X , the metric projection of ϕ onto K is the set

P K (ϕ) = {z ∈ K : ϕ -z X = dist(ϕ, K)}.
In general, this set can be empty or composed of one or more than one element. However, in the particular case where K is a finite dimensional vector space, P K (ϕ) is not empty. For any n ≥ 1, the non empty set

P n (ϕ) = {z ∈ X n : ϕ -z X = dist(ϕ, X n )} ( 14
)
will denote the metric projection of ϕ ∈ X onto X n . Since the uniqueness of the metric projection onto X n is not necessarily ensured, in the following, P n (ϕ) will denote one of the elements of the set [START_REF] Maday | A Parameterized-Background Data-Weak approach to variational data assimilation: formulation, analysis, and application to acoustics[END_REF]. We now define τ n (F ) X := max

f ∈F f -P n (f ) X , n ≥ 1. ( 15
)
Note that τ n (F ) X ≤ max f ∈F f X ≤ 1 given that the elements of F have norm less than 1. We will use the abbreviation τ n and

d n for τ n (F ) X and d n (F, X ). Likewise, (τ n ) ∞ n=1 and (d n ) ∞ n=1 will denote the sequences (τ n (F ) X ) ∞ n=1 and (d n (F, X )) ∞ n=1
respectively. Finally we introduce the parameter

γ n = η 1 + Λ n , ∀ 1 ≤ n ≤ N . ( 16
)
where η was introduced in ( 9) and Λ n is the Lebesgue constant.

Main strategy to derive convergence rates

We start this section by proving the following lemma.

Lemma 4.1 For any n ≥ 1, the function ϕ n defined in (6) verifies

ϕ n -P n (ϕ n ) X ≥ γ n τ n . (17)
Proof. From equation [START_REF] Devore | Data assimilation in Banach spaces[END_REF] applied to ϕ = ϕ n we have

ϕ n -P n (ϕ n ) X ≥ 1 1 + Λ n ϕ n -J n (ϕ n ) X . But ϕ n -J n (ϕ n ) X ≥ η ϕ -J n (ϕ) X for any ϕ ∈ F according to the definition of ϕ n . Thus ϕ n - P n (ϕ n ) X ≥ γ n ϕ -J n (ϕ) X ≥ γ n ϕ -P n (ϕ) X .
Lemma 4.1 shows that the weak greedy algorithm of GEIM has very similar properties as the one in [START_REF] Devore | Greedy algorithms for reduced bases in Banach spaces[END_REF]. The difference is that, in [START_REF] Devore | Greedy algorithms for reduced bases in Banach spaces[END_REF], inequality [START_REF] Micchelli | The optimal recovery of smooth functions[END_REF] involves a constant parameter γ independent of n. We take this into account in our analysis: in section 4.3 we analyze the convergence rates for (τ n ) ∞ n=1 by extending the proofs of [START_REF] Devore | Greedy algorithms for reduced bases in Banach spaces[END_REF] to the case where γ depends on n. For the sake of comparison, we first recall here their main results in lemmas 4.2 and 4.3 below:

Lemma 4.2 (Corollary 4.2 -(ii) of [8]) If, for α > 0, we have d n ≤ C 0 n -α , n = 1, 2, . . . , then for any 0 < β < min{α, 1/2}, we have τ n ≤ C 1 n -α+1/2+β , n = 1, 2, . . . , with C 1 := max C 0 4 4α+1 γ -4 2β + 1 2β α ; max n=1,...,7 n α-β-1/2 . Lemma 4.3 (Corollary 4.2 -(iii) of [8]) If, for α > 0, d n ≤ C 0 e -c1n α , n = 1, 2, . . . , then τ n < √ 2C 0 γ -1 √ ne -c2n α , n = 1, 2, . . . , where c 2 = 2 -1-2α c 1 .
The factor √ n can be removed by reducing the constant c 2 .

Once this generalization is done, by using inequality [START_REF] Devore | Data assimilation in Banach spaces[END_REF], convergence rates for the interpolation error will easily follow (see section 4.4).

Convergence rates for

(τ n ) ∞ n=1 in the case where (γ n ) ∞ n=1 is not constant
We start by looking for an upper bound of the sequence (τ n ) ∞ n=1 that involves the sequence of Kolmogorov n-widths (d n ) ∞ n=1 . The case n = 1 is addressed in lemma 4.4. The case n > 1 is addressed in theorem 4.5. From this last theorem, we infer corollaries 4.6 and 4.7 that will be useful to derive convergence rates for (τ n ) ∞ n=1 .

Lemma 4.4 For n = 1, τ 1 ≤ 2(1 + η -1 )d 1 .
Proof. Given the parameter η in the GEIM greedy algorithm, let us chose β > 1/η. We begin by recalling and introducing some notations. First of all, ϕ 0 is the first interpolating function chosen in (5) by the greedy algorithm and X 1 = span{ϕ 0 }. For any ϕ, P 1 (ϕ) is the metric projection of ϕ onto X 1 . Let ϕ max 0 = arg max ϕ∈F ϕ X . From (9) in the case n = 0, ϕ 0 X ≥ η ϕ max 0 X . Let X µ be a one dimensional subspace and E µ := max

x∈F min y∈Xµ x -y X . For any ϕ ∈ F , ϕ -P Xµ (ϕ) X ≤ E µ . Let ϕ max µ = arg max ϕ∈F P Xµ (ϕ) X .
We now divide the proof by considering two cases of values of P Xµ (ϕ max µ ) X . If

P Xµ (ϕ max µ ) X ≤ 1+η η-1/β E µ , for all ϕ ∈ F : ϕ -P 1 (ϕ) X ≤ ϕ X ≤ ϕ -P Xµ (ϕ) X + P Xµ (ϕ) X ≤ E µ + P Xµ (ϕ max µ ) X ,
which yields

ϕ -P 1 (ϕ) X ≤ 1 + 1 + η η -1/β E µ , ∀ϕ ∈ F. ( 18
)
If P Xµ (ϕ max µ ) X ≥ 1+η η-1/β E µ , we have:

P Xµ (ϕ 0 ) X ≥ ϕ 0 X -E µ ≥ η ϕ max 0 X -E µ ≥ η ϕ max µ X -E µ , (19)
and thus

P Xµ (ϕ 0 ) X ≥ η P Xµ (ϕ max µ ) X -E µ -E µ ≥ η P Xµ (ϕ max µ ) X -(1 + η)E µ ,
from which we infer that

P Xµ (ϕ 0 ) X ≥ P Xµ (ϕ max µ ) X /β. ( 20
)
From inequality (20), it follows that P Xµ (ϕ 0 ) X > 0 given that P Xµ (ϕ max µ ) X is positive. Furthermore, for any ϕ ∈ X , there exits λ ϕ ∈ R such that:

P Xµ (ϕ) = λ ϕ P Xµ (ϕ 0 ). ( 21
)
Hence the decomposition:

ϕ = P Xµ (ϕ) + ϕ -P Xµ (ϕ) = λ ϕ P Xµ (ϕ 0 ) + ϕ -P Xµ (ϕ) = λ ϕ (P Xµ (ϕ 0 ) -ϕ 0 ) + λ ϕ ϕ 0 + ϕ -P Xµ (ϕ). ( 22
)
Since ϕ -P 1 (ϕ) X ≤ ϕ -λ ϕ ϕ 0 X , we can use equation ( 22) to bound ϕ -λ ϕ ϕ 0 X and write

ϕ -P 1 (ϕ) X ≤ |λ ϕ | P Xµ (ϕ 0 ) -ϕ 0 X + ϕ -P Xµ (ϕ) X ≤ (1 + |λ ϕ |)E µ .
Furthermore, given that P Xµ (ϕ max µ ) X ≥ P Xµ (ϕ) X for any ϕ ∈ F , we have

P Xµ (ϕ max µ ) X ≥ |λ ϕ | P Xµ (ϕ 0 ) X , (23)
where we have used equality (21). Inequalities (20) and (23) yield |λ ϕ | ≤ β and therefore ϕ-P 1 (ϕ) X ≤ (1 + β)E µ . As a result, we have proven that for any β > 1/η and any ϕ ∈ F , ϕ -P 1 (ϕ) X ≤ g η (β)E µ , where

∀β > 1/η, g η (β) := max 1 + β; 1 + 1 + η η -1/β . Thus ϕ-P 1 (ϕ) X ≤ min β>1/η g η (β)E µ = 2(1+η -1 )E µ .
Since the inequality is valid for any one dimensional space X µ , the final result follows by taking the infimum over all one dimensional spaces in X .

Theorem 4.5 For any N ≥ 0, consider a weak greedy algorithm for which (17) holds. Then, for any

K ≥ 2, 1 ≤ m < K K i=1 τ 2 N +i ≤ 1 K i=1 γ 2 N +i 2 K K K-m K i=1 τ 2 N +i m d 2(K-m) m . (24)
Proof. This result is an extension of theorem 4.1 of [START_REF] Devore | Greedy algorithms for reduced bases in Banach spaces[END_REF] to the case where the parameter γ depends on N , the dimension of the space X N . The proof is a slight modification of the one in [START_REF] Devore | Greedy algorithms for reduced bases in Banach spaces[END_REF] but we provide it in the appendix for the self-consistency of this paper.

Corollary 4.6 For any n ≥ 2,

τ n ≤ 1 n i=1 γ 1/n i √ 2 min 1≤m<n    n n-m 2n n i=1 τ 2 i m 2n d n-m n m    (25)
In particular, for any ≥ 1:

τ 2 ≤ 2 1 2 i=1 γ 1/2 i d . (26)
Proof. We take N = 0, K = n and any 1 ≤ m < n in (24) and use the monotonicity of (τ n ) ∞ n=1 to obtain:

τ 2n n ≤ n i=1 τ 2 i ≤ 1 n i=1 γ 2 i 2 n n n-m n i=1 τ 2 i m d 2(n-m) m ,
that yields (25). In particular, if n = 2 and m = , we have:

τ 2 ≤ 1 2 i=1 γ 1/2 i √ 2(2 ) 1/4 2 i=1 τ 2 i 1/4 d ≤ 1 2 i=1 γ 1/2 i √ 2(2 ) 1/4 (2 ) 1/4 d = 2 1 2 i=1 γ 1/2 i d ,
where we used that all τ i ≤ 1.

Corollary 4.7 For N ≥ 0, K ≥ 2 and 1 ≤ m < K:

τ N +K ≤ 1 K i=1 γ 1/K N +i √ 2Kτ m/K N +1 d 1-m/K m (27)
Proof. Using that (τ n ) ∞ n=1 is monotonically decreasing and following the same lines as above, we derive from inequality (24) that:

τ 2K N +K ≤ 1 K i=1 γ 2 N +i 2 K K K-m K i=1 τ 2 N +i m d 2(K-m) m . Therefore, τ N +K ≤ 1 K i=1 γ 1/K N +i √ 2K K-m 2K Kτ 2 N +1 m/2K d 1-m/K m ≤ 1 K i=1 γ 1/K N +i √ 2Kτ m/K N +1 d 1-m/K m .
We now derive convergence rates for the sequence (τ n ) ∞ n=1 . As we will see, the convergence and its rate strongly depend on the behavior of the Lebesgue constant. As discussed in section 2, (Λ n ) ∞ n=1 can diverge exponentially. On the contrary and as it is often the case in practice, it can be polynomially increasing or even be bounded. We take this point into account by assuming different types of convergence rates for (d n ) ∞ n=1 . To begin with, Lemmas 4.8 and 4.9 below consider the case where (d n ) ∞ n=1 decreases polynomially or exponentially. No assumption on the behavior of (Λ n ) ∞ n=1 is made in these results. With the reference to γ n introduced in (16), we have Lemma 4.8 For any n ≥ 1, let n = 4 + k (where ∈ {0, 1, . . . } and k ∈ {0, 1, 2, 3}). If, for n ≥ 1, d n ≤ C 0 n -α , with C 0 > 0, then τ n ≤ C 0 β n n -α , where

β n = β 4 +k :=        2 1 + η -1 if n = 1 1 2 i=1 γ 1 2 1- k 4 +i 2 2 β 1 (2 √ 2) α if n ≥ 2,
and 1 = 2 + 2k 3 , 2 = 2 + k 4
, where • and • are the floor and ceiling functions respectively. Proof. The proof is done by induction over n and the case n = 1 directly follows from lemma 4.4. In the case n ≥ 2, we write n = N + K with N ≥ 0 and K ≥ 2. Thanks to corollary 4.7, we have for any 1 ≤ m < K:

τ n = τ N +K ≤ 1 K i=1 γ 1/K N +i √ 2Kτ m/K N +1 d 1-m/K m . ( 28
)
We now use that d m ≤ C 0 m -α and the recurrence hypothesis at index N + 1 that states τ N +1 ≤ C 0 β N +1 (N + 1) -α which yields: These choices of N, K and m combined with the upper bound of ξ yield the result τ n ≤ C 0 β n n -α in the case k = 1, 2 or 3. To address the case n = 4 , we come back to estimate (28) and use that τ N +1 ≤ τ N . It follows:

τ N +K ≤ C 0 √ 2K 1 K i=1 γ 1 K N +i β m K N +1 ξ(N, K, m) α (N + K) -α , (29)
τ n ≤ 1 K i=1 γ 1/K N +i √ 2Kτ m/K N d 1-m/K m . ( 30
)
Choosing N = K = 2 and m = , the inequality (30) directly yields the desired result:

τ 4 ≤ C 0 √ 2 2 β 2 1 2 i=1 γ 1 2 2 +i (2 √ 2) α (4 ) -α .
Lemma 4.9 If, for n ≥ 1, d n ≤ C 0 e -c1n α , with C 0 ≥ 1 and α > 0, then τ n ≤ C 0 β n e -c2n α , where c 2 := c 1 2 -2α-1 and

β n :=          2 1 + η -1 , if n = 1 √ 2 1 2 n 2 i=1 γ 1 2 n 2 i √ n, if n ≥ 2.
Proof. The case n = 1 easily follows from lemma 4.4. For n = 2 ( ≥ 1), inequality (26) directly yields:

τ 2 ≤ 2 1 2 i=1 γ 1/2 i d ≤ C 0 √ 2 1 2 i=1 γ 1/2 i √ 2 e -c 1 2 1+α (2 ) α , ( 31
)
where we used that d ≤ C 0 e -c1( ) α and that C 0 ≥ 1. For n = 2 + 1, by using inequality (31) and τ 2 +1 ≤ τ 2 , we have:

τ 2 +1 ≤ C 0 √ 2 1 2 i=1 γ 1/2 i √ 2 e -c 1 2 1+α (2 ) α ≤ C 0 √ 2 1 2 i=1 γ 1/2 i √ 2 + 1e -c 1 2 1+2α (2 +1) α . ( 32
)
From lemmas 4.8 and 4.9 we observe that, if (Λ n ) ∞ n=1 diverges exponentially, then an exponential decay is required for (d n ) ∞ n=1 . Let us now derive some results by adding different assumptions in the behavior of (Λ n ) ∞ n=1 . In corollary 4.10, we assume that (Λ n ) ∞ n=1 is monotonically increasing (i.e., (γ n ) ∞ n=1 monotonically decreasing).

Corollary 4.10 Assume that (Λ n ) ∞ n=1 is monotonically increasing, then: i) If d n ≤ C 0 n -α for any n ≥ 1, then τ n ≤ C 0 βn n -α , with βn := 2 1 + η -1 , if n = 1 2 3α+1 2 γ -2 n , if n ≥ 2.
If we write n as n = 4 + k (with ∈ {0, 1, . . . } and k ∈ {0, 1, 2, 3}),

then 2 = 2 + k 4 . ii) If d n ≤ C 0 e -c1n α for n ≥ 1 and C 0 ≥ 1, then τ n ≤ C 0 βn e -c2n -α , with c 2 = c 1 2 -2α-1 and βn := 2 1 + η -1 , if n = 1 √ 2nγ -1 n , if n ≥ 2.
Proof.

i) We show by induction that βn is larger than the coefficient β n defined in lemma 4.8. If n = 1, β1 = β 1 . Then, for n > 1, given that (γ n ) ∞ n=1 is monotonically decreasing,

β n ≤ γ -1 n 2 2 β 1 2 √ 2 α ≤ γ -1 n 2 2 β 1 2 √ 2 α ,
where we used the recurrence hypothesis β 1 ≤ β 1 in the second inequality. Furthermore, since β 1 ≤ 2 3α+1 2 γ -2 n , it follows that:

β n ≤ γ -1 n 2 2 2 3α+1 2 γ -2 n 2 √ 2 α = 2 3α+1 2 γ -2 n = βn .
ii) The result is straightforward and follows from the definition of β n given in lemma 4.9.

If (Λ n ) ∞ n=1 is constant, corollary 4.10 shows that we obtain exactly the same result as the one derived in [START_REF] Devore | Greedy algorithms for reduced bases in Banach spaces[END_REF] for the exponential case (recalled in lemma 4.3). In the case of polynomial decay, the result of corollary 4.10 provides a slightly degraded result with respect to the one in [START_REF] Devore | Greedy algorithms for reduced bases in Banach spaces[END_REF] (recalled in lemma 4.2). The most important difference relies on the fact that in [START_REF] Devore | Greedy algorithms for reduced bases in Banach spaces[END_REF] a convergence rate of order O(n -α+1/2+ε ) is obtained whereas the present results yields a convergence in O(n -α+1 ). It has so far not been possible to derive better convergence rates in the polynomial case for a general behavior of the sequence (Λ n ) ∞ n=1 . However, under the refined assumption

Λ n = O(n ζ ),
which is a typical behavior observed in numerical applications, Lemma 4.11 below shows that, in this case, the convergence is of order O(n -α+ζ+1/2+ε ), which is consistent with the result of [START_REF] Devore | Greedy algorithms for reduced bases in Banach spaces[END_REF], in case of a constant Λ n (ζ = 0).

Lemma 4.11 If, for n > 0, d n ≤ C 0 n -α and γ -1 n ≤ C ζ n ζ , with constants C 0 , C ζ , α, ζ > 0, then for any β > 1/2, we have τ n ≤ C 1 n -α+ζ+β , n ∈ N * , where C 1 := max C 0 2 2α 2 ζ ζ + β β -1 2 α max 1; C ζ+β ζ ζ ; max n=1,...,2 2(ζ+β) +1 n α-ζ-β .
Note that in the above lemma, the constant β has no connection with β n defined in section 2.

Proof. It follows from the monotonicity of (τ n ) ∞ n=1 and inequality (24) for N = K = n and any 1 ≤ m < n that:

τ 2n ≤ √ 2n 1 n i=1 γ 1/n n+i τ δ n d 1-δ m , δ := m n . ( 33
) Given β > 1/2, we define m := β -1 2 ζ + β + 1 (so that m < n for n > 2(ζ + β) > 2ζ + 1). It follows that δ = m n ∈ β -1 2 ζ + β , β -1 2 ζ + β + 1 n . (34)
We prove our claim by contradiction. Suppose it is not true and M is the first value where τ M > C 1 M -α+ζ+β . Clearly, because of the definition of C 1 and the fact that

τ n ≤ 1, we must have M > 2 2(ζ + β) + 1 (since M ≥ 2 2(ζ + β) + 2)
. We first consider the case M = 2n, and therefore n ≥ 2(ζ + β) + 1. From (33), we have:

C 1 (2n) -α+ζ+β < τ 2n ≤ √ 2n 1 n i=1 γ 1/n n+i τ δ n d 1-δ m ≤ √ 2nC ζ (2n) ζ C δ 1 n δ(-α+ζ+β) C 1-δ 0 (δn) -α(1-δ) , (35)
where we have used the fact that

τ n ≤ C 1 n -α+ζ+β and d m ≤ C 0 m -α . It follows that C 1-δ 1 < 2 α-β+ 1 2 C ζ C 1-δ 0 δ -α(1-δ) n 1 2 +δ(ζ+β)-β
and therefore

C 1 < 2 α-β+ 1 2 1-δ C 1 1-δ ζ C 0 δ -α n ζ+β 1-δ δ- β-1 2 ζ+β . Since, for n ≥ 2(ζ + β) + 1 > 2(ζ + β), we have δ < β -1 2 ζ + β + 1 n < β ζ + β , (36) then, 1 1 -δ
< ζ + β ζ . (37)
Hence,

ζ + β 1 -δ δ - β -1 2 ζ + β < ζ + β 1 -δ 1 n < (ζ + β) 2 ζ 1 n , (38)
where we have used inequalities (36) and (37). By using (38), it follows that

n ζ+β 1-δ δ- β-1 2 ζ+β < n (ζ+β) 2 ζ 1 n < 2 (ζ+β) 2 ζ . (39)
This yields:

C 1 < 2 α-β+ 1 2 1-δ C 1 1-δ ζ C 0 δ -α 2 (ζ+β) 2 ζ < 2 ( ζ+β ζ )(α+ζ+ 1 2 ) C 1 1-δ ζ C 0 δ -α . (40)
Furthermore, for -α + ζ + β < 0 (which is the meaningful case), and using the fact that β > 1 2 , we have:

2 ζ+β ζ (α+ζ+ 1 2 ) < 2 α ζ (α+ζ+β) < 2 2α 2 ζ and C 1 1-δ ζ < max 1; C ζ+β ζ ζ . (41)
Also, from (34), we have

δ -α < ζ + β β -1 2 α . (42)
By inserting inequalities (41) and ( 42) in (40), the desired contradiction follows:

C 1 < C 0 2 2α 2 ζ ζ + β β -1 2 α max 1; C ζ+β ζ ζ . Likewise, if M = 2n + 1, then M ≥ 2 2(ζ + β) + 3, which implies that n ≥ 2(ζ + β) + 1: C 1 2 -α+ζ+β (2n) -α+ζ+β < C 1 (2n + 1) -α+ζ+β < τ 2n+1 ≤ τ 2n . (43)
But, since we have from equation ( 35)

τ 2n ≤ √ 2nC ζ (2n) ζ C δ 1 n δ(-α+ζ+β) C 1-δ 0 (δn) -α(1-δ) , (44)
then, following the same argument as above, we get:

C 1 < C 0 2 ( ζ+β ζ )( 1 2 +2α-β) ζ + β β -1 2 α max 1; C ζ+β ζ ζ < C 0 2 2α 2 ζ ζ + β β -1 2 α max 1; C ζ+β ζ ζ ,
where we have used the fact that β > 1/2 in the last inequality.

Convergence rates of the interpolation error

Thanks to the convergence rates obtained for (τ n ) ∞ n=1 in section 4.3, the following rates are readily obtained for the interpolation error of GEIM.

Theorem 4.12 i) If d n ≤ C 0 n -α for any n ≥ 1, then ϕ -J n [ϕ] X ≤ (1 + Λ n )C 0 β n n -α for any ϕ ∈ F , where β n is given in lemma 4.8. ii) If d n ≤ C 0 e -c1n α for n ≥ 1 and C 0 ≥ 1, ϕ -J n [ϕ] X ≤ (1 + Λ n )C 0 β n e -c2n
α for any ϕ ∈ F , where β n and c 2 are defined as in lemma 4.9.

Proof. It follows from equation [START_REF] Devore | Data assimilation in Banach spaces[END_REF] and the definition of τ n that, ∀ϕ ∈ F, ϕ

-J n [ϕ] X ≤ (1 + Λ n ) ϕ - P n (ϕ) X ≤ (1 + Λ n )τ n .
We conclude the proof by bounding τ n by using lemmas 4.8 and 4.9.

If (Λ n ) ∞ n=1 is a monotonically increasing sequence, we have a more precise behavior: Corollary 4.13 Let (Λ n ) ∞ n=1 be a monotonically increasing sequence. Then, i) if

d n ≤ C 0 n -α for any n ≥ 1, then ∀ϕ ∈ F, ϕ -J n [ϕ] X ≤ 2C 0 1 + η -1 (1 + Λ 1 ), if n = 1. C 0 2 3α+1 2 (1 + Λ n ) 3 η -2 n -α , if n ≥ 2.
If we write n as n = 4 + k (with ∈ {0, 1, . . . } and k ∈ {0, 1, 2, 3}),

then 2 = 2 + k 4 . ii) if d n ≤ C 0 e -c1n α for n ≥ 1 and C 0 ≥ 1, then (remember c 2 = c 1 2 -2α-1 ) ∀ϕ ∈ F, ϕ -J n [ϕ] X ≤ 2C 0 1 + η -1 (1 + Λ 1 ), if n = 1, C 0 √ 2(1 + Λ n ) 2 η -1 √ ne -c2n α , if n ≥ 2, iii) if d n ≤ C 0 n -α and γ -1 n ≤ C ζ n ζ for any n ≥ 1, then for any β > 1/2, ∀ϕ ∈ F, ϕ -J n [ϕ] X ≤ ηC ζ C 1 n -α+2ζ+β ,
where the parameter C 1 is defined as in lemma 4.11.

Proof. i) and ii) easily follow from corollary 4.10 and iii) is derived by using lemma 4.11.

Convergence rates of GEIM in a Hilbert space

In this section, X is a Hilbert space equipped with its induced norm f X = (f, f ) X , where (., .) X is the scalar product in X . In the same spirit as in the case of a Banach space, we define the sequence (τ n ) ∞ n=1 as in formula ( 15) but now, for any f ∈ F , P n (f ) corresponds to the unique element of X n that is the orthogonal projection of f onto X n . Note that lemma 4.1 still holds in the Hilbert setting. We derive convergence rates for the interpolation error by applying the same strategy as in the Banach space case. In section 5.1, we derive convergence rates for (τ n ) ∞ n=1 as an intermediate step. We compare to [START_REF] Devore | Greedy algorithms for reduced bases in Banach spaces[END_REF] in corollary 3.3 by taking γ n = γ in our results. The results of [START_REF] Devore | Greedy algorithms for reduced bases in Banach spaces[END_REF] read:

Lemma 5.1 (Corollary 3.3 -(ii) of [8]) If d n ≤ C 0 n -α for n = 1, 2, . . . , then τ n ≤ C 1 n -α , n = 1, 2, . . . , with C 1 = 2 5α+1 γ -2 C 0 . Lemma 5.2 (Corollary 3.3 -(iii) of [8]) If d n ≤ C 0 e -c1n α for n = 1, 2, . . . , then τ n < √ 2C 0 γ -1 e -c2n α , n = 1, 2, . . . , where c 2 = 2 -1-2α c 1 .

Convergence rates for

(τ n ) ∞ n=1
Like in the Banach space case, we start by bounding the sequence (τ n ) ∞ n=1 with respect to (d n ) ∞ n=1 . This is done in theorem 5.3 (the analogue of theorem 4.5). It yields corollaries 5.4 and 5.5, that are the analogue of corollaries 4.6 and 4.7. The major difference with respect to the Banach space case is the absence of a factor √ n in corollaries 5.4 and 5.5. It will be the key to obtain improved results in Hilbert spaces.

Theorem 5.3 For any N ≥ 0, consider a weak greedy algorithm for which (17) holds. Then, for any

K ≥ 2, 1 ≤ m < K, K i=1 τ 2 N +i ≤ 1 K i=1 γ 2 N +i K m m K K -m K-m τ 2m N +1 d 2(K-m) m .
Proof. See appendix B.

In particular, for any ≥ 1

τ 2 ≤ √ 2 1 2 i=1 γ 1 2 i d . (46)
Corollary 5.5 For N ≥ 0, K ≥ 2 and 1 ≤ m < K:

τ N +K ≤ 1 K i=1 γ 1/K N +i √ 2τ m/K N +1 d 1-m/K m . (47)
Proof. The proofs of corollaries 5.4 and 5.5 follow very similar guidelines as the ones for corollaries 4.6 and 4.7. The only difference is that here the staring point is theorem 5.3 instead of 4.5. Using theorem 5.3, we derive decay rates of the sequence (τ n ) ∞ n=1 when (d n ) ∞ n=1 has a polynomial or an exponential decay. In lemmas 5.6 and 5.7, no assumption on the behavior of (Λ n ) ∞ n=1 is made. Lemma 5.6 For any n ≥ 1, let n = 4 + k (where ∈ {0, 1, . . . } and k ∈ {0, 1, 2, 3}). If, for n ≥ 1,

d n ≤ C 0 n -α with C 0 > 0, then τ n ≤ C 0 β n n -α , where β n = β 4 +k :=        2 1 + η -1 if n = 1 2β 1 1 2 i=1 γ 1 2 1- k 4 +i (2 √ 2) α if n ≥ 2 and 1 = 2 + 2k 3 , 2 = 2 + k 4 .
Corollary 5.10 If (Λ n ) ∞ n=1 is a monotonically increasing sequence, then:

• if d n ≤ C 0 n -α for any n ≥ 1, then for any ϕ ∈ F , ϕ -J n [ϕ] X ≤ 2C 0 1 + η -1 (1 + Λ 1 ), if n = 1. C 0 2 3α+1 (1 + Λ n ) 3 η -2 n -α , if n ≥ 2. • if d n ≤ C 0 e -c1n α for n ≥ 1 and C 0 ≥ 1, then for any ϕ ∈ F , ϕ -J n [ϕ] X ≤ 2C 0 1 + η -1 (1 + Λ 1 ), if n = 1, C 0 √ 2(1 + Λ n ) 2 η -1 e -c2n α , if n ≥ 2,
where c 2 = 2 -2α-1 .

Final remarks

We have analyzed the convergence rates of the interpolation error in GEIM in the case of polynomially or exponentially decaying Kolmogorov n-widths of F . The impact on this convergence rate of the Lebesgue constant appears as multiplicative factors of order O(Λ 2 n ) or O(Λ 3 n ). Given that, for reasonable enough dictionaries Σ, it has been observed in practical applications that (Λ n ) ∞ n=1 is linear in the worst case scenario (see [START_REF] Barrault | An empirical interpolation method: application to efficient reduced-basis discretization of partial differential equations[END_REF], [START_REF] Grepl | Efficient reduced-basis treatment of nonaffine and nonlinear partial differential equations[END_REF], [START_REF] Maday | A general multipurpose interpolation procedure: the magic points[END_REF], [START_REF] Maday | The Generalized Empirical Interpolation Method: Stability theory on Hilbert spaces with an application to the Stokes equation[END_REF]), our results prove that a decay of order O(n -3 ) in d n (F, X ) should be enough to ensure the convergence of the interpolation errors of GEIM.

A Proof of Theorem 4.5

We begin by recalling a preliminary lemma for matrices that is proven in [START_REF] Devore | Greedy algorithms for reduced bases in Banach spaces[END_REF].

Lemma A.1 Let G = (g i,j ) be a K × K lower triangular matrix with rows g 1 , . . . , g K , W be any m dimensional subspace of R K , and P be the orthogonal projection of R K onto W . Then,

K i=1 g 2 i,i ≤ 1 m K i=1 P g i 2 2 m 1 K -m K i=1 g i -P g i 2 2 K-m (48)
where . 2 is the euclidean norm of a vector in R K .

For the proof of theorem 4.5, we consider a lower triangular matrix A = (a i,j ) ∞ i,j=1 defined in the following way. For each j = 1, . . . , we let λ j ∈ X be the bounded linear functional of norm one that satisfies:

(i) λ j (X j ) = 0, (ii) λ j (ϕ j ) = dist(ϕ j , X j ),

where X j = span{ϕ 0 , . . . , ϕ j-1 }, j = 1, 2, . . . , is the interpolating space given by the greedy algorithm of GEIM. The existence of such a functional is a consequence of the Hahn-Banach theorem. We let A be the matrix with entries a i,j = λ j (ϕ i ).

The matrix A has the following properties:

Q1: The diagonal elements of A satisfy γ n τ n ≤ a n,n ≤ τ n .
Q2: For every j < i, |a i,j | ≤ dist(ϕ i , X j ) ≤ τ j .

Q3: For every j > i, a i,j = 0.

Proof.

Q1:

We have a j,j = λ j (ϕ j ) = dist(ϕ j , X j ) = ϕ j -P j (ϕ j ) X ≤ max ϕ∈F ϕ -P j (ϕ) X = τ j .

Lemma 4.1 directly yields the second part of the inequality: a j,j ≥ γ j τ j .

Q2: For any j < i and any g ∈ X j ,

|a i,j | = |λ j (ϕ i )| = |λ j (ϕ i -g)| ≤ λ j X ϕ j -g X ,
where we have used the fact that λ j (g) = 0 because g ∈ X j . Therefore, since λ j X = 1, we have |a i,j | ≤ ϕ j -g X , ∀ g ∈ X j . Thus, |a i,j | ≤ ϕ i -P j (ϕ i ) X ≤ τ j .

Q3: Clearly, for j > i, a i,j = λ j (ϕ i ) = 0 because ϕ i ∈ X j in this case.

We can now prove theorem 4.5: Proof. For a given K ≥ 2, consider the K × K matrix G formed by the rows and columns of A with indices from {N + 1, . . . , N + K}. Let Y m be a subspace of X of dimension ≤ m (we recall that 1 ≤ m < K). For each i, there exists an element

h i ∈ Y m such that ϕ i -h i X = dist(ϕ i , Y m ) ≤ d Ym , where d Ym := max ϕ∈F dist(ϕ, Y m ). Therefore |λ j (ϕ i ) -λ j (h i )| = |λ j (ϕ i -h i )| ≤ λ j X ϕ i -h i X ≤ d Ym . ( 50
)
We now consider the vectors (λ N +1 (h), . . . , λ N +K (h)) , h ∈ X m . They span a space W ⊂ R K of dimension ≤ m. We assume that dim(W ) = m (a slight notational adjustment has to be made if dim(W ) < m). It follows from (50) that each row g i of G can be approximated by a vector from W in the ∞ norm to accuracy d Ym , and therefore in the 2 norm to accuracy √ Kd Ym . Let P be the orthogonal projection of R K onto W . Hence, we have

g i -P g i 2 ≤ √ Kd Ym , i = 1, . . . , K. (51)
Also, from the property Q2,

P g i 2 ≤ g i 2 ≤ i j=1 τ 2 N +j 1/2
, and therefore

K i=1 P g i 2 2 ≤ K i=1 i j=1 τ 2 N +j ≤ K K i=1 τ 2 N +i . (52)
Next, we apply lemma A.1 for this G and W and use property Q1 and estimates (51) and (52) to derive

K i=1 γ 2 N +i τ 2 N +i ≤ K m K i=1 τ 2 N +i m K 2 K -m d 2 Ym K-m = K K-m K m m K K -m K-m K i=1 τ 2 N +i m d 2(K-m) Ym ≤ 2 K K K-m K i=1 τ 2 N +i m d 2(K-m) Ym
, where we have used the fact that x -x (1 -x x-1 ) ≤ 2 for 0 < x < 1. The proof follows by taking the infimum over all subspaces Y m of X of dimension ≤ m.

B Proof of Theorem 5.3

In this section, X is a Hilbert space. We denote by (ϕ * n ) n≥0 the orthonormal system obtained from (ϕ n ) n≥0 by Gram-Schmidt orthonormalisation. It follows that the orthogonal projector P n from X onto X n can be written as P n ϕ = n-1 i=0 (ϕ, ϕ * i ) X ϕ * i , for n ≥ 1. In particular, ϕ n = P n+1 ϕ n = n j=0 a n,j ϕ * j , with a n,j = (ϕ n , ϕ * j ) X , j ≤ n. There is no loss of generality in assuming that the infinite dimensional Hilbert space X is 2 (N) and that ϕ * j = e j , where e j is the sequence with all entries zero except the j-th entry which is 1. In a similar manner as in the Banach space case, we associate with the greedy procedure of GEIM the lower triangular matrix: A := (a i,j ) ∞ i,j=0 , a i,j := 1, j > i. The following two properties characterize any lower triangular matrix A generated by such a greedy algorithm. We can now prove theorem 5.3: Proof. For a given K ≥ 2, consider the K × K matrix G = (g i,j ) formed by the rows and columns of A with indices from {N + 1, . . . , N + K}. Each row g i is the restriction of ϕ N +i to the coordinates N + 1, . . . , N + K. Let Y m be a subspace of X of dimension ≤ m. Then, dist(ϕ N +i , Y m ) ≤ d Ym , i = 1, . . . , K. Let W be the linear subspace which is the restriction of Y m to the coordinates N + 1, . . . , N + K. In general, dim( W ) ≤ m. Let W be a m dimensional space, W ⊂ span{e N +1 , . . . , e N +K }, such that W ⊂ W and P and P are the projections in R K onto W and W , respectively. Clearly,

P g i 2 ≤ g i 2 ≤ τ N +1 , i = 1, . . . , K, (53)
where we have used property S2 in the last inequality. Note that

g i -P g i 2 ≤ g i -P g i 2 = dist g i , W ≤ dist (ϕ N +i , Y m ) ≤ d Ym , i = 1, . . . , K. (54)
It follows from property S1 that

K i=1 |a N +i,N +i | 2 ≥ K i=1 γ 2 N +i τ 2 N +i . (55)
To derive the result, we apply lemma A.1 for this G and W , use estimates (53), (54) and (55) and take the infimum over all subspaces of X of dimension ≤ m.

N = 2 - 1 ,

 21 ≤ m < K and any given index n = N + K ≥ 2, where N ≥ 0 and K ≥ 2. Furthermore, any n ≥ 2 can be written as n = 4 + k with ∈ N and k ∈ {0, 1, 2, 3}. If k = 1, 2 or 3, it can easily be proven that the function ξ is bounded by 2 √ K = 2 + 2, m = + 1 and ≥ 1 in the case k = 1, N = 2 , K = 2 + 2, m = + 1 and ≥ 0 in the case k = 2, N = 2 + 1, K = 2 + 2, m = + 1 and ≥ 0 in the case k = 3.

Corollary 5 . 4

 54 For n ≥ 2,

S1:

  The diagonal elements of A satisfy γ n τ n ≤ |a n,n | ≤ τ n . S2: For every m ≥ n, one has For any n ≥ 1, since ϕ n -P n ϕ n = a n,n ϕ * n , it follows that for any n ≥ 1, |a n,n | = ϕ n -P n ϕ n ≤ τ n . The fact that |a n,n | ≥ γ n τ n directly follows from lemma 4.1. S2: For m ≥ n, m j=n a 2 m,j = ϕ m -P n ϕ m 2 ≤ max ϕ∈F ϕ -P n ϕ 2 = τ 2 n .

Note that in the application of GEIM discussed in section 1, the compact set F is of this form.

Proof. The proof is similar with the one of lemma 4.8: the case n = 1 directly follows from lemma 4.4 and if n ≥ 2, we write n = N + K with N ≥ 0 and K ≥ 2. Corollary 5.5 yields

By using that d m ≤ C 0 m -α and the recurrence hypothesis τ N +1 ≤ β N +1 (N + 1) -α , it follows that

for any 1 ≤ m < K and any given index

where N ≥ 0 and K ≥ 2. It suffices now to decompose any n ≥ 2 as n = 4 + k with ∈ {0, 1, . . . } and k ∈ {0, 1, 2, 3} and use the same choices of N, K and m described in the proof of lemma 4.8 to derive the result.

Proof. The proof is the same as lemma 4.9 but uses corollary 5.4 instead of corollary 4.6.

As in the case of Banach spaces, it is important to study convergence rates in the case where (Λ n ) ∞ n=1 is monotonically increasing. The following corollary accounts for it.

Proof. The proof is derived by following the same guidelines as the proof of corollary 4.10. As a direct consequence of corollary 5.8, if γ n is constant, we recover slightly better results than the ones in [START_REF] Devore | Greedy algorithms for reduced bases in Banach spaces[END_REF] for n ≥ 2 (see lemmas 5.1 and 5.2 above).

Convergence rates of the interpolation error

Following similar guidelines as in the case of Banach spaces, the following rates can easily be derived for the interpolation error of GEIM. Theorem 5.9

where the parameter β n is defined as in lemma 5.6.

2. If, for n ≥ 1, d n ≤ C 0 e -c1n α with C 0 ≥ 1, then ϕ -J n [ϕ] X ≤ (1 + Λ n )C 0 β n e -c2n α for any ϕ ∈ F , where β n and c 2 are defined as in lemma 5.7.