Approximation of functions over manifolds: a moving least-squares approach

DOI10.1016/J.CAM.2020.113140MaRDI QIDQ2199793zbMATH OpenOpenAlexWikidataFDO

Authors Yanyan Li

Publication date 14 September 2020

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.00765

zbMATH Keywords

dimension reductionhigh-dimensional approximationmanifold learningmoving least-squaresout-of-sample extensionregression over manifolds

Mathematics Subject Classification ID

Series expansions (e.g., Taylor, Lidstone series, but not Fourier series) (41A58) Computational methods for problems pertaining to statistics (62-08) Statistics on manifolds (62R30) Algorithms for approximation of functions (65D15)

Abstract: We present an algorithm for approximating a function defined over a $d$-dimensional manifold utilizing only noisy function values at locations sampled from the manifold with noise. To produce the approximation we do not require any knowledge regarding the manifold other than its dimension $d$. We use the Manifold Moving Least-Squares approach of (Sober and Levin 2016) to reconstruct the atlas of charts and the approximation is built on-top of those charts. The resulting approximant is shown to be a function defined over a neighborhood of a manifold, approximating the originally sampled manifold. In other words, given a new point, located near the manifold, the approximation can be evaluated directly on that point. We prove that our construction yields a smooth function, and in case of noiseless samples the approximation order is $mathcalO(h^{m+1})$, where $h$ is a local density of sample parameter (i.e., the fill distance) and $m$ is the degree of a local polynomial approximation, used in our algorithm. In addition, the proposed algorithm has linear time complexity with respect to the ambient-space's dimension. Thus, we are able to avoid the computational complexity, commonly encountered in high dimensional approximations, without having to perform non-linear dimension reduction, which inevitably introduces distortions to the geometry of the data. Additionaly, we show numerical experiments that the proposed approach compares favorably to statistical approaches for regression over manifolds and show its potential.

Recommendations

• Manifold approximation by moving least-squares projection (MMLS)
• Scattered manifold-valued data approximation
• Ambient spline approximation on manifolds
• SPLINE APPROXIMATIONS ON MANIFOLDS
• Implicit manifold reconstruction

Cites work

• 10.1162/153244304322972667
• Curvature Measures
• Diffusion maps
• Fast high-dimensional approximation with sparse occupancy trees
• Geodesic Entropic Graphs for Dimension and Entropy Estimation in Manifold Learning
• Geometric harmonics: a novel tool for multiscale out-of-sample extension of empirical functions
• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• scientific article; zbMATH DE number 3284143 (Why is no real title available?)
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• Local linear regression on manifolds and its geometric interpretation
• Manifold parametrizations by eigenfunctions of the Laplacian and heat kernels
• Moving least-squares are Backus-Gilbert optimal
• Multi-resolution geometric analysis for data in high dimensions
• Multi-scale geometric methods for data sets. II: Geometric multi-resolution analysis
• Multiscale geometric methods for data sets. I: Multiscale SVD, noise and curvature.
• Multivariate locally weighted least squares regression
• Nonlinear Dimensionality Reduction
• Optimal rates of convergence for nonparametric estimators
• Principal component analysis.
• Regression on manifolds: estimation of the exterior derivative
• Self-organizing maps.
• Surfaces Generated by Moving Least Squares Methods
• The approximation power of moving least-squares
• Universal algorithms for learning theory. I: Piecewise constant functions.
• Universal algorithms for learning theory. II: Piecewise polynomial functions

Cited in

(16)

• Manifold learning with arbitrary norms
• A direct approach for function approximation on data defined manifolds
• Manifold reconstruction and denoising from scattered data in high dimension
• Distributed learning via filtered hyperinterpolation on manifolds
• Manifold approximation by moving least-squares projection (MMLS)
• Approximating the span of principal components via iterative least-squares
• Smooth function extension based on high dimensional unstructured data
• Scattered manifold-valued data approximation
• Approximation of functions on manifolds in high dimension from noisy scattered data
• A double Fourier sphere method for \(d\)-dimensional manifolds
• Optimal reach estimation and metric learning
• Minimax boundary estimation and estimation with boundary
• An optimal ansatz space for moving least squares approximation on spheres
• Estimation of local geometric structure on manifolds from noisy data
• A semi-Lagrangian scheme on embedded manifolds using generalized local polynomial reproductions
• Fast and Stable Harmonic Approximation from Ill-distributed Data using Moving Least Squares

Describes a project that uses

Uses Software

• COIL-20

This page was built for publication: Approximation of functions over manifolds: a moving least-squares approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2199793)