# Fitting a Sobolev function to data I

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

## Cite this article

Charles Fefferman, Arie Israel, Garving K. Luli, Fitting a Sobolev function to data I. Rev. Mat. Iberoam. 32 (2016), no. 1, pp. 275–376

DOI 10.4171/RMI/887