2019/12/19 by Kelum Gajamannage, Gajamannage, Kelum, Randy Paffenroth +1 · 1 citation
Computer Science · Mathematics · #68T05 #Computer Vision and Pattern Recognition (cs.CV) #FOS: Computer and information sciences #H.2.8 #I.2.6 #Machine Learning (cs.LG) #Machine Learning (stat.ML) #acm:68T05 #cs.CV #cs.LG #msc:68T05 #stat.ML
paper · pdf · doi:10.48550/arxiv.1912.09026
12 pages, 7 figures, submitted to Pattern Recognition Journal
arxiv created 2019/12/19 · arxiv updated 2019/12/21
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.