Multilevel interpolation and approximation

Interpolation by translates of a given radial basis function (RBF) has beco me a well-recognized means of fitting functions sampled at scattered sites in Ed. A major drawback of these methods is their inability to interpolate very large data sets in a numerically stable way while maintaining a good f it. To circumvent this problem, a multilevel interpolation (ML) method for scattered data was presented by Floater and Iske. Their approach involves m levels of interpolation where at the jth level, the residual of the previo us level is interpolated. On each level, the RBF is scaled to match the dat a density. In this paper, we provide some theoretical underpinnings to the ML method by establishing rates of approximation for a technique that devia tes somewhat from the Floater-Iske setting. The final goal of the ML method will be to provide a numerically stable method for interpolating several t housand points rapidly. (C) 1999 Academic Press.