Fitting a Sobolev function to data II
Charles Fefferman, Arie Israel, Garving K. Luli · Revista Matemática Iberoamericana · 2016
In this paper and two companion papers, we produce efficient algorithms to solve the following interpolation problem. Let \mathfrak m \geq 1 and \mathfrak p > \mathfrak n \geq 1 . Given a finite set E \subset \mathbb{R}^{\mathfrak n} and a function f: E \rightarrow \mathbb{R} , compute an extension F of f belonging to the Sobolev space W^{\mathfrak {m,p}}(\mathbb{R}^{\mathfrak 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 \mathfrak m , \mathfrak n , and \mathfrak p .