arXiv preprint ·
A Computationally-Efficient Closed-Form $C^{s,1}$-Extension Formula
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We identify explicit closed-form and variational formulae for interpolating the exact values and derivatives through order $s$ of a $C^{s,1}$ function $f:\mathbb{R}^d\to\mathbb{R}$ at $N$ distinct points in $[0,1]^d$. The reconstruction satisfies bounds on its global $C^{s,1}$ seminorm and its Lipschitz constant on $[0,1]^d$ that are independent of the sample size $N$, the latter being the sharp Whitney condition. For $s\ge2$, the reconstruction is real analytic away from the data points and definable in the o-minimal structure $\mathbb{R}_{\exp}$. Our nonlinear extension formula coincides with the formula of McShane (1934) for $s=0$ and with the formulae of Le Gruyer and Phan (2015) and Azagra, Le Gruyer, and Mudarra (2018) for $s=1$, and is new for $s\ge2$. For fixed $d$ and $s\ge2$, our closed-form formula is computable away from the data points by a circuit using only elementary unary and binary real operations, with $\mathcal{O}(N)$ gates and $\mathcal{O}(\log N)$ depth. This yields $\mathcal{O}(N)$ storage and $\mathcal{O}(\log N)$ parallel evaluation time. From the supplied coefficients and weights, the circuit can be compiled with $\mathcal{O}(N)$ one-time work in the exact-real word-RAM model. Thus, in this supplied-data setting, our nonlinear construction improves by a logarithmic factor on the $\mathcal{O}(N\log N)$ initialization bound of Fefferman and Klartag (2009), while retaining linear storage and attaining logarithmic query time through parallel evaluation.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Functional Analysis
Description Complexity Bounds for Analytic Approximations of Lipschitz Functions
The double descent and Runge phenomena in overparametrized polynomial interpolation
On the gradient conjecture at infinity: Finite spherical length for gradient trajectories of definable potentials
Why Directly Learning Periodic Trajectories Can Fail
Resolving Tusnády's Problem
Get the few papers worth your time in Functional Analysis every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.