Revista Matemática Iberoamericana


Full-Text PDF (991 KB) | Metadata | Table of Contents | RMI summary
Volume 32, Issue 1, 2016, pp. 275–376
DOI: 10.4171/RMI/887

Published online: 2016-02-29

Fitting a Sobolev function to data I

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 $m \geq 1$ and $p > n \geq 1$. Given a finite set $E \subset \mathbb{R}^n$ and a function $f: E \rightarrow \mathbb{R}$, compute an extension $F$ of $f$ belonging to the Sobolev space $W^{m,p}(\mathbb{R}^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 $C N \mathrm{log} N$, where $N$ denotes the cardinality of $E$, and $C$ depends only on $m$, $n$, and $p$.

Keywords: Algorithm, interpolation, Sobolev spaces

Fefferman Charles, Israel Arie, Luli Garving: Fitting a Sobolev function to data I. Rev. Mat. Iberoamericana 32 (2016), 275-376. doi: 10.4171/RMI/887