On nonlinear dimensionality reduction, linear smoothing, and boundary conditions

Abstract

We develop theory for nonlinear dimensionality reduction (NLDR). While a large number of NLDR methods have been proposed in the literature, there is limited understanding of how these methods work and how they interrelate. Also, existing theory provides little in the way of leverage for devising new algorithms. We provide a novel theoretical framework for the analysis of NLDR based on a connection to the statistical theory of linear smoothers. This allows us to both understand existing methods and derive new ones. We use this connection to show that existing NLDR methods correspond asymptotically to discrete approximations of the solutions of sets of differential equations given a boundary condition. In particular, we can characterize many existing methods in terms of just three limiting differential operators and boundary conditions. Our theory also provides a way to assert that one method is preferable to another; indeed, we show that local tangent space alignment is superior within a class of methods that assume that a global coordinate chart defines an isometric embedding of the manifold.