A new analysis of empirical interpolation methods and Chebyshev greedy algorithms

Abstract

We present new convergence estimates of generalized empirical interpolation methods in terms of the entropy numbers of the parametrized function class. Our analysis is transparent and leads to sharper convergence rates than the classical analysis via the Kolmogorov n-width. In addition, we also derive novel entropy-based convergence estimates of the Chebyshev greedy algorithm for sparse n-term nonlinear approximation of a target function. This also improves classical convergence analysis when corresponding entropy numbers decay fast enough.

arXiv comment18 pages, 4 figures

References in corpus (9)

• A New Selection Operator for the Discrete Empirical Interpolation Method -- improved a priori error bound and extensions
• Approximation and learning by greedy algorithms
• A Generalized Empirical Interpolation Method: application of reduced basis techniques to data assimilation
• Sharp Bounds on the Approximation Rates, Metric Entropy, and $n$-widths of Shallow Neural Networks
• Convergence analysis of the Generalized Empirical Interpolation Method
• A unified way of analyzing some greedy algorithms
• Banach space projections and Petrov-Galerkin estimates
• Entropy-based convergence rates of greedy algorithms
• A reduced conjugate gradient basis method for fractional diffusion