Fitting a Cm-smooth function to data, I
Charles Fefferman, Bo’az Klartag · Annals of Mathematics · 2009
Suppose we are given a finite subset E ⊂ R n and a function f : E → R. How to extend f to a C m function F : R n → 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 CN log N , where N is the cardinality of E and C is a constant depending only on m and n.