Manifold Locally Optimal Projection (MLOP)

The dissemination of high-dimensional data poses many analytic and computational challenges. Of primal interest is the problem of extracting valuable information from such data. Often, the data suffers from the presence of noise, outliers, and non-uniform sampling, which can influence the result of the mining task. A common practice is to assume that the high-dimensional input data lies on an intrinsically low-dimensional Riemannian manifold. Given a noisy point-cloud situated near a low dimensional manifold, the proposed solution distributes points near the unknown manifold in a noise-free and quasi-uniformly manner, by leveraging a generalization of the robust L1-median to higher dimensions. We prove that the non-convex computational method converges to a local stationary solution with a bounded linear rate of convergence if the starting point is close enough to the local minimum. The effectiveness of our approach is demonstrated in various numerical experiments, by considering different manifold topologies with various amounts of noise, including a case of a manifold of different co-dimensions at different locations.

Function approximation and Manifold Locally Optimal Projection (FMLOP)

Let us consider the fundamental problem of approximation of functions on a low-dimensional manifold embedded in a high-dimensional space. Classical approximation methods, developed for the low-dimensional case, are challenged by the high-dimensional data, and the presence of noise. Here, we introduce a new approximation method that is parametrization free, can handle noise and outliers in both the scattered data and function values and does not require any assumptions on the scattered data geometry. Given a noisy point-cloud situated near a low dimensional manifold and the corresponding noisy function values, the proposed solution finds a noise-free, quasi-uniform manifold reconstruction as well as the denoised function values at these points. Next, this data is used to approximate the function at new points near the manifold. We prove that in the case of noise-free samples, the approximation order is quadratic in the fill-distance.

Repairing Manifold via Locally Optimal Projection (RMLOP)

Last, we study the problem of the repairing and recovery of a low-dimensional manifold embedded in high-dimensional space from noisy scattered data. Suppose that we observe a point cloud sampled from the low-dimensional manifold, with noise. Let us also assume that part of the scattered data is missing, which results in holes in the data. Can we recover missing information inside the holes? While in the low-dimension the problem was extensively studied, manifold repairing in high dimensions is still an open problem. We introduce a new approach, called Repairing Manifold via Locally Optimal Projection (R-MLOP) to cope with manifold repairing in low and high-dimensional cases. We prove that the suggested solution recovers missing information inside the hole, with an approximation order that is controlled by the density of the sample as well as the size of the amended hole.

List of papers related to this project:

    1) Manifold Reconstruction and Denoising from Scattered Data in High Dimension via a Generalization of L1-Median
    Faigenbaum-Golovin, S., Levin, D.,
    Journal of Computational and Applied Mathematics, 421, 114818, 2023.
    2) Approximation of Functions over Manifolds in High Dimension from Noisy Scattered Data
    Faigenbaum-Golovin, S., Levin, D.,
    Jaen Journal on Approximation, Vol. 13, 43-73, 2022.
    3) Mind The Gap: Hole-Filling and Reconstruction in High-Dimensional Manifolds
    Faigenbaum-Golovin, S., Levin, D.,