Fitting a Sobolev function to data. I (Q268252)

In this impressive paper, the authors interpolate scattered data by a multivariate function \(F:\,{\mathbb R}^n \to {\mathbb R}\) whose Sobolev norm has the least possible order of magnitude. These new results extend former results of \textit{C. L. Fefferman} and \textit{B. Klartag} [Ann. Math. (2) 169, No. 1, 315 -- 346 (2009; Zbl 1175.41001)] on interpolation of scattered data by a \(C^m({\mathbb R}^n)\) function with a controlled norm. Let \(m \geq 1\) and \(p > n \geq 1\). Let \(E \subset {\mathbb R}^n\) be a finite set of \(N\) points. Further let \(W^{m,p}({\mathbb R}^n)\) be the Sobolev space. The authors produce efficient algorithms to solve the following interpolation problem: For a given function \(f:\,E \to {\mathbb R}\), compute an extension \(F \in W^{m,p}({\mathbb R}^n)\) of \(f\) with Sobolev norm having the smallest possible order of magnitude. The combined running time of the algorithms is at most \(CN\, \log N\), where the constant \(C\) depends only on \(m,n\), and \(p\).