Efficient Algorithms for Approximate Smooth Selection

Abstract

In this paper we provide efficient algorithms for approximate ${\mathcal{C}}^m({\mathbb{R}}^n,{\mathbb{R}}^D)-$selection. In particular, given a set $E$, constants $M_0>0$ and $0<\ddot{I}„\le \ddot{I}{„}_{\max }$, and convex sets $K(x)\subset {\mathbb{R}}^D$ for $x\in E$, we show that an algorithm running in $C(\ddot{I}„)N\log N$ steps is able to solve the smooth selection problem of selecting a point $y\in (1+\ddot{I}„)⧫K(x)$ for $x\in E$ for an appropriate dilation of $K(x)$, $(1+\ddot{I}„)⧫K(x)$, and guaranteeing that a function interpolating the points $(x,y)$ will be ${\mathcal{C}}^m({\mathbb{R}}^n,{\mathbb{R}}^D)$ with norm bounded by $C{M}_0$.

98 pages, submitted to Journal of Geometric Analysis. arXiv admin note: text overlap with arXiv:1511.04804, arXiv:1603.02323