论文标题
通过$ l_1 $ -Median的概括，在高维数据中从分散数据中重建和转化
Manifold Reconstruction and Denoising from Scattered Data in High Dimension via a Generalization of $L_1$-Median
论文作者
论文摘要
在本文中，我们提出了一种在高维空间中降低和重建低维歧管的方法。我们建议Lipman等人引入的本地最佳投影算法的多维扩展。 2007年，用于3D中的表面重建。该方法绕过了维度的诅咒，并避免了进行维度降低的需求。它基于非凸优化问题，该问题利用了较高的L1-Median对更高尺寸的概括，同时生成无噪声的准均匀分布点，重建未知的低维歧管。我们开发了一种新的算法，并证明它会收敛到局部固定解决方案，如果起点足够接近局部最小值，则具有有界线性的收敛速率。此外，我们表明其近似顺序为$ O（H^2）$，其中$ h $是给定点之间的代表距离。我们通过考虑具有各种噪声的不同歧管拓扑来证明我们的方法的有效性，包括不同位置的不同共限度的歧管的情况。
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.
