Manifold Reconstruction and Denoising from Scattered Data in High Dimension via a Generalization of $L_1$-Median
Authors:
Preprint
Abstract
In this paper, we present a method for denoising and reconstruction of low-dimensional manifold in high-dimensional space. We suggest a multidimensional extension of the Locally Optimal Projection algorithm which was introduced by Lipman et al. in 2007 for surface reconstruction in 3D. The method bypasses the curse of dimensionality and avoids the need for carrying out dimensional reduction. It is based on a non-convex optimization problem, which leverages a generalization of the outlier robust L1-median to higher dimensions while generating noise-free quasi-uniformly distributed points reconstructing the unknown low-dimensional manifold. We develop a new algorithm and prove that it converges to a local stationary solution with a bounded linear rate of convergence in case the starting point is close enough to the local minimum. In addition, we show that its approximation order is $O(h^2)$, where $h$ is the representative distance between the given points. We demonstrate the effectiveness of our approach by considering different manifold topologies with various amounts of noise, including a case of a manifold of different co-dimensions at different locations.
Keywords
All Related Versions
This publication has 28 references indexed in Scilit:
- Manifold Approximation by Moving Least-Squares Projection (MMLS)Constructive Approximation, 2019
- Constraint-based point set denoising using normal voting tensor and restricted quadratic error metricsComputers & Graphics, 2018
- Algorithmic handwriting analysis of Judah’s military correspondence sheds light on composition of biblical textsProceedings of the National Academy of Sciences, 2016
- Manifold Reconstruction Using Tangential Delaunay ComplexesDiscrete & Computational Geometry, 2013
- Approximation of High-Dimensional Rank One TensorsConstructive Approximation, 2013
- Geometric Inference for Probability MeasuresFoundations of Computational Mathematics, 2011
- Manifold Reconstruction in Arbitrary Dimensions Using Witness ComplexesDiscrete & Computational Geometry, 2009
- Finding the Homology of Submanifolds with High Confidence from Random SamplesDiscrete & Computational Geometry, 2008
- Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion mapsProceedings of the National Academy of Sciences, 2005
- Estimating bounds on the highest and lowest eigenvalues of any matrixTheoretical Chemistry Accounts, 2000