Bounded manifold completion.

• Our algorithm detects a low-dimensional manifold that lies within a set of bounds. • The bounds are derived using a given high-dimensional dataset of a point cloud. • A matrix representing the distances on a low-dimensional manifold is low-rank. • Our method recovers a partially observed distance matrix using fully observed entries. • Low-rank matrix completion is used to recover partially observed distance matrices. Nonlinear dimensionality reduction is an active area of research. In this paper, we present a thematically different approach to detect a low-dimensional manifold that lies within a set of bounds derived from a given point cloud. A matrix representing distances on a low-dimensional manifold is low-rank, and our method is based on current low-rank Matrix Completion (MC) techniques for recovering a partially observed matrix from fully observed entries. MC methods are currently used to solve challenging real-world problems such as image inpainting and recommender systems. Our MC scheme utilizes efficient optimization techniques that employ a nuclear norm convex relaxation as a surrogate for non-convex and discontinuous rank minimization. The method theoretically guarantees on detection of low-dimensional embeddings and is robust to non-uniformity in the sampling of the manifold. We validate the performance of this approach using both a theoretical analysis as well as synthetic and real-world benchmark datasets. [ABSTRACT FROM AUTHOR]