Fitting a Sobolev function to data. II. (Q726773)

Summary: In this paper and two companion papers (Part I and Part III) [the authors, ibid. 32, No. 1, 275--376 (2016; Zbl 1338.65028); ibid. 32, No. 3, 1039--1126 (2016; Zbl 1386.65069)], 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 \to \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\).