Fitting a Sobolev function to data I

Abstract

In this paper and two companion papers, we produce efficient algorithms to solve the following interpolation problem: Let $m\ge 1$ and $p>n\ge 1$. Given a finite set $E\subset {\mathbb{R}}^n$ and a function $f:E\to \mathbb{R}$, compute an extension $F$ of $f$ belonging to the Sobolev space $W^{m,p}({\mathbb{R}}^n)$ with norm having the smallest possible order of magnitude; secondly, compute the order of magnitude of the norm of $F$. The combined running time of our algorithms is at most $CN\log N$, where $N$ denotes the cardinality of $E$, and $C$ depends only on $m$, $n$, and $p$.