论文标题
贪婪的重组插值法（Grim）
Greedy Recombination Interpolation Method (GRIM)
论文作者
论文摘要
在本文中，我们开发了贪婪的重组插值方法（GRIM），以找到最初作为某些（大）一些简单函数的线性组合的功能的稀疏近似值。 Grim以类似的精神与Cosamp算法相似，结合了基于动态生长的插值技术和基于稀疏的还原技术。基于动态增长的方面是对广义经验插值方法（GEIM）中使用的贪婪生长的修改。修改的结果是，我们的增长不仅限于吉姆（Geim）中的一个步骤。基于稀疏的方面是通过重组进行的，这是最近开创性凸内核正交法的关键组成部分。 Grim在减少度量的支持之外提供了首次使用重组。 Grim发现的近似值的稀疏性受数据的几何浓度控制，这与特定的数据数据相关。我们对径向基函数内核的内核正交任务进行了严峻的态度，并验证其性能是否与其他当代核正素技术相匹配。
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.
