Higher Order Lipschitz Greedy Recombination Interpolation Method (HOLGRIM)

In this paper we introduce the Higher Order Lipschitz Greedy Recombination Interpolation Method (HOLGRIM) for finding sparse approximations of Lip$(\gamma)$ functions, in the sense of Stein, given as a linear combination of a (large) number of simpler Lip$(\gamma)$ functions. HOLGRIM is developed as a refinement of the Greedy Recombination Interpolation Method (GRIM) in the setting of Lip$(\gamma)$ functions. HOLGRIM combines dynamic growth-based interpolation techniques with thinning-based reduction techniques in a data-driven fashion. The dynamic growth is driven by a greedy selection algorithm in which multiple new points may be selected at each step. The thinning reduction is carried out by recombination, the linear algebra technique utilised by GRIM. We establish that the number of non-zero weights for the approximation returned by HOLGRIM is controlled by a particular packing number of the data. The level of data concentration required to guarantee that HOLGRIM returns a good sparse approximation is decreasing with respect to the regularity parameter $\gamma > 0$. Further, we establish complexity cost estimates verifying that implementing HOLGRIM is feasible.