Generalised Recombination Interpolation Method (GRIM)

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$.