Approximation of functions over manifolds : A Moving Least-Squares approach
Year of publication
2021
Authors
Sober, Barak; Aizenbud, Yariv; Levin, David
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 knowledge about the local geometry of the manifold or its local parameterizations. We do require, however, knowledge regarding the manifold's intrinsic dimension d. We use the Manifold Moving Least-Squares approach of Sober and Levin (2019) 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 O(hm+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. Additionally, we show numerically that our approach compares favorably to some well-known approaches for regression over manifolds.
Show moreOrganizations and authors
University of Jyväskylä
Aizenbud Yariv
Publication type
Publication format
Article
Parent publication type
Journal
Article type
Original article
Audience
ScientificPeer-reviewed
Peer-ReviewedMINEDU's publication type classification code
A1 Journal article (refereed), original researchPublication channel information
Publisher
Volume
383
Article number
113140
ISSN
Publication forum
Publication forum level
2
Open access
Open access in the publisher’s service
No
Self-archived
Yes
Other information
Fields of science
Mathematics
Keywords
[object Object],[object Object],[object Object],[object Object]
Publication country
Netherlands
Internationality of the publisher
International
Language
English
International co-publication
Yes
Co-publication with a company
No
DOI
10.1016/j.cam.2020.113140
The publication is included in the Ministry of Education and Culture’s Publication data collection
Yes