Fast algorithm to approximately fit a C^m-smooth function to data

You need to know: Euclidean space ${\mathbb R}^n$ , space of functions $C^m({\mathbb R}^n)$ (see this previous theorem description), notation $||F||_{C^m({\mathbb R}^n)}$ for the norm in this space, algorithm, its running time and memory use.

Background: Let $E \subset {\mathbb R}^n$ be a finite set of cardinality N. Let $f:E \to {\mathbb R}$ and $\sigma: E \to [0, \infty)$ be given functions on E. Let $||f||_{C^m(E,\sigma)}$ denote the infimum of all $M>0$ for which there exists $F \in C^m({\mathbb R}^n)$ such that $||F||_{C^m({\mathbb R}^n)}\leq M$ and $|F(x)-f(x)| \leq M \sigma(x)$ for all $x \in E$ . We say that two numbers $X, Y \geq 0$ determined by $E, f, \sigma, m, n$ have the same order of magnitude if $cX \leq Y \leq CX$ , where constants c and C depends only on m and n. By “compute the order of magnitude of X” we mean compute some Y such that X and Y have the same order of magnitude.

The Theorem: On 6th October 2005, Charles Fefferman and Bo’az Klartag submitted to the Annals of Mathematics a paper in which they presented an algorithm and proved that it computes, given $E, f, \sigma, m, n$ , the order of magnitude of $||f||_{C^m(E,\sigma)}$ in time at most $CN \log N$ and using memory at most $CN$ , where the constant C depends only on m and n.

Short context: Function $f:E \to {\mathbb R}$ represents N data points, to which we want to feet a smooth function F with smallest possible $C^m({\mathbb R}^n)$ norm. We may want the exact feet to data (case $\sigma=0$ ), or approximate one ( $\sigma \neq 0$ ). The Theorem proves the existence of efficient algorithm which approximately computes the smallest possible $C^m({\mathbb R}^n)$ norm of F we can achieve. In the subsequent paper, we same authors also presented algorithm which computes F itself.