Greedy Recombination Interpolation Method (GRIM)

MaRDI QIDQ6507837arXivFDO

Authors Terence J. Lyons, Andrew D. McLeod

Published in arXiv

Mathematics Subject Classification ID

Interpolation in approximation theory (41A05) Rate of convergence, degree of approximation (41A25) Numerical interpolation (65D05) Applications to the sciences (65Z05) Numerical analysis (educational aspects) (97N40) Interpolation and approximation (educational aspects) (97N50)

Abstract: In this paper we develop the Generalised Recombination Interpolation Method (GRIM) for finding sparse approximations of functions initially given as linear combinations of some (large) number of simpler functions. GRIM is a hybrid of dynamic growth-based interpolation techniques and thinning-based reduction techniques. We establish that the number of non-zero coefficients in the approximation returned by GRIM is controlled by the concentration of the data. In the case that the functions involved are Lip$(gamma)$ for some $gamma>0$ in the sense of Stein, we obtain improved convergence properties for GRIM. In particular, we prove that the level of data concentration required to guarantee that GRIM finds a good sparse approximation is decreasing with respect to the regularity parameter $gamma>0$.

This page was built for publication: Greedy Recombination Interpolation Method (GRIM)

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