Geometric harmonics: A novel tool for multiscale out-of-sample extension of empirical functions

We describe a simple scheme, based on the Nystrom method, for extending empirical functions f defined on a set X to a larger set X. The extension process that we describe involves the construction of a specific family of functions that we term geometric harmonics. These functions constitute a generalization of the prolate spheroidal wave functions of Slepian in the sense that they are optimally concentrated on X. We study the case when X is a submanifold of R-n in greater detail. In this situation, any empirical function f on X can be characterized by its decomposition over the intrinsic Fourier modes, i.e., the eigenfunctions of the Laplace-Beltrami operator, and we show that this intrinsic frequency spectrum determines the largest domain of extension of f to the entire space R-n. Our analysis relates the complexity of the function on the training set to the scale of extension off this set. This approach allows us to present a novel multiscale extension scheme for empirical functions. (C) 2006 Published by Elsevier Inc.