Efficient formula reconstructs smooth functions from exact data
A Computationally-Efficient Closed-Form $C^{s,1}$-Extension Formula
Data Structures and Algorithms
Summary
This paper presents a new efficient method to reconstruct smooth functions from exact values and derivatives at specific points. The authors provide a formula that can recreate the function and its smoothness properties with guaranteed bounds regardless of how many data points are used. For smoothness levels two and higher, their method produces functions that are very well behaved analytically except at the data points. Their approach improves on existing formulas for the simplest cases and is computationally efficient for larger problems, allowing storing and evaluating the function quickly in parallel.
What this means in practice
- •For computational geometry teams: Efficiently reconstruct smooth surfaces from discrete measurements with guaranteed smoothness bounds using a closed-form formula.
- •For computer graphics developers: Generate smooth shapes from sampled data points quickly and with low memory using a circuit-based formula supporting parallel evaluation.
Authors
Anastasis Kratsios, Philipp Zimmermann
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.