# Fitting a Sobolev function to data III

### Charles Fefferman

Princeton University, United States### Arie Israel

University of Texas at Austin, USA### Garving K. Luli

University of California at Davis, USA

## Abstract

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,\mathfrak 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$.

## Cite this article

Charles Fefferman, Arie Israel, Garving K. Luli, Fitting a Sobolev function to data III. Rev. Mat. Iberoam. 32 (2016), no. 3, pp. 1039–1126

DOI 10.4171/RMI/908