Fitting a $C^m$-smooth function to data, I

Abstract

Suppose we are given a finite subset $E \subset \mathbb{R}^n$ and a function $f: E \rightarrow \mathbb{R}$. How to extend $f$ to a $C^m$ function $F: \mathbb{R}^n \rightarrow \mathbb{R}$ with $C^m$ norm of the smallest possible order of magnitude? In this paper and in [20] we tackle this question from the perspective of theoretical computer science. We exhibit algorithms for constructing such an extension function $F$, and for computing the order of magnitude of its $C^m$ norm. The running time of our algorithms is never more than $C N \log N$, where $N$ is the cardinality of $E$ and $C$ is a constant depending only on $m$ and $n$.