A new analysis of empirical interpolation methods and Chebyshev greedy algorithms

2024/01/25 by Li, Yuwen · 1 citation
#41A46 #41A65 #65J05 #65M12 #FOS: Mathematics #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.2401.13985

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.

Cited by

• Nearly optimal Kolmogorov widths under holomorphic mappings

Related

• Some New Convergence Analysis and Applications of POD-Greedy Algorithms
• Efficient Interpolation of Density Estimators
• Sparse sampling recovery by greedy algorithms
• Approximation and learning by greedy algorithms
• Interpolating Greedy and Reluctant Algorithms