Convergence analysis of the generalized empirical interpolation method

DOI10.1137/140978843MaRDI QIDQ2814454zbMATH OpenOpenAlexFDO

Authors O. Mula, Gabriel Turinici, Yvon Maday

Publication date 22 June 2016

Published in SIAM Journal on Numerical Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.07730

zbMATH Keywords

convergence ratesdata assimilationgeneralized empirical interpolationgreedy algorithmKolmogorov widthsoptimal recoveryreduced basis

Mathematics Subject Classification ID

Rate of convergence, degree of approximation (41A25) Approximation by arbitrary linear expressions (41A45) Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65) Error bounds for boundary value problems involving PDEs (65N15)

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

Review text

Using an adaptive greedy algorithm, interpolation schemes are studied to approximate functions from a Banach space \(\mathcal X\) (later-on also for a Hilbert space, where improved error estimates are found), where the approximand is restricted to a compact subset \(F\) and the approximant is from an \(n\)-dimensional subspace of \(\mathcal X\). That subspaces adapts itself to \(F\) and is constructed by a greedy method. The interpolation errors are estimated in particular by relating them to the error of the best approximation, the \(n\)-width. Up to an increased error due to the operator norm of the approximation, these errors in the actual approximation algorithm are shown to be asymptotically the same as the \(n\)-width so long as it has polynomial or exponential decay. The implementations of the methods are discussed too.

Recommendations

• Greedy algorithms for reduced bases in Banach spaces
• Convergence rates for greedy algorithms in reduced basis methods
• On greedy algorithm approximating Kolmogorov widths in Banach spaces
• Approximation of parametric derivatives by the empirical interpolation method
• The generalized empirical interpolation method: stability theory on Hilbert spaces with an application to the Stokes equation

Cites work

• A general multipurpose interpolation procedure: The magic points
• A generalized empirical interpolation method: application of reduced basis techniques to data assimilation
• A parameterized-background data-weak approach to variational data assimilation: formulation, analysis, and application to acoustics
• An `empirical interpolation' method: Application to efficient reduced-basis discretization of partial differential equations
• Convergence rates for greedy algorithms in reduced basis methods
• Data assimilation and sampling in Banach spaces
• Data Assimilation in Reduced Modeling
• Efficient reduced-basis treatment of nonaffine and nonlinear partial differential equations
• Greedy algorithms for reduced bases in Banach spaces
• scientific article; zbMATH DE number 3877692 (Why is no real title available?)
• scientific article; zbMATH DE number 4144656 (Why is no real title available?)
• scientific article; zbMATH DE number 1795892 (Why is no real title available?)
• Locally adaptive greedy approximations for anisotropic parameter reduced basis spaces
• Meshless methods: An overview and recent developments
• The generalized empirical interpolation method: stability theory on Hilbert spaces with an application to the Stokes equation
• The optimal recovery of smooth functions

Cited in

(34)

• Sensor placement in nuclear reactors based on the generalized empirical interpolation method
• The numerical approximation of nonlinear functionals and functional differential equations
• The generalized empirical interpolation method: stability theory on Hilbert spaces with an application to the Stokes equation
• Performance guarantees for a variational ``multi-space decoder
• Fast reconstruction of 3D blood flows from Doppler ultrasound images and reduced models
• Reducing sensors for transient heat transfer problems by means of variational data assimilation
• An EIM-degradation free reduced basis method via over collocation and residual hyper reduction-based error estimation
• A hyper-reduced MAC scheme for the parametric Stokes and Navier-Stokes equations
• A novel class of stabilized greedy kernel approximation algorithms: convergence, stability and uniform point distribution
• QTT-finite-element approximation for multiscale problems. I: Model problems in one dimension
• Variants of the empirical interpolation method: symmetric formulation, choice of norms and rectangular extension
• Stabilization of generalized empirical interpolation method (GEIM) in presence of noise: a novel approach based on Tikhonov regularization
• A weighted empirical interpolation method: a priori convergence analysis and applications
• The Discrete Empirical Interpolation Method: Canonical Structure and Formulation in Weighted Inner Product Spaces
• Approximation of parametric derivatives by the empirical interpolation method
• Magic Points in Finance: Empirical Integration for Parametric Option Pricing
• Nonlinear model reduction on metric spaces. Application to one-dimensional conservative PDEs in Wasserstein spaces
• State estimation with model reduction and shape variability. Application to biomedical problems
• A Multiscale Neural Network Based on Hierarchical Matrices
• Nonintrusive approximation of parametrized limits of matrix power algorithms -- application to matrix inverses and log-determinants
• Nonlinear reduced models for state and parameter estimation
• Wasserstein model reduction approach for parametrized flow problems in porous media
• A-posteriori reduced basis error-estimates for a semi-discrete in space quasilinear parabolic PDE
• Inverse problems: a deterministic approach using physics-based reduced models
• Sparse Wasserstein barycenters and application to reduced order modeling
• Neural-network-augmented empirical interpolation method for field reconstruction with noise and vibration tolerance
• Spatiotemporal GEIM for ultra-real-time prediction of coupled multi-physics in reactor transients using sparse observations
• Empirical sparse regression on quadratic manifolds
• A new rational approximation algorithm via the empirical interpolation method
• Reduced Krylov basis methods for parametric partial differential equations
• A new analysis of empirical interpolation methods and Chebyshev greedy algorithms
• Multi-physics model bias correction with data-driven reduced order techniques: application to nuclear case studies
• Bias and multiscale correction methods for variational state estimation
• Some new convergence analysis and applications of POD-Greedy algorithms

This page was built for publication: Convergence analysis of the generalized empirical interpolation method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2814454)