Approximation of Functions Over Manifolds by Moving Least Squares

Applied and Computational Mathematics Seminar
Monday, October 16, 2017 - 14:00
1 hour (actually 50 minutes)
Skiles 005
Tel Aviv University
We approximate a function defined over a $d$-dimensional manifold $M ⊂R^n$ utilizing only noisy function values at noisy locations on the manifold. To produce the approximation we do not require any knowledge regarding the manifold other than its dimension $d$. The approximation scheme is based upon the Manifold Moving Least-Squares (MMLS) and is therefore resistant to noise in the domain $M$ as well. Furthermore, the approximant is shown to be smooth and of approximation order of $O(h^{m+1})$ for non-noisy data, where $h$ is the mesh size w.r.t $M,$ and $m$ is the degree of the local polynomial approximation. In addition, the proposed algorithm is linear in time with respect to the ambient space dimension $n$, making it useful for cases where d is much less than n. This assumption, that the high dimensional data is situated on (or near) a significantly lower dimensional manifold, is prevalent in many high dimensional problems. Thus, we put our algorithm to numerical tests against state-of-the-art algorithms for regression over manifolds and show its dominance and potential.