Convergence analysis of the Generalized Empirical Interpolation Method

Abstract

Let $F$ be a compact set of a Banach space $\mathcal{X}$. This paper analyses the "Generalized Empirical Interpolation Method" (GEIM) which, given a function $f\in F$, builds an interpolant ${\mathcal{J}}_n[f]$ in an $n$-dimensional subspace $X_n\subset \mathcal{X}$ with the knowledge of $n$ outputs $({\sigma }_i(f){)}_{i=1}^n$, where ${\sigma }_i\in {\mathcal{X}}^{\prime }$ and ${\mathcal{X}}^{\prime }$ is the dual space of $\mathcal{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 $({\sigma }_i{)}_{i=1}^n$ from a dictionary $\Sigma \subset {\mathcal{X}}^{\prime }$. In this paper, we study the interpolation error ${\max }_{f\in F}\Vert f-{\mathcal{J}}_n[f]{\Vert }_{\mathcal{X}}$ by comparing it with the best possible performance on an $n$-dimensional space, i.e., the Kolmogorov $n$-width of $F$ in $\mathcal{X}$, $d_n(F,\mathcal{X})$. For polynomial or exponential decay rates of $d_n(F,\mathcal{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 $\mathcal{X}$ is a Hilbert space.

arXiv admin note: text overlap with arXiv:1204.2290 by other authors

Cited by in corpus (10)

• A novel class of stabilized greedy kernel approximation algorithms: Convergence, stability & uniform point distribution
• The Numerical Approximation of Nonlinear Functionals and Functional Differential Equations
• Multi-Physics Model Bias Correction with Data-Driven Reduced Order Modelling Techniques: Application to Nuclear Case Studies
• Reconstructing Haemodynamics Quantities of Interest from Doppler Ultrasound Imaging
• State Estimation with Model Reduction and Shape Variability. Application to biomedical problems
• An error indicator-based adaptive reduced order model for nonlinear structural mechanics -- application to high-pressure turbine blades
• A hyper-reduced MAC scheme for the parametric Stokes and Navier-Stokes equations
• Reduced Krylov Basis Methods for Parametric Partial Differential Equations
• A new analysis of empirical interpolation methods and Chebyshev greedy algorithms
• Nonintrusive approximation of parametrized limits of matrix power algorithms -- application to matrix inverses and log-determinants