Revista Matemática Iberoamericana


Full-Text PDF (1056 KB) | Metadata | Table of Contents | RMI summary
Volume 32, Issue 2, 2016, pp. 649–750
DOI: 10.4171/RMI/897

Published online: 2016-06-08

Fitting a Sobolev function to data II

Charles Fefferman[1], Arie Israel[2] and Garving K. Luli[3]

(1) Princeton University, United States
(2) University of Texas at Austin, USA
(3) University of California at Davis, USA

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$.

Keywords: Algorithm, interpolation, Sobolev spaces

Fefferman Charles, Israel Arie, Luli Garving: Fitting a Sobolev function to data II. Rev. Mat. Iberoamericana 32 (2016), 649-750. doi: 10.4171/RMI/897