SPARSE APPROXIMATE MULTIQUADRIC INTERPOLATION

Multiquadric interpolation is a technique for interpolating nonuniform samples of multivariate functions, in order to enable a variety of op erations such as data visualization. We are interested in computing sp arse but approximate interpolants, i.e., approximate interpolants with few coefficients. Such interpolants are useful since (1) the cost of evaluating the interpolant scales directly with the number of nonzero coefficients, and (2) the principle of Occam's Razor suggests that the interpolant with fewer coefficients better approximates the underlyin g function. Since the number of coefficients in a multiquadric interpo lant is, as is to be expected, equal to the number of data points in t he given set, the problem can be abstracted thus: given a set S of sam ples of a function f : R(k) --> R, and an error tolerance delta, find the smallest set of points T subset-or-equal-to S such that the multiq uadric interpolant of T is within delta of f over S. Using some recent results on sparse solutions of linear systems, we show how T may be s elected in a provably good fashion.