Back to Search
Start Over
Greedy Recombination Interpolation Method (GRIM)
- Publication Year :
- 2022
-
Abstract
- In this paper we develop the Greedy Recombination Interpolation Method (GRIM) for finding sparse approximations of functions initially given as linear combinations of some (large) number of simpler functions. In a similar spirit to the CoSaMP algorithm, GRIM combines dynamic growth-based interpolation techniques and thinning-based reduction techniques. The dynamic growth-based aspect is a modification of the greedy growth utilised in the Generalised Empirical Interpolation Method (GEIM). A consequence of the modification is that our growth is not restricted to being one-per-step as it is in GEIM. The thinning-based aspect is carried out by recombination, which is the crucial component of the recent ground-breaking convex kernel quadrature method. GRIM provides the first use of recombination outside the setting of reducing the support of a measure. The sparsity of the approximation found by GRIM is controlled by the geometric concentration of the data in a sense that is related to a particular packing number of the data. We apply GRIM to a kernel quadrature task for the radial basis function kernel, and verify that its performance matches that of other contemporary kernel quadrature techniques.
- Subjects :
- Mathematics - Numerical Analysis
97N40, 97N50, 65Z05, 65D05, 41A05, 41A25
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2205.07495
- Document Type :
- Working Paper