CONVERGENCE ANALYSIS OF THE GENERALIZED EMPIRICAL INTERPOLATION METHOD.

Let F be a compact set of a Banach space X. This paper analyzes the "generalized empirical interpolation method," 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))ⁿ_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)ⁿ_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. [ABSTRACT FROM AUTHOR]