Bounded manifold completion

PATTERN RECOGNITION

卷:111

Article

Gajamannage, Kelum¹  Paffenroth, Randy² 

[1] Texas A&M Univ, Dept Math & Stat, Corpus Christi, TX 78412 USA

[2] Worcester Polytech Inst, Dept Math Sci, Dept Comp Sci, Data Sci Program, Worcester, MA 01609 USA

关键词: Manifold;    Low-rank matrix completion;    Positive semi-definite;    Truncated nuclear norm;    Gramian;   

DOI  :  10.1016/j.patcog.2020.107661

来源: Elsevier

【 摘 要 】

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. (C) 2020 Elsevier Ltd. All rights reserved.

【 授权许可】

Free