  Nonlinear dimensionality reduction or, equivalently, the approximation of
high-dimensional data using a low-dimensional nonlinear manifold is an active
area of research. In this paper, we will present a thematically different
approach to detect the existence of a low-dimensional manifold of a given
dimension that lies within a set of bounds derived from a given point cloud. A
matrix representing the appropriately defined distances on a low-dimensional
manifold is low-rank, and our method is based on current techniques for
recovering a partially observed matrix from a small set of fully observed
entries that can be implemented as a low-rank Matrix Completion (MC) problem.
MC methods are currently used to solve challenging real-world problems, such as
image inpainting and recommender systems, and we leverage extent efficient
optimization techniques that use a nuclear norm convex relaxation as a
surrogate for non-convex and discontinuous rank minimization. Our proposed
method provides several advantages over current nonlinear dimensionality
reduction techniques, with the two most important being theoretical guarantees
on the detection of low-dimensional embeddings and robustness 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.
