Sparse Encoding of Observations from a Smooth Manifold via Locally Linear Approximations

Nicholas Bertrand, University of Colorado at Boulder


We investigate the problem of finding a parameterization of a smooth, low-dimensional manifold based on noisy observations from a high-dimensional ambient space. The formulation of such parameterizations sees applications in a variety of areas such as data denoising and image segmentation.

We propose an algorithm inspired by the existing k-svd algorithm for training dictionaries for sparse data representation, and the local best-fit flat algorithm for hybrid linear modeling. The output of our algorithm is an assignment of input data points to locally linear models. To demonstrate the applicability of our algorithm, we discuss experiments performed on synthetic datasets.