Convergence analysis of the Generalized Empirical Interpolation Method
Provides theoretical convergence guarantees for GEIM, a method used in reduced-order modeling and scientific computing, but the analysis is incremental as it extends existing error bounds.
This paper analyzes the Generalized Empirical Interpolation Method (GEIM) and proves that its interpolation error decays at the same rate as the Kolmogorov n-width of the compact set F, up to a factor involving the norm of the interpolation operator. For Hilbert spaces, sharper results are obtained.
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 $(σ_i(f))_{i=1}^n$, where $σ_i\in \mathcal{X}'$ and $\mathcal{X}'$ 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 $(σ_i)_{i=1}^n$ from a dictionary $Σ\subset \mathcal{X}'$. 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.