Entropy-based convergence rates of greedy algorithms

DOI10.1142/S0218202524500143arXiv2304.13332WikidataQ129663209 ScholiaQ129663209MaRDI QIDQ6509828FDOQ6509828

Abstract: We present convergence estimates of two types of greedy algorithms in terms of the metric entropy of underlying compact sets. In the first part, we measure the error of a standard greedy reduced basis method for parametric PDEs by the metric entropy of the solution manifold in Banach spaces. This contrasts with the classical analysis based on the Kolmogorov n-widths and enables us to obtain direct comparisons between the greedy algorithm error and the entropy numbers, where the multiplicative constants are explicit and simple. The entropy-based convergence estimate is sharp and improves upon the classical width-based analysis of reduced basis methods for elliptic model problems. In the second part, we derive a novel and simple convergence analysis of the classical orthogonal greedy algorithm for nonlinear dictionary approximation using the metric entropy of the symmetric convex hull of the dictionary. This also improves upon existing results by giving a direct comparison between the algorithm error and the metric entropy.

Mathematics Subject Classification ID

Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65) Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs (65M12) Error bounds for boundary value problems involving PDEs (65N15) Rate of convergence, degree of approximation (41A25) Approximation by arbitrary nonlinear expressions; widths and entropy (41A46)

This page was built for publication: Entropy-based convergence rates of greedy algorithms

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